数据结构与算法 / 系统课时

栈

栈

栈只通过同一端插入和移除元素,遵循后进先出。上一节的双向链表可以提供端点操作。本课使用 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。

java
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));
        }
    }
}
text
栈顶: 30
出栈: 30
剩余栈: [20, 10]
{[()]} 匹配: true
{[(])} 匹配: false
a * (b + [c - d]) 匹配: true

打印顺序由队首到队尾,[20, 10] 中的 20 是栈顶。算法逐个读取字符串的 UTF-16 代码单元,无需复制整段文本。对长度为 nn 的字符串,最坏总时间为 Θ(n)\Theta(n)。运行中若最多同时有 dd 个未闭合括号,辅助存储量为 O(d+1)O(d+1)。遇到明显不匹配时可以提前返回。

本课练习

分别验证空字符串、单个右括号和缺一个右括号的情况。用两个栈实现撤销与重做,说明撤销后执行新操作时为什么通常要清空重做栈。下一课把两端分工改成一端写入、一端读出。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

栈

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通