栈就像枪的弹匣一样，放入子弹的时候只能从上面一个一个压入，取子弹时也只能从上面一颗颗取。
最先放进出去的子弹只能最后取出，同样的，『先进后出』就是数据结构中的栈了。
栈的应用场景有很多，最常见就是函数调用栈了，程序在执行时，操作系统给每个线程分配了一块独立空间，而这块内存就是用“栈”来组织的。
程序每调用一个函数，意味着一次入栈操作，而入栈的内容为该函数，称为栈帧。函数执行结束返回结果值，代表一次出栈操作。
实现一个栈
栈对外只暴露两个操作接口，分别为栈顶的「插入」和「删除」操作。
而栈既可以用数组实现，也可以用链表实现，前者称为顺序栈，后者称为链式栈。
数组和链表作为两大基础数据结构，成为了复杂数据结构的载体。栈、队列、树、图等结构都可以用数组或链表来表示。
使用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的虚拟机栈、浏览器的前进后退功能等等。