什么是栈
栈是一种“操作受限”的线性表，只允许在一端插入和删除数据。
相比数组和链表，栈带给我的只有限制，并没有任何优势。那我直接使用数组或者链表不就好了吗？为什么还要用这个“操作受限”的“栈”呢？
从功能上来说，数组或链表确实可以替代栈，但你要知道，特定的数据结构是对特定场景的抽象，而且，数组或链表暴露了太多的操作接口，操作上的确灵活自由，但使用时就比较不可控，自然也就更容易出错。
当某个数据集合只涉及在一端插入和删除数据，并且满足后进先出、先进后出的特性，这时我们就应该首选“栈”这种数据结构。
栈的几种实现方式
顺序栈
基于数组实现
代码例子
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 }
在入栈和出栈过程中，只需要一两个临时变量存储空间，所以空间复杂度是 O(1)。
这里存储数据需要一个大小为 n 的数组，并不是说空间复杂度就是 O(n)。因为，这 n 个空间是必须的，无法省掉。所以我们说空间复杂度的时候，是指除了原本的数据存储空间外，算法运行还需要额外的存储空间。
链式栈
基于链表实现
支持动态扩容的栈
链式栈天然支持扩容,顺序栈需要动态扩容数组
链式栈缺点就是使用的是链表。需要存储后驱节点指针
顺序栈是基于数组，扩容阶段的时候会拷贝一份到新数组,造成扩容的时候内存占用双份。同事还会预留一些闲置空间
关于栈的应用场景
函数调用栈
