栈
后进者先出，先进者后出，这就是“栈”结构，支持的最基本操作是入栈push()和出栈pop()。示意图如下：
当某个数据集合只涉及在一端插入和删除数据，并且满足后进先出、先进先出的特性，我们就应该首选“栈”。
栈的实现
用数组实现的栈，叫做顺序栈，用链表实现的栈，叫做链式栈。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;
++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)。
支持动态扩容的顺序栈
上面通过数组实现的栈，是一个固定大小的栈，即栈满之后，无法再添加数据，尽管链式栈的大小不受限，但是要存储next指针，内存消耗也更多。
要实现一个支持动态扩容的栈，只需要底层依赖一个支持动态扩容的数组就可以了。当栈满了之后，我们就申请一个更大的数组，将原来的数据搬移到新数组中，示意图如下：
支持动态扩容的栈，实际上平时开发中并不常用到。出栈的时间复杂度都是O(1)，入栈的时间复杂度最好是o(1)，最坏是O(n)，均摊时间复杂度是O(1)。
均摊时间复杂度一般都等于最好情况时间复杂度。因为在大多数情况下，入栈的时间复杂度都是O(1)，只有在个别时刻才会退化为O(n)，所以把耗时多的入栈操作的时间均摊到其他入栈操作上，平均情况下的耗时就接近O(1)。
栈在函数调用中的应用
操作系统个每个线程分配了一块独立的内存空间，这块内存被组织成“栈”这种结构，用来存储函数调用时的临时变量。
栈在表达式求值中的应用
编译器通过两个栈来实现，其中一个保存操作数的栈，另一个保存运算符的栈。从左到右遍历表达式，遇到数字，就直接压入操作数栈；当遇到运算符，就与运算符栈的栈顶元素优先级进行比较：
- 如果比运算符栈顶元素的优先级高，就将当前运算符压入栈
- 如果比运算符栈顶元素的优先级低，或者相同，从运算符中取栈顶运算符，从操作数栈的栈顶取两个操作数，然后进行计算，再把计算完的结果压入操作数栈，继续比较
栈在括号匹配中的应用
利用栈来检查表达式中的括号是否匹配。用栈来保存未匹配的左括号，从左到右依次扫描字符串，当扫描到左括号时，则将其压入栈中；当扫描到右括号时，从栈顶取出一个左括号，如果能够匹配：
- ”(” 对应 “)”
- ”{” 对应 “}”
- “[” 对应 “]”
则继续扫描剩下的字符串，如果扫描过程中不匹配，或者栈中没有数据，则说明为非法格式。扫描完之后，查看栈是否为空，是空说明字符串合法，反之，不合法。
如何利用实现浏览器的前进和后退功能
利用两个栈，X和Y，把首次浏览的页面依次压入栈X，当点击后退按钮时，再依次从X中出栈，并将出栈的数据压入栈Y。当我们点击前进按钮时，依次从栈Y中取出数据，放入栈X中。当栈X中没有数据时，说明页面不可以继续后退了，当栈Y中没有数据时，说明不能继续前进了。如果没有点击后退按钮，而是进入其他新的页面，那么栈Y的元素需要清空，表示无法通过前进达到栈Y中的页面。
操作系统堆栈 VS 数据结构中的“栈”
内存中的堆栈和数据结构堆栈不是一个概念，可以说内存中的堆栈是真实存在的物理区，数据结构中的堆栈是抽象的数据存储结构。
内存空间在逻辑上分为三部分：代码区、静态数据区和动态数据区，动态数据区又分为栈区和堆区。
- 代码区：存储方法体的二进制代码。高级调度（作业调度）、中级调度（内存调度）、低级调度（进程调度）控制代码区执行代码的切换
- 静态数据区：存储全局变量、静态变量、常量，常量包括final修饰的常量和String常量。系统自动分配和回收
- 栈区：存储运行方法的形参、局部变量、返回值。由系统自动分配和回收
- 堆区：new一个对象的引用或地址存储在栈区，指向该对象存储在堆区中的真实数据
注：本文是《数据结构与算法之美》的读书笔记，配套代码地址GitHub。本文仅限个人学习，请勿用作商业用途，谢谢。
Note: Cover Picture