算法-栈

前言

浏览器的前进、后退功能，我想你肯定很熟悉吧？

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

假如你是浏览器的开发设计者，你会如何实现这个功能呢？带着这个问题，我们来看一下“栈”这个数据结构。

如何理解栈？

关于栈，举一个非常贴切的例子。比如叠盘子，我们放盘子的时候都是从下往上一个一个放。取的时候，我们也是从上往下一个一个取，不能从中间抽取。先进者后出，后进者先出，这就是典型的栈结构。

从栈的操作特性上来看，栈是一种操作受限的线性表，只允许在一端插入和删除数据。

我第一次接触这种数据结构的时候，就对它存在的意义产生了很大的疑惑。因为相比数组和链表，栈带给我的只有限制，并没有任何优势。那我直接使用数组或者链表就好了？为什么还要用这个“操作受限”的数据结构呢？

事实上，从功能上来说，数组和链表确实可以代替栈，但是你要知道，特定的数据结构是对特定场景的抽象，而且数组和链表暴露了太多的操作接口，操作上的确灵活自由，但使用时就比较不可控，自然就更容易出错。

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

如何实现一个栈？

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

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

基于数组实现的顺序栈

我这里用Java实现一个基于数组的顺序栈，基于链表的实现，可以自己写一下。

// 基于数组实现的链式栈
public class ArrayStack<T> implements stack<T> {
    private final Object [] DEFAULT_ARRAY = new Object[10];
    private final int DEFAULT_CAP = 10;
    private Object[] data;
    private int  cap;
    private int size;

    public ArrayStack() {
        this.cap = DEFAULT_CAP;
        this.size = 0;
        this.data = DEFAULT_ARRAY;
    }
    public ArrayStack(int cap){
        if (cap < 0) throw new IllegalArgumentException("Illegal Capacity: "+ cap);
        this.cap = cap;
        this.data = new Object[cap];
    }
    public void push(T val) {
        if (size<cap){
            // 数组满了
            data[size] = val;
            size++;
        }else {
          throw new Runtime("stack is full!")
          // 可以动态扩容的stack
          // Object[] objects = new Object[cap*2];
          // System.arraycopy(data, 0, objects, 0, size);
          // data = objects;
          // data[size] = val;
          // size ++;
        }
    }
    public T pop() {
        if (size == 0) return null;
        T result = (T) data[size-1];
        size--;
        return result;
    }
}

了解了定义和基本操作，那它的操作时间、空间复杂度是多少呢？

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

注意这里存储数据需要一个大小为n的数组，并不是说空间复杂度是O(n)，因为这n个空间是必须的，无法省掉。所以我们说空间复杂度的时候，是指除了原本的数据存储空间外，算法运行还需要额外的存储空间。

时间复杂度分析：不管是入栈、出栈，都只涉及栈顶个别数据的操作，因此时间复杂度为O(1)。

支持动态扩容的顺序栈

刚才那个基于数组实现的顺序栈，是一个固定大小的栈，也就是说，在初始化后需要实现指定栈的大小，当栈满之后，就无法在王栈里添加数据了，尽管链式栈的大小不受限，但是要存储next指针，内存消耗相对较多。那我们如何实现一个可以支持动态扩容的栈呢？

还记得，在数组那一节，要如何来实现一个支持动态扩容的数组吗？当数组空间不足时，我们重新申请一块更大的内存，将原来数组中的数据拷贝过去，这样就实现了一个支持动态扩容的数组。

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

实际上，支持动态扩容的顺序栈，我们开发中并不经常用到。这块我们复习一下复杂度分析方法。现在我们来分析一下支持动态扩容的顺序栈的入栈、出栈时间复杂度。

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

也就是说，对于入栈操作来说，最好时间复杂度为O(1)，最坏情况时间复杂度为O(n)。那平均情况下的时间复杂度是多少呢？还记得时间复杂度分析方法中的摊还分析法吗？这个入栈操作的平均情况的时间按复杂度正好可以用摊还分析法来分析。

为了分析方便，我们先做一些假设和定义：

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

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

从上图看出，这K次入栈操作，总共涉及了K个数据的搬移，以及K次simple-push操作。讲K个数据搬移均摊到K次入栈操作，那每个入栈操作只需要一个数据搬移和一个simpel-push操作。以此类推，入栈操作的时间复杂度为O(1)。

通过这个例子分析，也验证了前面讲的，均摊时间复杂度一般都等于最好时间复杂度。因为在大部分情况下，入栈操作的时间复杂度都是O(1)，只有在个别情况才会退化为O(n)，所以把耗时多的入栈操作的时间均摊到其他入栈操作上，平均情况下耗时就接近O(1)。

栈的应用场景

栈在函数调用中的应用

前面讲的都比较偏理论，我们现在来看，栈在软件工程中的实际应用。栈作为一个比较基础的数据结构，应用场景还是蛮多的。其中比较经典的一个应用场景就是函数调用栈。

我们知道，操作系统给每个线程分配了一块独立的内存空间，这块内存空间被组织成“栈”这种结构，用来存储函数调用时的临时变量。每进入一个函数，就会将临时变量作为一个栈帧入栈，当被调用函数执行完成，返回之后，将这个函数对应的栈帧出栈。为了更好理解函数调用栈，一起来看一下这段代码的执行过程。

int main(){
  int a = 1;
  int ret = 0;
  int res = 0;
  ret = add(3,5);
  res = a + ret;
  printf("%d", res);
  return 0;
}

int add(int x, int y){
  int sum = 0;
  sum = x + y;
  return sum;
}

从代码中我们可以看出，main函数调用了add函数，获取计算结果，并且与临时变量a相加，最后打印res的值，为了清晰的看到这个过程的函数栈里对应的入栈、出栈过程，我这里画了一张函数栈图：

栈在表达式求值中的应用

我们再来看一个栈的常见应用场景，编译器如何利用栈实现表达式求值。

这里我们用一个只包含加减乘除四则运算的表达式来解释，比如：34+13*9+44-12/3。对于这个四则运算，我们人脑可以很快算出来，但是对于计算机来说，理解这个表达式本身就是个挺难的事。如果是你，你会怎么实现一个表达式求值的功能呢？

实际上，编译器就是通过两个栈来实现的。其中一个是保存操作数的栈，另一个保存运算符的栈。我们从左往右遍历表达式，当遇到数字，我们直接压入操作数栈。当遇到运算符，就与运算符的栈顶元素进行比较。如果运算符比当前栈顶元素的优先级高，就直接压入运算符栈中，如果比栈顶元素的优先级低或者相同，就将当前栈顶元素取出，再从操作数栈中取出两个操作数，然后进行运算，再把计算完的结果压入操作数栈，继续比较。

这里用一个简单的例子：3+5*8-6 我将这个表达式的计算过程画成一个图，结合图来理解刚才的计算过程。

栈在括号匹配中的应用

出了用栈来实现表达式求值，我们还可以借助栈来检查表达式中的括号是否匹配。

我们同样简化一下背景，假设表达式只包含三种括号，圆括号()、方括号[]、花括号{}，并且他们可以任意嵌套。比如{[{}]}、[([]){()}]等都为合法格式，而{[}()或[{(}]为非法格式。那现在给你一个包含三种括号的表达式字符串，如何检查它是否合法呢？

这里也可以用栈来解决。我们用栈来保存未匹配的左括号，从做到右一次扫描字符串。当扫描到左括号时，则将其压入栈中，当扫描到右括号时，从栈顶取出一个左括号。如果能够匹配，比如”(“和”)”匹配、”[“和”]”匹配、”{“和”}”匹配，则继续扫描剩下的字符串。如果扫描过程中，遇到不能匹配的右括号，或者栈中没有数据，则说明为非法格式。

当所有的括号都扫描完成后，如果栈为空，则说明字符串为合法格式；否则说明有为匹配的左括号，为非法格式。

解答开篇

好了，理解了栈的概念和应用，再回头看看开篇的问题。如何实现浏览器的前进、后退功能？学过栈之后，就可以用两个栈完美的解决这个问题了。

我们使用两个栈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，此时栈中数据如下：

总结

栈是一种操作受限的数据结构，只支持入栈和出栈操作。后进先出是它的最大特点。栈既可以通过数组来实现，也可以通过链表来实现。不管是数组实现的栈，还是链表实现的栈，他们的入栈、出栈时间复杂度都为O(1)。在基于数组实现的动态扩容的顺序栈中，时间复杂度均为O(1)，重点是入栈时间复杂度中关于摊还分析法的掌握。

思考

1、再讲栈的应用时，讲到用函数调用栈来保存临时变量，为什么函数调用要用”栈”这种数据结构来保存临时变量呢？用其他数据结构可以吗？
2、我们知道，JVM内存管理中有个“堆栈”的概念。栈内存用来白村局部变量和方法调用，堆内存用来存储java中的对象。那JVM里面的“栈”和我们这里的“栈”一样吗？不一样的话，为什么叫“栈”呢？