Stack

一、OverView

快速预览：

• 🐷：第一小节看一下栈的特性，为什么会有这种受限的数据结构的出现？
• 🐢：第二小节看一下要实现一个栈，最基本需要什么操作？
• 🐭：第三小节看一下栈的的应用，是不是这些应用驱动着栈的诞生
• 🐦：最后一个小节还是老套路，简单的看一下 Java 中关于栈的 API

二、特性

​ 在前面已经介绍了数组和链表两种最基本的数据结构，可以说他俩就是整个数据结构与算法的基石。看一下栈的组成：

那么它和其他线性表最大的区别在哪呢？毫无疑问：它只允许在一端进行插入和删除

或者说成 先进后出、后进先出

此时，小朋友，你是否有很多问号？为什么要有这种受限的数据结构，我用数组和链表不香吗？当然栈就是基于数组或链表实现的，但是在特定的需求下，栈就应用而生了。具体可以参考下面的栈的应用和 Java 中栈，就可以看到在某些情况下栈的优势、以及由于数组和链表暴露出太多的接口，而栈只需要其中的一小部分就可以了

三、实现栈

我们在上面就提到了，栈既可以基于数组实现，也可以基于链表实现。栈最重要的两个操作：入栈 和 出栈

3.1 定容栈

这是《算法》中文版中的译名，顾名思义就是容量固定的栈，基于数组并用 Java 代码来实现一下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

public class FixedCapacityStackOfString {

    private String[] items;
    private int count;
    private int n;

    public FixedCapacityStackOfString(int n) {
        this.items = new String[n];
        this.count = 0;
        this.n = n;
    }

    // 入栈
    private boolean push(String item) {
        if (count == n) return false;
        items[count] = item;
        count++;
        return true;
    }

    // 出栈
    private String pop() {
        if (count == 0) return null;
        String item = items[count - 1];
        count--;
        return item;
    }
}

时间复杂度：O(1)

空间复杂度：O(1) 不包含该栈本身，操作时的空间复杂度

3.2 扩容栈

在上面的定容栈中，是用一个固定大小的数组当成实现栈的结构，那么应该如何实现一个扩容栈呢？

其实也很好实现，回忆一下动态数组的事项，是将数组进行扩容，然后将原来的数据 copy 进去就行了；那么用同样的方式对基于数组的栈进行扩容 (当然基于链表实现的栈就没有这一概念，理论上只要内存空间足够大，栈可以无限大)

• 当栈满的时候，进行扩容：新建一个比现在大的数组
• 将原来栈中的数据全部复制到新的数组中

具体实现可以参考下面的第五小节

四、栈的应用

4.1 撤销操作

​ 如果你经常使用 command + Z 或者 ctrl + Z，你可能会非常理解这个操作：当我们复制或者修改了一个文件，我们想把它恢复成复制或修改之前的一样的状态，只需要按上面的快捷键就行了，仔细想一下是否有栈的影子在里面

就如同上面这个例子：我们写到了 wangba，随后又不想要 wangba 了，此时进行撤销操作，只需要将栈中的 wangba pop 就可以了，有的还有前进功能，此时只需要将其 push 进来即可

4.2 函数调用

​ 如果了解过操作系统或者听说过函数调用，那么可以更容易理解下面的内容，在计算机中，操作系统会给每个线程分配一个内存空间，而这个内存空间就是栈式结构，专门为函数调用存储临时变量，就例如下面的例子：

1
2
3
4
5
6
7
8
9

public static void main(String[] args){
    int a = 1, b = 2;
      int res = add(a, b);
    System.out.println(res);
}

private static Integer add(int x, int y) {
    return x + y;
}

在上面这段 Java 代码中，可以看见在 main 中调用了 add 函数，在栈帧中应该就是这样：

当然，真实情况不是这样的，要是这么简单，计算机底层就不会这么劝退了 ～～～

如果有兴趣了解更深可以参考：《深入理解计算机系统》或者想大概了解一下可以参考 这个

4.3 表达式求值

🐢：在编译器中是如何对表达式进行求值的呢？如果是后缀表达式就只需要一个操作栈即可；如果是前缀或中缀表达式则需要一个操作数栈和一个操作符栈，来看一下中缀表达式的求值过程：

a * (b + c)

过程大概如下：

• 遇到操作数就压到操作数的栈；遇到操作符就压到操作符的栈
• 在压到操作符的栈是有条件的：如果操作符栈顶的符号的优先级大于等于要压入的符号，那就取操作数栈顶的两个数进行计算；如果小于则直接把操作符压入操作符的栈

4.4 括号匹配

关于括号匹配可以参考 LeetCode 0020，关于这题的解答可以看 0020. Valid Parentheses

五、Java中的栈

首先看一下继承与实现的关系：

再看一下该类中的 Structure :

可以看出来很简单，就如同上面在定容栈中的操作差不多，实际上差的很多，要考虑到扩容、并发等等情况，操作大都是在他的父类 Vertor 中完成，如果你看过面经啥的，你应该就听过并发不要使用 Vertor，要多使用 JUC 包下面的类，然后究其原因就是：Vertor 使用 synchronized 关键字，JUC 包下的是使用 ReentrantLock，而可重入锁的底层则是 AQS

LeetCode 重点关于栈的重点：Monotonic Stack