第 3.1 章栈和队列

Stack and Queue

栈和队列引入

两个场景都在处理“等待中的一串对象”，但离开顺序完全不同。

函数 A 调用 B，B 又调用 C。当 C 结束时，程序应该先回到谁？不是最早进入的 A，而是最后进入的 B。

再看打印机：三份文档依次进入打印队列。若没有特殊优先级，最自然的规则却是第一份先打印。

同样都是“等待处理的一串对象”，为什么一个需要后进先出（Last In, First Out，LIFO），另一个需要先进先出（First In, First Out，FIFO）？

两种端点规则，到处都在出现

这种差异不是函数和打印机的偶然现象：

浏览器返回：最后访问的页面最先返回
表达式求值：运算符栈控制运算顺序
广度优先搜索（Breadth-First Search，BFS）：先发现的顶点先扩展，才能保证按层推进
智能体运行时：待执行的工具调用和任务常通过队列管理；需要回溯或深度优先搜索时则会显式使用栈

这些场景共同说明：限制插入和删除的位置，反而能得到非常强的语义。

栈把操作限制在同一端，得到后进先出；队列把插入和删除分离到两端，得到先进先出。

学习目标

掌握栈的抽象数据类型（Abstract Data Type，ADT）、数组栈（array stack）和链式栈（linked stack）
理解双栈共享数组的空间优化
理解单种括号只需计数，而多种括号还必须保存类型与打开顺序，并据此使用栈完成匹配
掌握队列的抽象数据类型、循环队列（circular queue）和链式队列（linked queue）
使用队列生成杨辉三角并完成网格最短路径标号
能够分析栈与队列应用的时间复杂度和空间复杂度

本章路线图

栈与队列
受限线性表

端点约束
后进先出 / 先进先出为什么有用栈抽象
入栈 / 出栈 · 数组与链式实现栈的应用
括号匹配 · 表达式求值队列抽象
入队 / 出队 · 首尾语义循环与链式队列
空间复用 · O(1) 端点操作队列的应用
杨辉三角 · 网格广度优先搜索

端点规则

运行时性能：为什么端点操作重要

栈和队列的高效来自“只在端点操作”。

数组栈的入栈/出栈只移动栈顶边界，内存连续，缓存局部性较好
链式栈避免扩容搬迁，但每个结点有指针和动态分配开销
循环队列用数组复用空间，适合操作系统缓冲区和生产者消费者模型
链式队列删除队头、插入队尾稳定为 $O(1)$，但结点分散会增加缓存未命中

操作系统中的等待队列、输入/输出缓冲区和事件循环都依赖这种“受限操作换取可预测成本”的思想。

栈

栈模型

栈抽象数据类型

操作	含义
`create()`	创建空栈
`empty()`	判断栈是否为空
`full()`	判断栈是否已满
`push(x)`	把 `x` 压入栈顶
`top()`	读取栈顶元素
`pop()`	删除栈顶元素
`topAndPop()`	读取并删除栈顶元素

栈的核心约束是：只能从栈顶观察和修改。

链式栈

链式栈把单链表头部作为栈顶；入栈和出栈都只改表头附近的指针。

空栈条件是 topOfStack == null。

链式栈代码 1：结构与入栈

static class LinkedStack<T> {
  private Node<T> top;
  private int size;

  void push(T value) {
    top = new Node<>(value, top);
    size++;
  }

  T pop() {
    if (top == null) {
      throw new NoSuchElementException("stack is empty");
    }
    T value = top.data;
    top = top.next;
    size--;
    return value;
  }

  T peek() {
    if (top == null) {
      throw new NoSuchElementException("stack is empty");
    }
    return top.data;
  }

  boolean isEmpty() {
    return size == 0;
  }

  int size() {
    return size;
  }
}

LinkedStack 用 top 指向唯一栈顶，链上的先后关系就是后进先出次序。

top 始终指向最近压入且尚未弹出的结点，size 与可达结点数同步；这两个状态共同定义栈。

push(…) 的契约是把新元素变成唯一栈顶，同时保持已有元素的后进先出相对次序。

入栈只把新结点接到旧 top 前面，再更新入口；已有结点不移动，因此是 O(1)。

pop(…) 必须返回并移除当前栈顶；空栈时没有合法结果，不能继续修改结构。

出栈先拒绝空栈，再保存栈顶值并把 top 推向后继；删除的永远是最后压入的元素，保持后进先出。

peek(…) 只读取当前栈顶而不改变任何链接、下标或元素个数。

peek 与 pop 共享同一空栈边界，但只读取 top.data，不会改变任何结构状态。

isEmpty(…) 只判断当前逻辑元素数是否为 0，不需要遍历或改变结构。

空栈等价于逻辑长度为 0；维护 size 让这个判断无需遍历链表。

size(…) 只报告当前逻辑规模，不应触发结构遍历或修改。

对外返回的长度就是当前有效节点数；链式容量不预先固定，长度与可用内存是两个不同概念。

链式栈代码 2：读取与出栈

T peek() {
  if (top == null) {
    throw new NoSuchElementException("stack is empty");
  }
  return top.data;
}

peek(…) 只读取当前栈顶而不改变任何链接、下标或元素个数。

读取栈顶之前必须排除空栈；否则“最近一次尚未弹出的元素”根本不存在。

top 已经直接指向答案，读取数据即可；不改链接也不改长度，所以 peek 是稳定的 O(1)。

数组栈

数组栈把连续数组的一段作为有效栈区，topOfStack 指向当前栈顶下标。

空栈条件是 $topOfStack=-1$；满栈条件是 $topOfStack=capacity-1$。push/pop 不搬动已有元素，只移动栈顶边界。

数组栈代码 1：状态与入栈

static class ArrayStack {
  private final String[] data;
  private int size;

  ArrayStack(int capacity) {
    data = new String[capacity];
  }

  void push(String value) {
    if (size == data.length) {
      throw new IllegalStateException("stack is full");
    }
    data[size++] = value;
  }

  String pop() {
    if (isEmpty()) {
      throw new NoSuchElementException("stack is empty");
    }
    int topIndex = --size;
    String value = data[topIndex];
    data[topIndex] = null;
    return value;
  }

  boolean isEmpty() {
    return size == 0;
  }
}

ArrayStack 用连续数组保存栈元素；数组下标给出物理位置，后进先出次序由 size 的边界维护。

有效元素始终占据 data[0..size)，因此非空时 size-1 就是唯一栈顶。

构造器只创建给定容量的数组；新对象的 size=0，所以一开始没有有效栈元素。

push 在满栈时拒绝写入，否则把新值放到第一个空槽 data[size] 并扩大有效前缀，整个操作是 O(1)。

pop 先缩短有效前缀，再取出原栈顶并清掉旧引用；其余元素不移动，因此仍是 O(1)。

isEmpty 只检查逻辑长度是否为 0；底层数组即使已经分配，也不代表栈里有元素。

数组栈代码 2：出栈与成员变量

String pop() {
  if (isEmpty()) {
    throw new NoSuchElementException("stack is empty");
  }
  int topIndex = --size;
  String value = data[topIndex];
  data[topIndex] = null;
  return value;
}

pop(…) 必须返回并移除当前栈顶；空栈时没有合法结果，不能继续修改结构。

空栈时没有合法栈顶；先拒绝操作，才能保证后续的 –size 仍指向一个真实元素。

先缩短有效前缀得到原栈顶下标，再保存值并清掉旧引用；逻辑删除与内存引用释放都在常数时间完成。

两个栈共享一个数组

括号匹配

哪些括号写法是对的？

观察下面几个字符串。哪些是正确的括号写法？判断时，你在关注什么？

括号匹配：一个计数器足够

static boolean balancedParentheses(String expression) {
  Objects.requireNonNull(expression, "expression");
  int balance = 0;
  for (int i = 0; i < expression.length(); i++) {
    char ch = expression.charAt(i);
    if (ch == '(') {
      balance++;
    } else if (ch == ')') {
      if (balance == 0) {
        return false;
      }
      balance--;
    }
  }
  return balance == 0;
}

balancedParentheses(…) 判断整个圆括号串是否合法；状态只需记录当前尚未闭合的左括号数量。

balance 只表示当前前缀还有多少个左括号没闭合；一种括号没有类型差异，因此不需要保存每一层的具体身份。

遇到左括号只增加欠账数量；扫描到任意位置时，balance 都等于“已打开但尚未关闭”的圆括号个数。

右括号到来时若 balance==0，当前前缀已经先关闭了不存在的左括号，后续字符无法修复；否则正常抵消一层。

扫描结束还要检查欠账是否全部结清；因此单种括号判真伪只需 O(1) 辅助空间。

三种括号：分别计数够吗？

圆括号、方括号、花括号各自维护一个计数器，看起来很自然：每一类都不欠括号，整个字符串是否就一定正确？

计数器缺少了什么？

([)] 和 ([]) 的每类括号数量都相同，为什么只有一个正确？把对应的左、右括号连接起来，观察它们的闭合关系。

三种括号：栈保存待关闭顺序

扫描 {[()]}：每读到一个字符，栈里应该留下哪些左括号？当前内层闭合以后，外层如何重新成为栈顶？

交叉关闭：栈顶立即暴露冲突

扫描 ([)]：错误出现在哪个位置？栈中有同类型的左括号，就一定能配对吗？

三种括号：最终代码

static boolean balancedBrackets(String expression) {
  Objects.requireNonNull(expression, "expression");
  LinkedStack<Character> stack = new LinkedStack<>();
  for (int i = 0; i < expression.length(); i++) {
    char ch = expression.charAt(i);
    if (ch == '(' || ch == '[' || ch == '{') {
      stack.push(ch);
    } else if (ch == ')' || ch == ']' || ch == '}') {
      if (stack.isEmpty()) {
        return false;
      }
      char open = stack.pop();
      if ((ch == ')' && open != '(')
          || (ch == ']' && open != '[')
          || (ch == '}' && open != '{')) {
        return false;
      }
    }
  }
  return stack.isEmpty();
}

balancedBrackets(…) 判断三类括号是否按类型和嵌套顺序匹配；待关闭左括号必须按后进先出顺序保存。

使用自定义的 LinkedStack，保存当前所有尚未关闭的左括号；栈内容就是扫描前缀仍需记住的全部上下文。

左括号出现时还不能确定何时关闭，只能按出现顺序压栈；嵌套越深，待关闭序列就越长。

右括号到来时，空栈表示没有任何可关闭结构；否则只弹出最近打开的左括号，不允许跳过栈顶。

弹出的类型必须与当前右括号对应；这个检查正是三个独立计数器无法表达的“类型顺序”约束。

所有字符处理完后还要求栈为空；每个括号最多入栈或出栈一次，因此时间 O(n)，最坏辅助空间 O(n)。

四个括号任务：复杂度分别是多少？

1. 只有圆括号：判断是否完全匹配。
时间 $\Theta(n)$，辅助空间 $\Theta(1)$。一个 balance 计数器就能保存全部必要状态。

2. 只有圆括号：输出所有未匹配左、右括号的位置。
时间 $\Theta(n)$。输出规模最坏为 $\Theta(n)$；若要在单趟扫描中保留这些位置，最坏还需要 $O(n)$ 额外存储。

3. 三种括号混合：判断是否完全匹配。
时间 $\Theta(n)$，辅助空间 $\Theta(n)$。除了数量，还必须保存尚未关闭括号的类型和顺序。

4. 三种括号混合：输出所有未匹配左、右括号的位置。
时间 $\Theta(n)$，辅助空间 $\Theta(n)$。栈中还要保存对应的位置，才能在发现冲突或扫描结束后报告它们。

四题的时间下界都是 $\Omega(n)$：最坏情况下，最后一个字符就能改变答案。第 2、4 题的输出规模本身最坏也是 $\Theta(n)$。

正则表达式（regular expression）：用模式描述字符串集合

这里讨论形式语言中的普通正则表达式。工程正则表达式引擎可能提供更多扩展；经典正则表达式由有限几种组合规则构成。

字面字符：a；特殊字符要转义，如 \(。
连接：ab 表示 a 后面紧跟 b。
选择：a|b 表示二选一。
重复：a* 为 0 次或更多，a+ 为 1 次或更多，a? 为 0 或 1 次。
分组：(ab|cd)* 把子表达式作为一个整体参与重复。
字符类/边界：[0-9] 表示一个数字；^...$ 常用于约束整串。

例如，ab*c 可以匹配 ac、abc、abbc；(cat|dog)s? 可以匹配 cat、dog、cats、dogs；$[0-9]+$ 可以匹配 (7)、(123)，但这里只描述一对字面圆括号。

关键直觉： 普通正则表达式可以转成有限自动机。状态数固定，因此它没有一个会随着输入嵌套深度不断增长的记忆区。

正则表达式能匹配所有合法括号串吗？

有限深度的例子可以直接写成固定模式：

() → 
()() → 
(()()) → $\($\)

甚至固定最大嵌套深度 $K$ 也能做到：

最多 1 层可以写成 ()*；
最多 2 层可以继续展开成 ($(\($)*\))*；
对任意一个事先给定的 $K$，都可以继续有限次展开。

无法支持任意层嵌套：左括号可能有 1000 层、10000 层，正则表达式不可能把所有深度逐一写完。

结论： 任意深度的括号匹配需要无界记忆。只有一种括号、只判断真伪时，一个可无限增长的计数器就够；多种括号混合时，还必须记住类型顺序，因此自然使用栈 / 下推自动机（pushdown automaton）。支持“递归模式”的工程正则表达式引擎已经超出了这里所说的经典正则表达式能力。

表达式求值

编译器和计算器常把中缀表达式（infix expression）转成后缀表达式（postfix expression），再求值。

中缀表达式	后缀表达式
`AB-CD#`	`ABCD-#`
`(A+B)((C-D)E+F)#`	`AB+CD-EF+#`

后缀表达式没有括号，操作数次序不变，运算符出现的次序就是执行次序。

后缀表达式求值

中缀：$2 * 3 - 4 * 5$ 后缀：$2 3 * 4 5 * -$

后缀表达式求值代码

static double evalPostfix(List<Token> tokens) {
  LinkedStack<Double> stack = new LinkedStack<>();
  for (Token token : tokens) {
    if (token.type() == TokenType.NUMBER) {
      stack.push(token.value());
      continue;
    }
    if (stack.size() < 2) {
      throw new IllegalArgumentException("not enough operands");
    }
    double right = stack.pop();
    double left = stack.pop();
    stack.push(apply(token.type(), left, right));
  }
  if (stack.size() != 1) {
    throw new IllegalArgumentException("postfix expression is incomplete");
  }
  return stack.pop();
}

private static double apply(TokenType type, double left, double right) {
  return switch (type) {
    case PLUS -> left + right;
    case MINUS -> left - right;
    case TIMES -> left * right;
    case DIVIDE -> {
      if (right == 0.0) {
        throw new ArithmeticException("division by zero");
      }
      yield left / right;
    }
    case NUMBER -> throw new IllegalArgumentException("NUMBER is not an operator");
  };
}

evalPostfix(…) 从左到右计算后缀表达式；操作数压栈，运算符只消费最近的两个未使用结果。

数字记号（token）直接入栈；栈因此始终保存“已经算出、但还没有被后续运算符合并”的局部结果。

二元运算符必须已有两个局部结果；先弹出 right、再弹出 left，减法和除法的次序绝不能交换。

把当前运算结果重新压栈，相当于用一个值替代两个操作数和一个运算符；每次折叠都让未完成表达式更小。

全部记号处理完后必须恰好只剩一个值；多余或不足都说明输入并不是完整的后缀表达式。

apply(…) 只负责把一个运算符作用到两个操作数，并返回这一步的局部计算结果。

apply 只负责普通运算符的数学语义，栈管理留在外层；两部分因此可以独立验证。

除法还必须拒绝零除数，NUMBER 也不能进入运算符分支；这些检查保证每次折叠都有定义。

中缀转后缀

中缀转后缀规则

当前字符	动作
操作数	直接输出
`(`	入运算符栈
`)`	弹出并输出，直到遇到 `(`
运算符	弹出优先级不低于当前运算符的栈顶，再把当前运算符入栈
结束符 `#`	弹出并输出剩余运算符

该算法同样是线性时间。

队列

队列模型

队列是只允许在一端插入、另一端删除的线性表。

端点	操作
`rear`	新元素入队
`front`	旧元素出队

队列也称先进先出结构。

队列抽象数据类型

操作	含义
`create()`	创建空队列
`empty()`	判断是否为空
`full()`	判断是否已满
`front()`	读取队头
`back()`	读取队尾
`enqueue(x)`	在队尾加入 `x`
`dequeue()`	删除并返回队头

普通数组队列的问题

若每次出队都把元素整体左移，出队是 $O(n)$。

若只移动 front，前面会出现空洞。

循环数组的目标是复用这些空洞。

循环队列

循环队列：空、满与越界

边界检查必须发生在任何数组读写和下标推进之前。非法的入队或出队操作不应改变队列状态。

循环队列代码

static class CircularQueue {
  private final String[] data;
  private int front;
  private int size;

  CircularQueue(int capacity) {
    data = new String[capacity];
  }

  boolean offer(String value) {
    if (size == data.length) {
      return false;
    }
    int rear = (front + size) % data.length;
    data[rear] = value;
    size++;
    return true;
  }

  String poll() {
    if (size == 0) {
      throw new NoSuchElementException("queue is empty");
    }
    String value = data[front];
    data[front] = null;
    front = (front + 1) % data.length;
    size--;
    return value;
  }
}

CircularQueue 用数组保存物理槽位，用 front 和 size 描述逻辑队列。

front 指向当前队头，size 给出有效元素数；其余逻辑位置通过取模绕回数组开头。

构造器只创建固定容量的数组；初始 front=0,size=0，因此队列为空。

offer 用 (front+size)%capacity 找到队尾后的空槽；满队列直接拒绝，成功入队只写一个槽并增加 size，所以是 O(1)。

poll 取出 front，清掉旧槽，再按取模推进队头并减小 size；其余元素完全不搬动。

另一种约定：只保存队尾下标和队列长度

下面切换到教材习题常见的另一种记号：这里 rear 指最后一个有效元素的下标，不再表示上面代码中的“下一次写入位置”。若数组长度为 $m$，保存队尾下标 rear 和队列长度 length，队头位置为：

\[ front=(rear-length+1+m)\bmod m \]

队空条件：

\[ length=0 \]

队满条件：

\[ length=m \]

链式队列

队头删除，队尾插入。

链式队列代码

static class LinkedQueue<T> {
  private Node<T> front;
  private Node<T> rear;
  private int size;

  void offer(T value) {
    Objects.requireNonNull(value, "value");
    Node<T> node = new Node<>(value, null);
    if (rear == null) {
      front = node;
    } else {
      rear.next = node;
    }
    rear = node;
    size++;
  }

  T poll() {
    if (front == null) {
      throw new NoSuchElementException("queue is empty");
    }
    T value = front.data;
    front = front.next;
    size--;
    if (front == null) {
      rear = null;
    }
    return value;
  }

  boolean isEmpty() {
    return size == 0;
  }
}

LinkedQueue 同时维护队头和队尾，使入队与出队都只改常数个链接。

front 指向下一次出队位置，rear 指向最后一个节点；空队列时两者必须同时为 null。

offer(…) 只在队尾加入新元素；已有元素的先进先出次序不能改变。

入队只在尾部接一个新结点；空队列要同时建立 front，非空时只改旧尾的 next，因此都是 O(1)。

poll(…) 返回并移除队头元素；其余元素仍保持原来的先进先出次序。

出队推进 front；若删掉最后一个节点，还必须把 rear 一并清空，否则会留下指向已移除节点的尾指针。

isEmpty(…) 只判断当前逻辑元素数是否为 0，不需要遍历或改变结构。

维护 size 让空判断保持常数时间，也作为两端引用是否应同时为空的逻辑校验。

队列应用

队列应用一：杨辉三角

杨辉三角的前五行是：

\[\begin{array}{ccccccccc} &&&&1\\ &&&1&&1\\ &&1&&2&&1\\ &1&&3&&3&&1\\ 1&&4&&6&&4&&1 \end{array}\]

两侧永远是 $1$；中间每个数都等于上一行相邻两个数之和。

例如第 5 行中的 $4,6,4$ 来自：

$1+3=4,\qquad 3+3=6,\qquad 3+1=4$

怎么只用上一行生成下一行

生成下一行时，我们其实只需要从左到右读取上一行，不需要保存整个杨辉三角。

以第 4 行生成第 5 行为例：

$1,3,3,1 \quad\longrightarrow\quad 1,4,6,4,1$

把边界看成两个 $0$：

$0,\boxed{1,3,3,1},0$

然后依次计算相邻两数之和。问题变成：怎样一边从左到右消费旧的一行，一边把新的一行接到后面？

队列正好适合这个过程。

用队列生成下一行

初始化：队列保存上一行，并在队尾补一个右边界 $0$；变量 prev=0 表示左边界：$Q=[1,3,3,1,0],\qquad prev=0$。

每次重复：先出队得到 $x$，计算 $y=prev+x$，再把 $y$ 入队并令 prev=x。一行生成完毕后，如果还要继续生成下一行，需要先把 prev 重置为 $0$，并再次在队尾补一个右边界 $0$。

队列应用二：网格布线

给定一个网格：

a 是起点，b 是终点
灰色格不可通过
每一步只能向上、下、左、右移动一格
目标是找到从 a 到 b 的最短路径

为什么这里需要队列

从 a 出发，可以把所有位置按距离分层：

第 0 层：a
第 1 层：一步能到的位置
第 2 层：两步能到的位置
……

如果始终先处理更早发现的位置，就会把距离较小的一整层处理完，再进入下一层。

这正是先进先出队列的规则。因此：

一个位置出队 → 检查它的未访问邻格 → 给邻格编号并入队

第一次发现 b 时，得到的距离一定最短。

队列如何推进搜索前沿

左边是网格中的编号过程，右边始终显示当前队列。队头就是下一次要扩展的位置。

网格布线算法

static boolean findPath(boolean[][] open, Position start, Position finish) {
  validateGrid(open);
  requireInside(open, start);
  requireInside(open, finish);
  if (!open[start.row()][start.col()] || !open[finish.row()][finish.col()]) {
    return false;
  }

  int rows = open.length;
  int cols = open[0].length;
  boolean[][] visited = new boolean[rows][cols];
  LinkedQueue<Position> queue = new LinkedQueue<>();
  queue.offer(start);
  visited[start.row()][start.col()] = true;
  int[][] delta = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

  while (!queue.isEmpty()) {
    Position current = queue.poll();
    if (current.equals(finish)) {
      return true;
    }
    for (int[] direction : delta) {
      int nextRow = current.row() + direction[0];
      int nextCol = current.col() + direction[1];
      if (0 <= nextRow && nextRow < rows
          && 0 <= nextCol && nextCol < cols
          && open[nextRow][nextCol]
          && !visited[nextRow][nextCol]) {
        visited[nextRow][nextCol] = true;
        queue.offer(new Position(nextRow, nextCol));
      }
    }
  }
  return false;
}

private static void validateGrid(boolean[][] open) {
  Objects.requireNonNull(open, "open");
  if (open.length == 0 || open[0] == null || open[0].length == 0) {
    throw new IllegalArgumentException("grid must be non-empty");
  }
  int columns = open[0].length;
  for (boolean[] row : open) {
    if (row == null || row.length != columns) {
      throw new IllegalArgumentException("grid must be rectangular");
    }
  }
}

private static void requireInside(boolean[][] open, Position position) {
  Objects.requireNonNull(position, "position");
  if (position.row() < 0 || position.row() >= open.length
      || position.col() < 0 || position.col() >= open[0].length) {
    throw new IndexOutOfBoundsException(position.toString());
  }
}

findPath(…) 在网格中返回从起点到终点的一条可行路径；访问标记避免重复搜索同一格。

搜索前先确认网格、起终点和可通行性都合法；这些条件不满足时，最短路问题没有必要进入广度优先搜索。

起点入队时就标记 visited；队列保存“已发现但尚未扩展”的前沿，先进先出规则让它们按距离层次被处理。

每次从队头取出的都是当前最早发现的位置；因此第一次取到终点时，不可能还有更短路径尚未处理。

只把合法、可通行、未访问邻格加入下一层，并在入队时立即标记；这样每个格子最多入队一次，避免同层重复发现。

若队列耗尽仍未遇到终点，所有从起点可达的位置都已扩展过，因此可以确定不存在路径。

validateGrid(…) 只验证输入边界，使后续核心算法可以在合法前提下运行。

广度优先搜索的数组访问依赖矩形网格；先统一校验每行长度，后续才能用同一个列边界安全扫描。

requireInside(…) 只验证输入边界，使后续核心算法可以在合法前提下运行。

起点和终点还必须分别落在网格内部；把越界错误挡在搜索前，广度优先搜索主循环就只处理合法坐标。

网格布线复杂度

设网格规模为 $m\times m$。

编号阶段每个格子最多入队一次：

\[ O(m^2) \]

路径重构只沿最短路径回退：

\[ O(PathLen) \]

栈与队列对比

维度	栈	队列
删除规则	最近加入者先删除	最早加入者先删除
典型算法	深度优先搜索、递归、表达式处理	广度优先搜索、缓冲区、调度
关键指针	`top`	`front` 与 `rear`
数组实现	单端增长	循环数组
链式实现	表头作为栈顶	头删尾插

本章小结

栈的抽象数据类型用同一端完成插入和删除；数组栈关注容量边界，链式栈关注表头指针更新。
两个栈共享一个数组时，空间利用率来自相向增长，真正的满栈条件是两个栈顶边界相邻。
只有一种括号且只判合法性时，一个计数器就足够；多种括号还必须记住尚未闭合括号的类型顺序，因此自然需要栈。后缀求值和中缀转后缀则继续利用栈保存尚未完成的计算状态。
队列的抽象数据类型分离入队端和出队端；循环队列用取模复用数组空洞，链式队列维护头尾指针。
杨辉三角和网格最短路径都依赖先进先出，用队列保证生成顺序或搜索前沿按层推进。
分析栈与队列应用时，要同时数入栈/出栈、入队/出队次数，并检查辅助存储规模。

下载本章完整 Gradle 工程

本章习题

习题 1：打印缓冲区：主机把打印数据依次写入缓冲区，打印机依次取出。
习题 2：栈容量：元素 a,b,c,d,e,f,g 依次进栈，每个元素出栈后立即进入队列，出队顺序为： b,d,c,f,e,a,g
习题 3：循环队列：数组 Q[m] 保存循环队列，rear 指示队尾，length 表示元素个数。
习题 4：循环左移：把数组 $X0,X1,\ldots,X{n-1}$ 循环左移 $p$ 位，得到： $Xp,\ldots,X{n-1},X0,\ldots,X{p-1}$

致谢

谢谢

sqlite@nju.edu.cn
https://slab-nju.cn

石守谦

中缀表达式	后缀表达式
`AB-CD#`	`ABCD-#`
`(A+B)((C-D)E+F)#`	`AB+CD-EF+#`

第 3.1 章 栈和队列