栈实现浏览器的前进和后退功能

一 概述

当你一次访问完一串页面a-b-c之后，点击浏览器的后退按钮，就可以查看之前浏览过的页面b和a。当你后退到页面a，点击前进按钮，就可以重新查看页面b和c。但是，如果你后退到页面b后，点击了新的页面d，那就无法再前继，后退功能查看页面c了。

二 栈

关于栈操作可以比作看书，一般都是一张纸一张纸的往后阅读，如同进栈操作从前往后进栈，出栈如同一张纸一张纸的往前合上书籍，如同出栈操作从后往前出栈。出栈结束表示整本书都关闭了。所有后进先出，先进后出，就是典型的"栈"结构。

                          

栈是一种操作特性上来看，栈是一种"操作受限"的线性表，只允许在一端插入和删除数据。当从这种功能上来说，数组或者链表确实可以替代栈，可是特定的数据结构是对特定场景的抽象，而且，数组或链表暴露了太多的操作接口，操作上的确灵活*，但使用时就比较不可控，自然也就更容易出错。

当某个数据集合只涉及在一端插入和删除数据，并且满足后进先出，先进后出的特性，我们就应该首选"栈"这种数据结构。

三 栈的实现

从栈的定义上来看，栈主要包括两个操作，出栈和入栈，也就是在栈顶插入一个数据和栈顶删除一个数据。理解了栈的定义之后，我们来看看如何用代码实现一个栈。

实际上，栈既可以用数组来实现，也可以用链表来实现。用数组来实现的栈，我们叫作顺序栈，用链表实现的栈，我们叫作链式栈。

不管是顺序表还是链式表，我们存储数据只需要一个大小为n的数组就够了。在入栈和出栈过程中，只需要一两个临时变量存储空间，所以空间复杂度是O(1)。

支持动态扩容的顺序栈

基于数组实现的栈，是一个固定大小的栈，也就是说，在初始化栈时需要实现指定栈的大小。当栈满之后，就无法再往栈里添加数据了。尽管链式栈的大小受限，但要存储next指针，内存消耗相对较多。

根据动态扩容的数组，当数组空间不够时，我们就重新申请一块更大的内存，将原来数组汇总数据统统拷贝过去。这样就实现了一个支持动态扩容的数组。

如果要实现一个支持动态扩容的栈，我们只需要底层依赖一个支持动态扩容的数组就可以了。当栈满了以后，我们就申请一个更大的数组，将原来的数据搬移到新数组中。

                           

支持动态扩容的顺序栈的入栈，出栈操作的时间复杂度

入栈：对于入栈而言，最好情况时间复杂度为O(1)，最坏情况时间复杂度时O(n)。对于栈的分析需要从这几点都是可以考虑的。

• 栈空间不够时，我们重新申请一个是原来大小两倍的数组；
• 为了简化分析，假设只有入栈操作没有出栈操作；
• 定义不涉及内存搬移的入栈操作为simple-push操作，时间复杂度为O(1)。

如果当前栈大小为K，并且已满，当再有新的数据要入栈时，就需要重新申请2倍大小的内存，并且做K个数据的搬移操作，然后再入栈。但是，接下来的K-1次入栈操作，我们都不需要再重新申请内存和搬移数据，所以这K-1次入栈操作都需要一个simple-push操作就可以完成。

                            

在K次入栈操作，总共涉及了K个数据的搬移，以及K次simple-push操作。将K个数据搬移均摊到k次入栈操作，那每次入栈操作只需要一个数据搬移和一个simple-push操作。所以均摊时间复杂度一般都等于最好情况时间复杂度。因为在大部分情况下，入栈操作的时间复杂度均为O(1)，只有在个别时刻才会退化为O(n)，所以把耗时多的入栈操作的时间均摊到其他入栈操作上，平均情况下的耗时就接近O(1)。

出栈：对于出栈操作不会涉及内存的重新申请和数据的搬移，所以出栈的时间复杂度仍然是O(1)。但是，对于入栈操作而言，情况就不一样。当栈中空闲空间时，入栈操作的时间复杂度为O(1)。但当空间不够时，就需要重新申请内存和数据搬移，数据搬移时的时间复杂度为O(n)。

三 栈在函数中的应用

在软件工程中的实际应用中，栈作为一个比较基础的数据结构，应用场景还是蛮多的，其中，比较经典的应用场景就是函数调用栈。

操作系统给每个线程分配了一块独立的内存空间，这块内存被组织成"栈"这种结构，用来存储函数调用时的临时变量。每进入一个函数，就会将临时变量作为一个栈帧入栈，当被调用函数执行完成，返回之后，将这个函数对应的栈帧出栈。、

四 栈实现浏览器的前进和后退功能

其实我们可以通过两个栈，X和Y，我们把首次浏览的页面依次压入栈X，当点击后退按钮时，再依次从栈X中出栈，并将出栈的数据依次放入栈Y。当我们点击前进按钮时，我们依次从栈Y中取出数据，放入栈X中。当栈X中没有数据时，那就说明没有页面可以继续后退浏览了，同理，当栈Y中没有数据，那就说明没有页面可以再点击前进按钮浏览了。

比如你顺序查看了 a，b，c 三个页面，我们就依次把 a，b，c 压入栈，这个时候，两个栈的数据就是这个样子：

                       

当你通过浏览器的后退按钮，从页面 c 后退到页面 a 之后，我们就依次把 c 和 b 从栈 X 中弹出，并且依次放入到栈 Y。这个时候，两个栈的数据就是这个样子：

                       

这个时候你又想看页面 b，于是你又点击前进按钮回到 b 页面，我们就把 b 再从栈 Y 中出栈，放入栈 X 中。此时两个栈的数据是这个样子：

                        

这个时候，你通过页面 b 又跳转到新的页面 d 了，页面 c 就无法再通过前进、后退按钮重复查看了，所以需要清空栈 Y。此时两个栈的数据这个样子：

                         

五 栈保存临时变量的原因

再函数调用的过程中，我们不一定非要用栈来保存临时变量，只不过如果这个函数调用符号后进先出的特性，用栈这种数据结构来实现，是顺理成章的选择。

从函数调用进入被调用函数，对于数据来说，变化的是作用域，所以根本上，只要能保证每进入一个新的函数，都是一个新的作用域就可以。而实现这个，用栈就非常方便。在进入被调用函数的时候，分配一段栈空间给这个函数的变量，在函数结束的时候，将栈顶复位，正好回到调用函数的作用域内。

六 内存中堆栈和数据结构中的堆栈

内存中的堆栈和数据结构不是同一个概念，可以说内存中的堆栈是真实存在的物理区，数据结构中的堆栈是抽象的数据存储结构。

JVM里面的栈一般是指虚拟机栈，在每个方法被执行的时候，Java虚拟机都会同步创建一个栈帧用于存储局部变量表，操作数栈，动态连接，方法出口等信息，每个方法被调用直至执行完毕的过程，就对应一个栈帧在虚拟机栈中从入栈到出栈的过程。