数据结构-栈

栈就像枪的弹匣一样，放入子弹的时候只能从上面一个一个压入，取子弹时也只能从上面一颗颗取。

最先放进出去的子弹只能最后取出，同样的，『先进后出』就是数据结构中的栈了。

栈的应用场景有很多，最常见就是函数调用栈了，程序在执行时，操作系统给每个线程分配了一块独立空间，而这块内存就是用“栈”来组织的。

程序每调用一个函数，意味着一次入栈操作，而入栈的内容为该函数，称为栈帧。函数执行结束返回结果值，代表一次出栈操作。

实现一个栈

栈对外只暴露两个操作接口，分别为栈顶的「插入」和「删除」操作。

而栈既可以用数组实现，也可以用链表实现，前者称为顺序栈，后者称为链式栈。

数组和链表作为两大基础数据结构，成为了复杂数据结构的载体。栈、队列、树、图等结构都可以用数组或链表来表示。

使用Java实现的顺序栈如下：

// 基于数组实现的顺序栈
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;
    return true;
  }
  
  // 出栈操作
  public String pop() {
    // 栈为空，则直接返回null
    if (count == 0) return null;
    // 返回下标为count-1的数组元素
    String tmp = items[--count];
    return tmp;
  }
}

由于栈只能对栈顶进行操作，入栈和出栈的时间复杂度都为O(1)。

这个顺序栈在初始化时指定了大小，所以当栈满时，就不能继续添加数据了。解决方法有两个，一是改为链式栈，二是增加扩容机制。

链式栈虽然支持动态扩容，但每项数据都额外存储了next指针，加大了内存开销。

增加扩容机制其实就是数组的扩容机制，当空间不够时，申请一个新的空间更大的数组，将原数组迁移到新数组。

END

写到一半写不下去了:)，因为栈的内容本身就很精炼，只要知道「先进后出」这个原则就好了。

对于栈，不要停留在它的定义上，我们更多关注它在算法和软件工程中的应用场景。栈的结构是单调的，但运用的思想却是巧妙的。

比如算法中的括号匹配、表达式运算、拼写检查等，还有递归的调用栈、JVM的虚拟机栈、浏览器的前进后退功能等等。