Some applications about stack

极客时间版权所有: https://time.geekbang.org/column/article/41222

定义

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

// 基于数组实现的顺序栈
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;
  }
}

复杂度

• 插入 O(1)
• 删除 O(1)

当涉及到动态内存申请，比如利用数组实现到顺序栈，当数组空间不够时，需要重新申请一块更大的内存，同时将原有的数据全部拷贝进去。每次进行 k-1 个插入时间复杂度为O(1)的动作，就需要进行一次需要进行k个数据搬移的插入动作，时间复杂度为O(k)。利用摊还分析的方法，k次插入动作的时间复杂度依然为O(1)。

应用

表达式求值

求 34+13*9+44-12/3

实际上，编译器通过两个栈来实现。其中一个是操作数栈，另外一个是运算符栈。从左到右遍历时， - 遇到数字就直接压入操作数栈； - 遇到运算符就与栈顶的运算符元素进行比较，分为两种情况讨论： - 如果比栈顶运算符的优先级低或者相同，取出栈顶运算符，同时从操作数栈的栈顶取两个操作数，进行计算，然后将结果入栈。 - 如果运算符优先级高，直接入栈。

括号匹配

从左到右依次扫描字符串，用栈来保存没有匹配的左括号。扫描到左括号时，压栈；扫描到右括号时，检查与栈顶的左括号是否匹配，若匹配，左括号出栈，继续扫描，如果不匹配，字符串非法。