栈

什么是栈

栈是一个非常基础的数据结构，它的特点是对保存的数据进行“后进先出”的操作。你可以想象你在刷盘子：先刷好的盘子放在最下面，最后刷完的盘子放在最上面，如果你需要使用盘子，一定会选择最上面的盘子，或者你要下面的盘子，就一定要先将上面的盘子移走。
你可以用下面的图理解栈：

栈.jpg

从栈的操作上来看，栈是一种“操作受限”的线性表，它只允许从栈顶插入和删除数据。
你是否会有和我最初一样的疑惑：我们已经有功能齐全的数组和链表，为什么还要使用这样一个操作被限制的数据结构呢？
确实，数组或者链表可以在功能上替代栈，但是特定的数据结构是对特定场景的抽象，当某个数据集合只设计在一端插入和删除数据，并满足后进先出的特性，我们就应当首选“栈”这种数据结构。而且，数组和链表暴露了太多的操作接口，虽然灵活自由，但是使用容易失控，也就更容易出错。

栈的实现

栈的实现可以由数组或者链表完成，由数组完成的栈被称为“顺序栈”，由链表完成的栈被称为“链式栈”，个人认为使用数组作为栈比较简单，下面给出专栏老师的代码：

// 基于数组实现的顺序栈
public class ArrayStack {
  private String[] items;  // 数组
  private int count;       // 栈中元素个数
  private int n;           //栈的大小

  // 初始化数组，申请一个大小为n的数组空间
  public ArrayStack(int n) {
    this.items = new String[n];
    this.n = n;
    this.count = 0;
  }

  // 入栈操作
  public boolean push(String item) {
    // 数组空间不够了，直接返回false，入栈失败。
    if (count == n) return false;
    // 将item放到下标为count的位置，并且count加一
    items[count] = item;
    ++count;
    return true;
  }
  
  // 出栈操作
  public String pop() {
    // 栈为空，则直接返回null
    if (count == 0) return null;
    // 返回下标为count-1的数组元素，并且栈中元素个数count减一
    String tmp = items[count-1];
    --count;
    return tmp;
  }
}

很容易发现，栈的push操作和pop操作都是O(1)的时间和空间复杂度。

支持动态扩容的顺序栈

如以前我们所讲的，数组的问题在于只能保存固定数据大小的内容，我们当然可以对栈进行扩容，其大致思路是这样的：
当栈未满，正常进行push操作，如果栈满，push操作就会申请一块更大的内存（假定为两倍），将栈内的数据搬运到新的栈中，然后再进行push操作，其过程大致如下：

支持动态扩容的顺序栈.jpg
在上面的过程中，你会发现push操作在不同的情况下会有不同的时间复杂度，要想分析它的时间复杂度，就要使用到之前学习过的摊还分析法：

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

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

如果当前栈大小为 K，并且已满，当再有新的数据要入栈时，就需要重新申请 2 倍大小的内存，并且做 K 个数据的搬移操作，然后再入栈。但是，接下来的 K-1 次入栈操作，我们都不需要再重新申请内存和搬移数据，所以这 K-1 次入栈操作都只需要一个 simple-push 操作就可以完成。为了让你更加直观地理解这个过程，我画了一张图。

摊还分析动态栈的时间复杂度.jpg

经过分析，可以将扩容的时间均摊到之后的入栈操作中，均摊后他们的复杂度为O(1).

栈的应用

栈在函数调用中的应用

在操作系统中，操作系统会为每个线程分配一块独立的内存空间，这块内存就是栈的结构，它用于存储函数调用时的临时变量。每调用一个函数，就会将临时变量作为一个栈帧入栈，调用完成，就将函数对应的栈帧出栈。

栈在表达式求值中的应用

对于计算机来说，了解一个算数表达式是一件很困难的事，那么如何通过栈实现这个功能呢？举个例子，我们希望计算机实现计算 3+5*8-6 ：
我们使用两个栈，一个栈保存操作数，一个栈保存运算符，我们从左到右依次遍历表达式，当遇到数字，就将数字入栈；遇到运算符，则需要和运算符栈的栈顶进行比较：
如果当前运算符比栈顶的运算符的优先级高，则直接入栈；如果比栈顶元素优先级低或者相同，就从运算符栈中取出运算符，从操作数栈中取出 2 个操作数，然后进行计算，然后把计算结果放入数字栈，然后再进行比较。
下面图解这一过程：

用栈做算术.jpg

用栈匹配括号

可以参考leetcode的第20题
解题思路：
我们从左往右依次扫描字符串，使用栈来保存尚未被匹配的左括号，当扫描到左括号就将其入栈，遇到右括号的时候，将栈顶出栈，如果栈顶元素可以匹配左括号，继续扫描。
在扫描过程中遇到不匹配的右括号，或栈中没有数据，或扫描完成后栈仍有数据，则说明格式非法。
下面给出解题代码：

class Solution:
    def isValid(self, s: str) -> bool:
        dic = {')':'(' ,']':'[' ,'}':'{'}
        stack = []
        for i in s:#依次扫描表达式
            if stack and i in dic.keys():#如果扫描到右括号
                ls = stack.pop()#栈顶出栈
                if ls == dic[i]:#如果左右括号匹配，就继续
                    pass
                else:#不匹配：表达式不合法
                    return False
            else:
                #左括号入栈
                stack.append(i)
        return not bool(stack) #如果stack空，则合法，如果不为空，则不合法

思考：你能否使用栈完成浏览器中的“前进”和“后退”功能呢？

---

以上就是关于栈的所有内容

注：本文章的主要内容来自我对极客时间app的《数据结构与算法之美》专栏的总结，我大量引用了其中的代码和截图，如果想要了解具体内容，可以前往极客时间