本文首发于 LOGI'S BLOG，由作者转载。
栈 是一种操作受限的线性表，只支持从一端插入和删除。后进先出是它的最大特点。栈既可用数组也可用链表实现，前者叫顺序栈，后者叫链栈，无论哪种，出入栈操作的时间复杂度都是 O(1)。从功能上说，数组和链表都可代替栈，但特定的数据结构是对特定场景的抽象，尽管数组和链表操作灵活，但它们暴露了太多接口，使用时不可控因素增多，自然也就更容易出错。当某个数据集合只涉及在一端插入和删除数据，并且满足后进先出、先进后出的特性时，就应首选栈这种数据结构。
现实生活中的栈
我们平时放盘子的时候，都是从下往上一个一个放；取的时候从上往下一个一个取，不能从中间任意抽出，这种先进后出的结构便是栈。
顺序栈的实现
class ArrayBasedStack {
Object[] items;
int capacity;
int size;
public ArrayBasedStack(int capacity) {
this.items = new Object[capacity];
this.capacity = capacity;
this.size = 0;
}
// 入栈
public void push(Object item) {
// 动态扩容
if (this.capacity == this.size) {
this.capacity = this.capacity << 1;
Object[] newItems = new Object[this.capacity];
System.arraycopy(items, 0, newItems, 0, this.size);
/*
for (int i = 0; i < this.size; i++) {
newItems[i] = this.items[i];
}
*/
this.items = newItems;
}
this.items[this.size++] = item;
}
// 出栈
public Object pop() {
return this.size == 0 ? null : this.items[--this.size];
}
}
链式栈的实现
class SinglyLinkedListBasedStack {
SinglyLinkedListNode head;
int size;
public void push(Object item) {
SinglyLinkedListNode current = new SinglyLinkedListNode(item);
current.next = this.head.next;
this.head.next = current;
this.size++;
}
public Object pop() {
SinglyLinkedListNode current = this.head.next;
if (current != null) {
this.head.next = this.head.next.next;
}
this.size--;
return current;
}
}
class SinglyLinkedListNode {
SinglyLinkedListNode next;
Object item;
public SinglyLinkedListNode(Object item) {
this.item = item;
}
}
出入栈的时空复杂度分析
对于链式栈，push 操作实际上是链表头插，时间复杂度为 O(1)。pop 操作是删除第一个有效节点，时间复杂度同样为 O(1)。两个操作都未使用额外空间，因此空间复杂度为 O(1)。
对于顺序栈，push 操作在链表满时需要数据搬移，时间复杂度 O(n)，空间复杂度 O(n)，这是最坏情况。最好情况是数组未满，直接将 item 放入 size 位置，时空复杂度都是 O(1)。pop 操作直接返回 size-1 位置，时空复杂度都是 O(1)。
我们发现，顺序栈的 push 操作，大多数情况下可在 O(1) 时间完成，只有少数情况需要 O(n) 时间，并且它们之间存在时间先后关系，具体是，每 n-1 次 O(1) 操作跟随 1 次 O(n) 操作。在 算法的时空复杂度分析 这篇文章中，我们介绍过，遇到上述情况，在分析平均复杂度时，应使用摊还分析代替平均加权，得到均摊复杂度，并且通常情况下，均摊复杂度等于最好情况复杂度。本例中，将 n 个数据搬移均摊到 n 次上，相当于一次只需一次搬移，均摊复杂度为 O(1)，这也更符合较长时间的性能测量。
// 顺序栈 push 操作的时间复杂度
// 第一行为次数
// 第二行为每次的时间复杂度
|- n -| 1 |- n-1 -| 1 |- n-1 -|
1,1,...,1,n,1,1,...,1,n,1,1,...,1,...
栈的常规应用
处理函数调用
我们知道，操作系统给每个线程分配了一块独立的内存空间，这块内存空间被组织成栈，用来存储函数调用时的临时变量。每进入一个函数，操作系统便将临时变量作为栈帧入栈，当调用结束返回后，再将该栈帧出栈。通过模拟以下代码的执行过程，可以得到函数调用栈的结构。
int main() {
int a = 1;
int ret = 0;
int res = 0;
ret = add(3, 5);
res = a + ret;
printf("%d", res);
return 0;
}
int add(int x, int y) {
int sum = 0;
sum = x + y;
return sum;
}
下图显示了执行到 add 函数时，函数调用栈的栈帧分布情况。
| · |-----
| · | |
| · |
|sum=0| add
| x=3|
| y=5| |
| · |-----
| · | |
| · |
|res=0| main
|ret=0|
| a=1| |
-----------
为什么函数调用要用 “栈” 来保存临时变量呢？用其他数据结构不行吗？
其实，我们不一定非要用栈来保存临时变量，只不过如果这个函数调用符合后进先出的特性，用栈这种数据结构是最顺理成章的选择。
从调用函数进入被调用函数，对于数据来说，变化的是什么呢？是作用域。所以从根本上，只要能保证每进入一个新的函数，都是一个新的作用域就可以。而要实现它，用栈就非常方便。在进入被调用函数的时候，分配一段栈空间给这个函数的变量，在函数结束的时候，将栈顶复位，正好回到调用函数的作用域内。
浏览器的前进后退
思路：
- 初始化两个栈 X 和 Y，把首次浏览的页面压入 X
- 当点击后退时，依次从 X 出栈，并将其压入 Y 中
- 当点击前进时，依次从 Y 出栈，并将其压入 X 中
- 打开新页面时，应清空前进栈 Y
- 当 X 中无数据时，则说明没有页面可以后退了
- 当 Y 中无数据时，则说明没用页面可以前进了
举例：
- 打开 A，B，C 三个页面，X 和 Y 的栈帧如下
|C| | |
|B| | |
|A| | |
--- ---
X Y
- 点击两次后退，从 C 退 B 再退到 A 页面
| | | |
| | |B|
|A| |C|
--- ---
X Y
- 点击前进，回到 B 页面
| | | |
|B| | |
|A| |C|
--- ---
X Y
- 打开新页面 D，从逻辑上讲，D 时最新页面，不存在更前面的页面了，需要清空 Y
|D| | |
|B| | |
|A| | |
--- ---
X Y
括号匹配
问题：
假设表达式中允许三种括号：圆括号、方括号和大括号。编写一个算法，判断表达式中的各种左括号是否与右括号匹配。例如，输入 2+(3+4)2+{[3]}-8，输出匹配正确；输入 2+(3+4[2)+{[3]}-8，输出匹配错误。
思路：
初始化一个栈，从左到右扫描表达式。扫描到左括号时入栈。扫描到右括号时，栈顶弹出，若能匹配，则继续扫描，否则匹配失败。当表达式扫描结束后，若栈为空，则匹配成功，否则匹配失败。
复杂度：
时间复杂度 O(n)，空间复杂度 O(n)。
实现：
public boolean braceMatching(String expression) {
ArrayBasedStack<Character> stack = new ArrayBasedStack<>(8);
for (int i = 0; i < expression.length(); i++) {
char c = expression.charAt(i);
switch (c) {
case '(':
case '[':
case '{':
stack.push(c);
break;
case ')':
if (stack.pop() != '(') {
return false;
}
break;
case ']':
if (stack.pop() != '[') {
return false;
}
break;
case '}':
if (stack.pop() != '{') {
return false;
}
break;
}
}
if (stack.size != 0) {
return false;
}
return true;
}
算术表达式求值
问题：
输入算术表达式，输出其运算结果。为了简化问题，我们只考虑 +、-、*、/ 四种运算，他们的优先级规则如下：
- 先乘除，后加减
- 从左算到右
- 先括号内，再括号外
算符优先法
思路：
- 设置两个工作栈，一个存储操作数，另一个存储操作符
- 自左向右扫描算术表达式，遇到操作数直接入操作数栈
- 若遇到操作符，则根据算符优先规则决定下一步操作：若优先级高于栈顶操作符则入栈。否则，弹出栈顶算符，并从操作数栈弹出两个操作数计算，将计算结果入操作数栈。继续与栈顶操作符比较优先级，若相等或低于，则再计算，直至大于之，此时方可将操作符入栈
- 左括号一定入栈，且优先级低于后续任何算符，即优先级高于括号前，低于括号中。右括号一定出栈计算，直至遇到左括号，即低于括号中
- 扫描完毕后，由于剩余算符的优先级相同，直接依次出栈计算，结果入操作数栈，当操作符栈空时，计算结束
复杂度：
时间复杂度 O(n)，空间复杂度 O(n)。
实现：
public class StackReview {
public static void main(String[] args) {
String arithmeticExpression = "2-6/(1+3*2-1)+(4+4)*5+1";
System.out.println(arithmeticExpression + " = " + new StackReview().calculate(arithmeticExpression));
}
public double calculate(String arithmeticExpression) {
SinglyLinkedListBasedStack<Double> operands = new SinglyLinkedListBasedStack<>();
SinglyLinkedListBasedStack<Character> operators = new SinglyLinkedListBasedStack<>();
for (int i = 0; i < arithmeticExpression.length(); i++) {
char c = arithmeticExpression.charAt(i);
switch (c) {
case '(':
operators.push(c);
break;
case '+':
case '-':
case '*':
case '/':
while (operators.size > 0 && !this.isGreater(c, operators.getTop())) {
operands.push(calSubExpress(operands.pop(), operands.pop(), operators.pop()));
}
operators.push(c);
break;
case ')':
while (operators.getTop() != '(') {
operands.push(calSubExpress(operands.pop(), operands.pop(), operators.pop()));
}
// '()' 匹配完毕，'(' 出栈
operators.pop();
break;
default:
operands.push((double) (c - '0'));
break;
}
}
// 剩余算符优先级相同，直接依次出栈
while (operators.size > 0) {
operands.push(calSubExpress(operands.pop(), operands.pop(), operators.pop()));
}
return operands.pop();
}
public boolean isGreater(char operator1, char operator2) {
if (operator1 == '/' || operator2 == '(') {
// 自左向右，/ 比 * 优先级高。括号里面必须先算
return true;
} else if (operator1 == '-' && operator2 == '+') {
// 自左向右，- 比 + 优先级高
return true;
} else if (operator1 == '*' && (operator2 == '+' || operator2 == '-')) {
return true;
}
return false;
}
public double calSubExpress(double operand1, double operand2, char operator) {
double result = 0;
switch (operator) {
case '+':
// 第二个数在前，因为它先入栈
result = operand2 + operand1;
break;
case '-':
result = operand2 - operand1;
break;
case '*':
result = operand2 * operand1;
break;
case '/':
result = operand2 / operand1;
break;
}
return result;
}
}
后缀表达式法
步骤：
- 将中缀表达式转为后缀
- 根据后缀表达式求值
后缀的定义：
后缀表达式，指的是不包含括号，运算符放在两个运算对象的后面，所有的计算按运算符出现的顺序，严格从左向右进行（不再考虑运算符的优先规则）。
举例：
- 前缀表达式：操作符在操作数的前面，比如 +-543
- 中缀表达式：操作符在操作数的中间，这也是人类最容易识别的算术表达式 3+4-5
- 后缀表达式：操作符在操作数的后面，比如 34+5-
中缀转后缀：
- 设置两个栈，一个储存算符，另一个储存后缀表达式
- 自左向右扫描中缀表达式，遇到数字直接入后缀表达式栈
- 遇到操作符，比较其与算符栈顶的优先级：
- 若不高于栈顶算符优先级，则栈顶出栈并入后缀表达式栈，继续比较后续栈顶符号，直到遇到低于自己的符号，此时入操作符栈
- 高于栈顶算符优先级，直接入操作符栈
- 左括号直接入操作符栈
- 右括号不入栈，且依次弹出栈内操作符并入后缀表达式栈，直到遇到左括号，将左括号也出栈
- 扫描完毕后，将操作符栈依次弹出并压入后缀表达式栈
- 逆序输出后缀表达式栈
根据后缀表达式求值：
- 设置一个操作数栈
- 从左到右扫描后缀表达式，遇到操作数入栈
- 遇到算符便从栈中弹出两个操作数计算，结果入栈
- 直到算符处理完毕，最后入栈的操作数便是表达式的值
复杂度：
时间复杂度 O(n)，空间复杂度 O(n)。
实现：
public class StackReview {
public static void main(String[] args) {
String arithmeticExpression = "2-6/(1+3*2-1)+(4+4)*5+1";
StackReview stackReview = new StackReview();
StringBuilder suffixExpression = stackReview.InfixToSuffix(arithmeticExpression);
System.out.println(arithmeticExpression + " = " + stackReview.calculateWithSuffixExpression(suffixExpression));
}
public double calculateWithSuffixExpression(StringBuilder suffixExpression) {
ArrayBasedStack<Double> operands = new ArrayBasedStack<>(8);
for (int i = suffixExpression.length() - 1; i >= 0; i--) {
char c = suffixExpression.charAt(i);
switch (c) {
case '+':
case '-':
case '*':
case '/':
operands.push(this.calSubExpress(operands.pop(), operands.pop(), c));
break;
default:
operands.push((double) c - '0');
}
}
return operands.pop();
}
public StringBuilder InfixToSuffix(String arithmeticExpression) {
ArrayBasedStack<Character> operators = new ArrayBasedStack<>(8);
ArrayBasedStack<Character> suffixExpression = new ArrayBasedStack<>(8);
for (int i = 0; i < arithmeticExpression.length(); i++) {
char c = arithmeticExpression.charAt(i);
switch (arithmeticExpression.charAt(i)) {
case '(':
operators.push(c);
break;
case '+':
case '-':
case '*':
case '/':
while (operators.size > 0 && !this.isGreater(c, operators.getTop())) {
suffixExpression.push(operators.pop());
}
operators.push(c);
break;
case ')':
while (operators.size > 0 && operators.getTop() != '(') {
suffixExpression.push(operators.pop());
}
operators.pop();
break;
default:
suffixExpression.push(c);
}
}
while (operators.size > 0) {
suffixExpression.push(operators.pop());
}
StringBuilder expression = new StringBuilder();
while (suffixExpression.size > 0) {
expression.append(suffixExpression.pop());
}
return expression;
}
public boolean isGreater(char operator1, char operator2) {
if (operator1 == '/' || operator2 == '(') {
// 自左向右，/ 比 * 优先级高。括号里面必须先算
return true;
} else if (operator1 == '-' && operator2 == '+') {
// 自左向右，- 比 + 优先级高
return true;
} else if (operator1 == '*' && (operator2 == '+' || operator2 == '-')) {
return true;
}
return false;
}
public double calSubExpress(double operand1, double operand2, char operator) {
double result = 0;
switch (operator) {
case '+':
// 第二个数在前，因为它先入栈
result = operand2 + operand1;
break;
case '-':
result = operand2 - operand1;
break;
case '*':
result = operand2 * operand1;
break;
case '/':
result = operand2 / operand1;
break;
}
return result;
}
}
JVM 中的栈
JVM 的内存结构大概分为：
- 堆（Heap）：线程共享。所有的对象实例以及数组都要在堆上分配。回收器主要管理的对象
- 方法区（Method Area）：线程共享。存储类信息、常量、静态变量、即时编译器编译后的代码
- 方法栈（JVM Stack）：线程私有。存储局部变量表、操作栈、动态链接、方法出口，对象指针
- 本地方法栈（Native Method Stack）：线程私有。为虚拟机使用到的 Native 方法服务。如 Java 使用 c 或者 c++ 编写的接口服务时，代码在此区运行
- 程序计数器（Program Counter Register）：线程私有。有些文章也翻译成 PC 寄存器（PC Register），同一个东西。它可以看作是当前线程所执行的字节码的行号指示器。指向下一条要执行的指令
