数据结构与算法之美 - 06栈

一、什么是栈？

一种“操作受限”的线性表结构，只支持数据的添加（入栈-push）和删除(出栈-pop)操作，并具备先进后出，后进先出特性。

线性表数据结构.jpg

栈的实现

使用数组、链表都可以实现栈数据结构。数组实现的栈我们称之为顺序栈；链表实现称之为链式栈。

通过栈的概念我们抽象出一个栈最基本的功能接口：

interface Stack<T> {
    //压栈
    boolean push(T item);

    //弹栈
    T pop();

    //是否为空
    boolean isEmpty();

    //栈中数据的数量
    int size();

    //返回栈中最近添加的元素而不删除它
    T peek();
}

1、顺序栈

实现一个存储字符串的顺序栈：

class StringArrayStack implements Stack<String> {

    private int count;
    private String[] items;
    private int maxSize;
    private String curItem;

    public StringArrayStack(int maxSize) {
        this.items = new String[maxSize];
        this.maxSize = maxSize;
    }


    @Override
    public boolean push(String item) {
        if (count == maxSize) return false;    
        items[count] = item;
        ++count;
        curItem = item;
        return true;
    }

    @Override
    public String pop() {
        if (count == 0) return null;
        String item = items[count - 1];
        items[count - 1] = null;
        --count;
        curItem = items[count - 1];
        return item;
    }

    @Override
    public boolean isEmpty() {
        return count == 0;
    }

    @Override
    public int size() {
        return count;
    }

    @Override
    public String peek() {
        return curItem;
    }

    public void printAll() {
        for (int i = 0; i < count; i++) {
            System.out.print(items[i] + "\t");
        }
        System.out.println();
    }
}

测试：

//测试数据
public static StringArrayStack getStackAndData() {
    StringArrayStack stack = new StringArrayStack(10);
    stack.push("1");
    stack.push("2");
    stack.push("3");
    stack.push("4");
    stack.push("5");
    stack.push("6");
    stack.push("7");
    stack.push("8");
    stack.push("9");
    stack.push("10");
    return stack;
}

//测试代码
StringArrayStack stack = getStackAndData();
stack.printAll();
stack.pop();
stack.pop();
stack.peek();
stack.pop();
stack.printAll();

输出：

1    2    3    4    5    6    7    8    9    10    
1    2    3    4    5    6    7

以上是使用数组实现一个固定大小的栈，一般情况下固定大小的栈就满足我们的业务需求，诺需要动态扩容，只需要在内存不足时扩展一个大小大于原先数组的新数组，将旧数组数据copy进新数组（具体的实现可以查看
数组章节ArrayList的原码分析）。

空间复杂度

无论是添加还是删除操作，栈始终操作的是栈顶数据，每一个数据操作只占一个内存空间大小，所以空间复杂度为O(1)

时间复杂度

在支持动态扩容的情况下：

最好情况是数组大小足够时直接添加，所以最好时间复杂度为O(1)；
最坏情况是需要进行动态扩容，那么每个元素都需要进行位移，所以最坏时间复杂度为O(n)；
这里是个典型适合平摊分析法来计算平均时间复杂度场景，当插入n+1元素时，需要将前n个元素全部位移到新的数组中，我们把这n次位移均摊到它们自身的每次进栈操作中，每次的进栈操作时间复杂度依旧是O(1)，所以均摊时间复杂度为O(1).

其实，使用数组实现的栈，其添加和删除操作的时间复杂度和数组是一样。

2、链式栈

这里使用链表实现栈就不写实际的例子了，只要知道每一种数据结构的出现，都表明它在某些特殊领域能发出自己的独特作用。

链表实现的栈在内存方面因为有指针的存在，内存消耗更大，但在某些特殊场景又能为我们带来便利。

因为只需要栈顶添加和删除结点，所以时间复杂度都为O(1)，空间复杂度与顺序栈一样O(1).

二、栈的使用场景

以下列举栈数据结构的使用场景

1、函数调用变量存储栈

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

2、栈在表达式中的使用

当我们通过代码来实现一个表达式求值时（例如：1+2*3+4-5），可以使用两个栈分别来存储数字以及操作符。

思路：

利用两个栈，其中一个用来保存操作数，另一个用来保存运算符。我们从左向右遍历表达式，当遇到数字，我们就直接压入操作数栈；当遇到运算符，就与运算符栈的栈顶元素进行比较，若比运算符栈顶元素优先级高，就将当前运算符压入栈，若比运算符栈顶元素的优先级低或者相同，从运算符栈中取出栈顶运算符，从操作数栈顶取出2个操作数，然后进行计算，把计算完的结果压入操作数栈，继续比较。

3、浏览器的前进后退功能

思路：

利用两个栈，X栈用于存储新打开的页面，Y栈存储后退页面
当点击后退时，将X出栈一个页面，并存入Y栈
当点击前进时，将Y出栈一个页面，并存入X栈
当打开新页面时，入X栈，清空Y栈

三、思考

我们在讲栈的应用时，讲到用函数调用栈来保存临时变量，为什么函数调用要用“栈”来保存临时变量呢？用其他数据结构不行吗？

答：因为函数调用的执行顺序符合后进者先出，先进者后出的特点。比如函数中的局部变量的生命周期的长短是先定义的生命周期长，后定义的生命周期短；还有函数中调用函数也是这样，先开始执行的函数只有等到内部调用的其他函数执行完毕，该函数才能执行结束。
正是由于函数调用的这些特点，根据数据结构是特定应用场景的抽象的原则，我们优先考虑栈结构。

2.我们都知道，JVM 内存管理中有个“堆栈”的概念。栈内存用来存储局部变量和方法调用，堆内存用来存储 Java 中的对象。那 JVM 里面的“栈”跟我们这里说的“栈”是不是一回事呢？如果不是，那它为什么又叫作“栈”呢？

答：JVM里面的栈和我们这里说的是一回事，被称为方法栈。和前面函数调用的作用是一致的，用来存储方法中的局部变量。