1 栈的定义
1.1 什么是栈（Stack）
栈是一种 后进先出（LIFO, Last In First Out） 的线性数据结构。
插入和删除操作都发生在同一端，称为 栈顶（Top）。
另一端称为 栈底（Bottom），保持不动。
1.2 栈的特点
只能在栈顶进行操作。
入栈（Push）：将元素压入栈顶。
出栈（Pop）：将栈顶元素移除。
栈顶指针始终指向最新加入的元素。
结构简单但应用广泛。
1.3 栈的常见实现方式
1.3.1 基于数组实现的顺序栈（Array Stack）
通过数组保存数据。
栈顶索引 top 记录当前栈顶位置。
需要处理扩容问题。
1.3.2 基于链表实现的链式栈（Linked Stack）
栈顶对应链表的头节点。
每次入栈在链表头插入节点。
不需要扩容，灵活性好。
1.4 栈与队列、链表的对比
与队列对比：
栈是 LIFO，队列是 FIFO。与链表对比：
链表支持任意位置插入与删除，栈仅限顶部操作。
2 栈的结构与基本操作
2.1 栈的基本结构（以数组栈为例）
public class ArrayStack {
private int[] data;
private int top;
public ArrayStack(int capacity) {
data = new int[capacity];
top = -1; // -1 表示空栈
}
}
2.2 入栈（Push）操作
判断栈是否已满。
top++，将元素放入 data[top]。
public void push(int value) {
if (top == data.length - 1) {
throw new RuntimeException("栈满");
}
data[++top] = value;
}
2.3 出栈（Pop）操作
判断栈是否为空。
取 data[top]，top--。
public int pop() {
if (top == -1) {
throw new RuntimeException("栈空");
}
return data[top--];
}
2.4 查看栈顶元素（Peek）
public int peek() {
if (top == -1) {
throw new RuntimeException("栈空");
}
return data[top];
}
2.5 判断栈是否为空
public boolean isEmpty() {
return top == -1;
}
2.6 栈的遍历（从栈顶到底部）
public void printStack() {
for (int i = top; i >= 0; i--) {
System.out.println(data[i]);
}
}
3 链式栈（基于链表实现）
3.1 链式栈节点定义
class Node {
int value;
Node next;
Node(int value) {
this.value = value;
}
}
3.2 链式栈结构
public class LinkedStack {
private Node top; // 栈顶节点
public LinkedStack() {
top = null;
}
}
3.3 链式栈的入栈（Push）
新节点指向当前 top。
top 指向新节点。
public void push(int value) {
Node node = new Node(value);
node.next = top;
top = node;
}
3.4 链式栈的出栈（Pop）
public int pop() {
if (top == null) {
throw new RuntimeException("栈空");
}
int result = top.value;
top = top.next;
return result;
}
3.5 查看栈顶元素（Peek）
public int peek() {
if (top == null) {
throw new RuntimeException("栈空");
}
return top.value;
}
3.6 判断是否为空
public boolean isEmpty() {
return top == null;
}
3.7 遍历链式栈
public void printStack() {
Node temp = top;
while (temp != null) {
System.out.println(temp.value);
temp = temp.next;
}
}
4 栈的应用场景
4.1 表达式求值
中缀表达式转后缀表达式
后缀表达式计算
遇到数字 → 直接输出
遇到运算符：
若栈为空 → 入栈
若栈顶运算符优先级大于等于当前运算符 → 栈顶运算符弹出
当前运算符入栈
遇到左括号 → 入栈
遇到右括号 → 弹出直到遇到左括号
扫描结束 → 弹空栈中所有运算符
public static String infixToPostfix(String exp) {
StringBuilder output = new StringBuilder();
Stack<Character> stack = new Stack<>();
for (char ch : exp.toCharArray()) {
if (Character.isDigit(ch)) {
output.append(ch);
} else if (ch == '(') {
stack.push(ch);
} else if (ch == ')') {
while (!stack.isEmpty() && stack.peek() != '(') {
output.append(stack.pop());
}
stack.pop();
} else {
while (!stack.isEmpty() && priority(stack.peek()) >= priority(ch)) {
output.append(stack.pop());
}
stack.push(ch);
}
}
while (!stack.isEmpty()) {
output.append(stack.pop());
}
return output.toString();
}
private static int priority(char op) {
if (op == '+' || op == '-') return 1;
if (op == '*' || op == '/') return 2;
return 0;
}4.2 括号匹配问题
使用栈检查
()[]{}是否匹配遇到左括号入栈
遇到右括号检查栈顶是否匹配
遇到左括号 → 入栈
遇到右括号 → 判断栈顶是否对应：
(对)[对]{对}
若不匹配或栈空 → 表达式非法
扫描结束 → 若栈为空 → 匹配成功
public static boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
for (char ch : s.toCharArray()) {
if (ch == '(' || ch == '[' || ch == '{') {
stack.push(ch);
} else if (ch == ')' || ch == ']' || ch == '}') {
if (stack.isEmpty()) return false;
char top = stack.pop();
if (!match(top, ch)) return false;
}
}
return stack.isEmpty();
}
private static boolean match(char left, char right) {
return (left == '(' && right == ')') ||
(left == '[' && right == ']') ||
(left == '{' && right == '}');
}4.3 函数调用栈
JVM 的栈模型
每次函数调用压栈
函数返回时弹栈
4.4 深度优先搜索（DFS）
使用栈实现非递归 DFS
将根节点压栈
出栈并访问
将其子节点按逆序压栈
重复直到栈空
public void dfs(TreeNode root) {
if (root == null) return;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
System.out.println(node.val);
if (node.right != null) stack.push(node.right);
if (node.left != null) stack.push(node.left);
}
}4.5 浏览器前进后退
后退栈
前进栈
浏览器后退（Back）和前进（Forward）功能就是两个栈的应用。
backStack：记录用户访问历史
forwardStack：记录“前进”历史
用户访问新页面：
把当前页面压入 backStack
forwardStack 清空
用户点击后退：
当前页面压入 forwardStack
backStack 弹出作为当前页面
用户点击前进：
当前页面压入 backStack
forwardStack 弹出作为当前页面
public class Browser {
private Stack<String> backStack = new Stack<>();
private Stack<String> forwardStack = new Stack<>();
private String currentPage = "home";
public void visit(String page) {
backStack.push(currentPage);
currentPage = page;
forwardStack.clear();
}
public void back() {
if (!backStack.isEmpty()) {
forwardStack.push(currentPage);
currentPage = backStack.pop();
}
}
public void forward() {
if (!forwardStack.isEmpty()) {
backStack.push(currentPage);
currentPage = forwardStack.pop();
}
}
}