数据结构与算法 / 系统课时
栈
栈
栈只通过同一端插入和移除元素,遵循后进先出。上一节的双向链表可以提供端点操作。本课使用 Java 的 ArrayDeque 实现栈,并用它检查括号嵌套。
学习目标
- 分辨压栈、弹栈、查看栈顶和判空。
- 解释空栈的返回或异常,以及扩容对单次成本的影响。
- 用栈维护尚未闭合的括号,验证类型与顺序。
以队首作为栈顶
| Java 操作 | 行为 | 空栈时 |
|---|---|---|
push(value) |
从队首压入 | 插入非空值 |
pop() |
从队首删除并返回 | 抛出 NoSuchElementException |
peek() |
查看队首,不删除 | 返回 null |
isEmpty() |
检查是否为空 | 返回 true |
这里用 Deque 声明栈,使用 ArrayDeque 实现。它不允许存储 null,所以 peek() 返回的 null 可用于识别空栈。数组式实现的压栈通常为摊还常数时间,扩容时单次可能搬移已有元素。查看、判空以及栈顶删除只涉及端点。这里的结构用于单线程操作。 Java Deque 栈接口 Java ArrayDeque 约定与成本
用栈检查括号
从左向右扫描。遇到左括号,把它所需的右括号压栈。遇到右括号,就要与栈顶期待的字符相同并弹出。此时栈顶始终是最近一个尚未闭合的左括号所期待的右括号。扫完后栈必须为空。只数左右括号的总数无法判断顺序,例如 ([)] 数量相同仍不合法。
示例只检查 ASCII 的三种括号,忽略其他字符,包括引号和注释标记。它适合分析普通文本中的括号排列。若要按具体语言忽略字符串或注释里的括号,需要额外的词法规则。空字符串返回 true,null 不作为有效输入。
Java 17 可运行示例
将代码保存为 StackDemo.java。用 JDK 17 或以上执行 javac -encoding UTF-8 --release 17 StackDemo.java,再执行 java StackDemo。
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Objects;
public class StackDemo {
public static boolean isBalanced(String expression) {
Objects.requireNonNull(expression, "expression");
Deque<Character> expected = new ArrayDeque<>();
for (int i = 0; i < expression.length(); i++) {
char current = expression.charAt(i);
switch (current) {
case '(' -> expected.push(')');
case '[' -> expected.push(']');
case '{' -> expected.push('}');
case ')', ']', '}' -> {
if (expected.isEmpty() || expected.pop() != current) {
return false;
}
}
default -> { }
}
}
return expected.isEmpty();
}
public static void main(String[] args) {
Deque<Integer> stack = new ArrayDeque<>();
stack.push(10);
stack.push(20);
stack.push(30);
System.out.println("栈顶: " + stack.peek());
System.out.println("出栈: " + stack.pop());
System.out.println("剩余栈: " + stack);
for (String expression : new String[]{"{[()]}", "{[(])}", "a * (b + [c - d])"}) {
System.out.println(expression + " 匹配: " + isBalanced(expression));
}
}
}栈顶: 30
出栈: 30
剩余栈: [20, 10]
{[()]} 匹配: true
{[(])} 匹配: false
a * (b + [c - d]) 匹配: true打印顺序由队首到队尾,[20, 10] 中的 20 是栈顶。算法逐个读取字符串的 UTF-16 代码单元,无需复制整段文本。对长度为 的字符串,最坏总时间为 。运行中若最多同时有 个未闭合括号,辅助存储量为 。遇到明显不匹配时可以提前返回。
本课练习
分别验证空字符串、单个右括号和缺一个右括号的情况。用两个栈实现撤销与重做,说明撤销后执行新操作时为什么通常要清空重做栈。下一课把两端分工改成一端写入、一端读出。