什么是栈
符合后进先出，先进后出的数据结构成为栈。栈在表达式计算，括号匹配，浏览器的“前进”“后退”等场景下都能起到很好的应用效果。
如何写一个栈
栈可以用过数据或者链表来实现，用数组实现的栈，我们叫作顺序栈，用链表实现的栈，我们叫作链式栈。
如下是通过数据实现栈的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).
栈在表达式求值中的应用
表达式求值中，可以使用两个栈，一个用来保存操作数，一个用于保存运算符。编译器从左往右遍历表达式，当遇到操作数时，直接将操作数入操作数栈。当遇到运算符时，将运算符入操作符栈，在入栈时需要满足以下规则：
- 当运算符优先级比栈顶操作符优先级高，就直接将当前运算符入栈；
-
当运算符优先级比栈顶操作符优先级低或者相等，取出栈顶运算符，并从操作数栈中取出两个操作数进行计算，然后将计算结果入栈操作数栈，然后继续比较栈顶运算符优先级。
表达式求值.jpg
栈在括号匹配中的应用
在括号匹配中，使用栈也可以起到很好的效果。从左往右遍历表达式，当遇到左括号时入栈，当遇到右括号时取出栈顶括号进行匹配，如果匹配则继续扫描。当遇到右括号没有匹配的左括号，或者栈中没有元素可以匹配时，则说明格式非法。
完成遍历时，如果栈为空，则认为表达式括号是匹配的，否则表达式非法。
区分内存中的堆栈和数据结构中的堆栈
内存中的堆栈，是真实的物理内存区；
数据结构中的堆栈，是抽象的数据存储结构；
内存中的堆栈分为：代码区，静态数据区，动态数据区。动态数据区又分为堆区和栈区。
代码区：存储方法体中的二进制代码。高级调度（作业调度）、中级调度（内存调度）、低级调度（进程调度）控制代码区执行代码的切换。
静态数据区：存储全局变量、静态变量、常量，常量包括final修饰的常量和String常量。系统自动分配和回收。
栈区：存储运行方法的形参、局部变量、返回值。由系统自动分配和回收。
堆区：new一个对象的引用或地址存储在栈区，指向该对象存储在堆区中的真实数据。
