什么是栈
栈是一种“操作受限”的线性表，只允许在一端插入和删除数据。
相比数组和链表，栈带给我的只有限制，并没有任何优势。那我直接使用数组或者链表不就好了吗？为什么还要用这个“操作受限”的“栈”呢？
从功能上来说，数组或链表确实可以替代栈，但你要知道，特定的数据结构是对特定场景的抽象，而且，数组或链表暴露了太多的操作接口，操作上的确灵活自由，但使用时就比较不可控，自然也就更容易出错。
当某个数据集合只涉及在一端插入和删除数据，并且满足后进先出、先进后出的特性，这时我们就应该首选“栈”这种数据结构。
栈的几种实现方式
顺序栈
基于数组实现
代码例子
1 // 基于数组实现的顺序栈
2 public class ArrayStack {
3 private String[] items; // 数组
4 private int count; // 栈中元素个数
5 private int n; //栈的大小
6
7 // 初始化数组，申请一个大小为n的数组空间
8 public ArrayStack(int n) {
9 this.items = new String[n];
10 this.n = n;
11 this.count = 0;
12 }
13
14 // 入栈操作
15 public boolean push(String item) {
16 // 数组空间不够了，直接返回false，入栈失败。
17 if (count == n) return false;
18 // 将item放到下标为count的位置，并且count加一
19 items[count] = item;
20 ++count;
21 return true;
22 }
23
24 // 出栈操作
25 public String pop() {
26 // 栈为空，则直接返回null
27 if (count == 0) return null;
28 // 返回下标为count-1的数组元素，并且栈中元素个数count减一
29 String tmp = items[count-1];
30 --count;
31 return tmp;
32 }
33 }
View Code
在入栈和出栈过程中，只需要一两个临时变量存储空间，所以空间复杂度是 O(1)。
这里存储数据需要一个大小为 n 的数组，并不是说空间复杂度就是 O(n)。因为，这 n 个空间是必须的，无法省掉。所以我们说空间复杂度的时候，是指除了原本的数据存储空间外，算法运行还需要额外的存储空间。
链式栈
基于链表实现
支持动态扩容的栈
链式栈天然支持扩容,顺序栈需要动态扩容数组
链式栈缺点就是使用的是链表。需要存储后驱节点指针
顺序栈是基于数组，扩容阶段的时候会拷贝一份到新数组,造成扩容的时候内存占用双份。同事还会预留一些闲置空间
关于栈的应用场景
函数调用栈
