顺序栈
顺序栈是指利用一组地址连续的存储单元（即数组）依次存放自栈底至栈顶的数据元素。在顺序栈中，我们只需要关注两个物理量：
- 数组 (Array)：用来承载数据的容器。
- 栈顶指针 (top)：本质上是一个索引（Index）。它始终指向当前栈中最新插入的元素位置。
顺序栈利用数组的连续性，剔除了链表节点频繁申请内存的开销。它虽然只能在一端操作，但其极致的读写速度，让它成为了递归调用、表达式求值（如计算器逻辑）以及浏览器后退功能的不二之选。
动态扩容的顺序栈核心代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
|
public class MyArrayStack {
private int[] data;
private int top;
private int capacity;
private static final int DEFAULT_CAPACITY = 10;
public MyArrayStack() {
this(DEFAULT_CAPACITY);
}
public MyArrayStack(int initCapacity) {
this.capacity = initCapacity;
this.data = new int[capacity];
this.top = 0;
}
private void resize(int newCapacity) {
int[] newData = new int[newCapacity];
System.arraycopy(data, 0, newData, 0, top);
data = newData;
capacity = newCapacity;
}
private boolean isEmpty() {
return top == 0;
}
public void push(int val) {
if (top == capacity) {
resize(capacity * 2);
}
data[top++] = val;
}
public int pop() {
if (isEmpty()) throw new EmptyStackException();
int val = data[--top];
if (top > 0 && top == capacity / 4 && capacity / 2 >= DEFAULT_CAPACITY) {
resize(capacity / 2);
}
return val;
}
public int peek() {
if (isEmpty()) throw new EmptyStackException();
return data[top - 1];
}
public int size() {
return top;
}
public void print() {
for (int i = top - 1; i >= 0; i--) {
System.out.print(data[i] + " ");
}
System.out.println();
}
public static void main(String[] args) {
MyArrayStack stack = new MyArrayStack(2);
stack.push(10);
stack.push(20);
stack.push(30);
stack.print();
System.out.println("Pop: " + stack.pop());
System.out.println("Peek: " + stack.peek());
stack.print();
}
}
|
链式栈
在顺序栈统治了高性能计算（如 JVM 虚拟机栈、编译器底层）的天下时，链式栈依然在某些特定领域有着不可替代的地位。它的核心优势在于 “无限增长” 和 “零内存碎片浪费”。以下是链式栈的三个典型实际应用场景：
- 撤销（Undo/Redo）操作的 “无限历史记录”
- 符号表管理：比如实现一个计算器
- 深度优先搜索（DFS）与回溯算法
准备就绪，点击开始
步进间隔:
链式栈小计算器核心代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
|
public class MyStackCalculator {
private static class LinkedStack<T> {
private class Node {
T data;
Node next;
Node(T data) {
this.data = data;
}
}
private Node top;
public void push(T val) {
Node node = new Node(val);
node.next = top;
top = node;
}
public T pop() {
if (top == null) throw new EmptyStackException();
T val = top.data;
top = top.next;
return val;
}
public T peek() {
return (top == null) ? null : top.data;
}
public boolean isEmpty() {
return top == null;
}
}
public int calculate(String exp) {
LinkedStack<Integer> numStack = new LinkedStack<>();
LinkedStack<Character> opStack = new LinkedStack<>();
for (int i = 0; i < exp.length(); i++) {
char c = exp.charAt(i);
if (Character.isDigit(c)) {
int num = 0;
while (i < exp.length() && Character.isDigit(exp.charAt(i))) {
num = num * 10 + (exp.charAt(i) - '0');
i++;
}
i--;
numStack.push(num);
} else if (isOperator(c)) {
while (!opStack.isEmpty() && priority(c) <= priority(opStack.peek())) {
process(numStack, opStack);
}
opStack.push(c);
}
}
while (!opStack.isEmpty()) {
process(numStack, opStack);
}
return numStack.pop();
}
private boolean isOperator(char c) {
return c == '+' || c == '-' || c == '*' || c == '/';
}
private int priority(char op) {
if (op == '*' || op == '/') return 2;
if (op == '+' || op == '-') return 1;
return 0;
}
private void process(LinkedStack<Integer> nums, LinkedStack<Character> ops) {
int b = nums.pop();
int a = nums.pop();
char op = ops.pop();
switch (op) {
case '+': nums.push(a + b); break;
case '-': nums.push(a - b); break;
case '*': nums.push(a * b); break;
case '/': nums.push(a / b); break;
}
}
public static void main(String[] args) {
MyStackCalculator calc = new MyStackCalculator();
String expression = "3 + 5*2-6/2";
System.out.println(calc.calculate(expression));
}
}
|
单调栈
单调栈不是一种新的物理结构，而是一种操作策略。它要求栈内的元素必须保持单调递增或单调递减。以单调递增栈为例，当一个新元素准备入栈时，如果它比栈顶元素小，就必须把栈顶 “踢出来”，直到新元素比栈顶大或者栈空了，它才进去。之所以这样做，是因为单调栈总能以 O(n) 的时间复杂度，找到数组中每个元素左/右边第一个比它大/小的元素。 如果用暴力循环，这需要 O(n^2)。
双端栈
双端栈（也叫双栈）是指两个栈共享同一个数组空间。
- 物理模型：一个长数组，栈 A 从左头开始向右增长，栈 B 从右头开始向左增长。
- 判满条件：当两个栈的栈顶指针 “相遇” 时（topA + 1 == topB），才说明数组真的满了。
如果分别给两个栈开辟数组，可能栈 A 溢出了，栈 B 却还空着大半，这叫 “贫富不均”。双端栈让两个栈互补余缺，极大地提高了内存利用率。应用场景如下：
- 虚拟机/解释器：在某些脚本语言引擎中，一个栈用于存储数据（操作数栈），另一个用于存储函数调用（帧栈）。由于无法预知谁用得多，共享空间是最佳选择。
- 前后端数据分离：在处理某些需要对比两端数据的算法时，用一个数组维护两个增长方向。