第3章栈、队列和数组

2027 王道 · 专题阅读 · 保留代码与校订注 · 与版本锁一致

第3章栈、队列和数组¶

通常以选择题形式考查，难度不大但命题灵活。 重点：入栈/出栈过程、出栈序列的合法性、队列的操作与特征；⚠️ 二者是线性表的应用与推广，也常出现在算法设计题中。此外双端队列特性、栈队列的常见应用、数组与特殊矩阵的压缩存储都必须掌握。

回源 · PDF 第 75 页 · b_75_5

【知识树】第3章骨架¶

栈
定义与 LIFO、Catalan 数
顺序栈（top=−1 与 top=0 两套约定）、共享栈
链栈
队列
定义与 FIFO、假溢出
循环队列（三种判满方案）
链式队列、双端队列
栈和队列的应用：括号匹配、表达式求值、递归、层次遍历、缓冲区
数组
一维/多维数组的存储与地址计算
特殊矩阵压缩：对称、三角、三对角、稀疏矩阵

回源 · PDF 第 75 页 · b_75_0；PDF 第 75 页 · b_75_2

3.1 栈¶

栈的定义和四个术语？　★1考¶

栈是仅允许在一端进行插入和删除操作的线性表。 - 栈顶 Top：允许插入删除的一端 - 栈底 Bottom：⚠️ 固定不变、不允许插入删除的另一端 - 空栈：不含任何元素 - 操作特性：后进先出（LIFO）

💡 教材方法论提醒：每接触一种新的数据结构，都应从逻辑结构、存储结构、基本运算三方面理解。

★ 考过 2017

回源 · PDF 第 75 页 · b_75_10

栈的六个基本操作？¶

InitStack(&S) 初始化 / DestroyStack(&S) 销毁
StackEmpty(S) 判空
Push(&S, x) 入栈 / Pop(&S, &x) 出栈（弹出栈顶并用 x 返回）
GetTop(S, &x) ⚠️ 读栈顶但不出栈，栈状态不变

⚠️ 栈和队列都是操作受限的线性表 —— 不允许直接访问或修改中间的元素。

回源 · PDF 第 76 页 · b_76_8

出栈序列总数怎么算？　★7考¶

n 个不同元素按固定次序入栈，可能的出栈序列总数为：

\[\frac{1}{n+1}C_{2n}^{n}\]

这就是卡特兰（Catalan）数。

💡 常用值：n=3 → 5 种；n=4 → 14 种；n=5 → 42 种。 ⚠️ 判合法性的口诀：已出栈的元素中，任何"较早入栈者"不能排在"其后入栈且尚未出栈者"之前 —— 实操上直接模拟一遍入出栈最稳。

★ 考过 2010、2011、2013、2015、2018、2020、2022

回源 · PDF 第 76 页 · b_76_12

顺序栈两套约定的四个条件？　★1考¶

约定一：top 初始为 −1（top 指向栈顶元素本身） - 入栈：S.data[++S.top] = x（指针先加 1，再入栈） - 出栈：x = S.data[S.top--]（先出栈，指针再减 1） - 栈空 S.top == −1；栈满 S.top == MaxSize−1；栈长 S.top+1

约定二：top 初始为 0（top 指向栈顶元素的下一个位置） - 入栈：S.data[S.top++] = x - 出栈：x = S.data[--S.top] - 栈空 S.top == 0；栈满 S.top == MaxSize

⚠️ 做题必看题目给的是哪套约定，判空判满条件随之改变。

★ 考过 2009

回源 · PDF 第 76 页 · b_76_14；PDF 第 76 页 · b_76_21；PDF 第 77 页 · b_77_3；PDF 第 77 页 · b_77_15；PDF 第 77 页 · b_77_17；PDF 第 78 页 · b_78_4

共享栈的判满条件是什么？¶

两个顺序栈共享同一段数组：栈底分别置于数组两端，栈顶向中间延伸。 - 初始：top0 = −1（0 号栈空），top1 = MaxSize（1 号栈空） - ⚠️ 栈满条件：top1 − top0 == 1（两栈顶相邻） - 0 号栈入栈 top0 先加 1 再赋值；1 号栈入栈 top1 先减 1 再赋值

好处：⚠️ 空间可动态调节，仅当整个数组占满才溢出；存取时间复杂度仍是 O(1)，对效率无影响。

回源 · PDF 第 78 页 · b_78_5；PDF 第 78 页 · b_78_10

链栈的两个优点和约定？¶

优点：便于动态分配存储空间，不存在栈满溢出问题；多栈共存时能更灵活地利用内存。

⚠️ 约定：所有操作均在链表的表头进行；本节实现不带头结点，栈顶指针直接指向栈顶元素。

typedef struct LinkNode{
    ElemType data;
    struct LinkNode *next;
}LiStack;

⚠️ 带头结点的链栈其初始化、判空及操作细节会有所不同，做题按题目设定来。

回源 · PDF 第 78 页 · b_78_11

3.2 队列¶

队列的定义和五个基本操作？¶

队列是仅允许在一端插入、另一端删除的线性表，操作特性是先进先出（FIFO）。 - 队头 Front（队首）：允许删除的一端 - 队尾 Rear：允许插入的一端

五个操作：InitQueue(&Q)、QueueEmpty(Q)、EnQueue(&Q, x)、DeQueue(&Q, &x)、GetHead(Q, &x)（⚠️ 读队首但不出队）。

回源 · PDF 第 88 页 · b_88_2

什么是假溢出？¶

顺序队列约定：front 指向队首元素，rear 指向队尾元素的下一个位置；初始 Q.front = Q.rear = 0。 - 入队：先存入队尾，再 rear 加 1 - 出队：先取出队首，再 front 加 1

⚠️ 假溢出：出队若干次后，队列中仅剩少量元素但 rear 已达 MaxSize，此时继续入队会"上溢"——但数组中其实仍有空闲单元，所以叫假溢出。 ⚠️ 所以不能用 Q.rear == MaxSize 作为队满条件。

⚠️ 教材特别提示：不同教材对 front / rear 含义的约定可能不同（rear 可能指向队尾元素本身），这会导致入队出队实现不同 —— 做题以题目为准。

回源 · PDF 第 89 页 · b_89_0

循环队列的四个公式？　★1考¶

初始：Q.front = Q.rear = 0
队首指针进 1：Q.front = (Q.front + 1) % MaxSize
队尾指针进 1：Q.rear = (Q.rear + 1) % MaxSize
⚠️ 队列长度：(Q.rear − Q.front + MaxSize) % MaxSize

💡 循环队列的本质：把顺序存储空间在逻辑上组织为环状，靠取模运算实现回绕，用来解决假溢出。

★ 考过 2011

回源 · PDF 第 89 页 · b_89_11；PDF 第 90 页 · b_90_7；PDF 第 90 页 · b_90_12；PDF 第 90 页 · b_90_14

循环队列判空判满的三种方案？　★1考¶

⚠️ 根本矛盾：队空是 front == rear；但 rear 追上 front 时同样满足 front == rear，此时却是队满 —— 仅凭 front == rear 无法区分。

① 牺牲一个存储单元（⚠️ 最普遍的做法）：约定"队尾指针的下一位置为队首"作为队满标志
队满：(Q.rear + 1) % MaxSize == Q.front
队空：Q.front == Q.rear
元素个数：(Q.rear − Q.front + MaxSize) % MaxSize
② 增设 size 成员：入队成功 size++，出队成功 size−−
队空 Q.size == 0；队满 Q.size == MaxSize
⚠️ 两种情形都有 front == rear，靠 size 区分
③ 增设 tag 标志位：
⚠️ 出队后置 tag = 0，若此时 front == rear → 队空
⚠️ 入队后置 tag = 1，若此时 front == rear → 队满

💡 记忆法："删了还相等就是空，加了还相等就是满"。

★ 考过 2014

回源 · PDF 第 89 页 · b_89_13；PDF 第 89 页 · b_89_17；PDF 第 90 页 · b_90_2；PDF 第 90 页 · b_90_3；PDF 第 90 页 · b_90_4

链式队列的判空条件和适用场景？　★3考¶

链式队列 = 同时带队首指针和队尾指针的单链表；front 指向队头结点，rear 指向队尾结点。

⚠️ 不带头结点时：Q.front == NULL 且 Q.rear == NULL 为空队
⚠️ 带头结点时：Q.front == Q.rear 为空队

⚠️ 不带头结点的边界处理烦琐（入队要判断原队列是否为空、出队要判断是否删的是最后一个），所以通常设计为带头结点，使插入删除逻辑统一。

适用场景：⚠️ 元素数量频繁变化，且不存在队满或溢出问题；程序中需要多个队列时优先选链式队列，可避免存储分配不合理或溢出。

★ 考过 2019

回源 · PDF 第 91 页 · b_91_4

链式队列出队时那个 if 是干什么的？　★1考¶

bool DeQueue(LinkQueue &Q, ElemType &x){
    if (Q.front == Q.rear) return false;   // 空队
    LinkNode *p = Q.front->next;
    x = p->data;
    Q.front->next = p->next;
    if (Q.rear == p) Q.rear = Q.front;     // ← 关键这一句
    free(p);
    return true;
}

⚠️ 那个 if 处理的是"原队列中只有一个结点"的情况 —— 删除后队列变空，必须把 rear 拉回 front，否则 rear 会变成野指针。

入队很简单：Q.rear->next = s; Q.rear = s;（带头结点时无须判空）。

★ 考过 2019

回源 · PDF 第 91 页 · b_91_20

双端队列的两种受限形式？　★2考¶

双端队列 = 允许在两端插入和删除的线性表，⚠️ 两端地位平等。 - 输出受限的双端队列：一端可插可删，另一端只允许插入 - 输入受限的双端队列：一端可插可删，另一端只允许删除

⚠️ 一个重要退化：若限定从某端点插入的元素只能从该端点删除，双端队列就蜕变为两个栈底相邻接的栈。

⚠️ 入队出队规则：前端插入的排在后端插入的之前；出队时无论从哪端出，先出的总排在后出的之前。

★ 考过 2010、2021

回源 · PDF 第 92 页 · b_92_9

双端队列经典例题：输入 1,2,3,4 各有哪两种序列做不到？¶

总排列 4! = 24 种，纯栈能得 14 种（Catalan），剩 10 种： 1,4,2,3 / 2,4,1,3 / 3,4,1,2 / 3,1,4,2 / 3,1,2,4 / 4,3,1,2 / 4,1,3,2 / 4,2,3,1 / 4,2,1,3 / 4,1,2,3

⚠️ 输入受限的双端队列做不到的两种：4,2,3,1 和 4,2,1,3
⚠️ 输出受限的双端队列做不到的两种：4,1,3,2 和 4,2,3,1

💡 由此可推第三问：两者都做不到的是 4,2,3,1（两个名单里都有它）。 💡 分析框架：输入受限时，一端输出相当于队列（1,2,3,4），另一端输出相当于栈（14 种）；混合使用可再多得 8 种。

★ 考过 2010、2021

回源 · PDF 第 93 页 · b_93_3；PDF 第 93 页 · b_93_16

3.3 栈和队列的应用¶

括号匹配算法的四步？¶

① 初始化空栈，顺序扫描括号序列
② 遇左括号入栈（表示新增一个待匹配的期待，优先级最高）
③ 遇右括号检查栈：⚠️ 栈非空且栈顶左括号与之匹配 → 弹出栈顶；否则序列非法，算法终止
④ 扫描结束后栈为空则合法，否则存在未匹配的左括号，非法

💡 为什么是栈：新读入的左括号会让先前的期待"暂时搁置"，而最近的期待最先被满足 —— 完全符合 LIFO。

回源 · PDF 第 102 页 · b_102_2

后缀表达式和表达式树是什么关系？　★1考¶

中缀表达式：运算符在两操作数之间，⚠️ 符合人类阅读习惯但不便于计算机求值，且必须依赖括号明确运算次序
后缀表达式：运算符在操作数之后，⚠️ 结构已隐含运算顺序，无须括号，仅由操作数和运算符构成

⚠️ 关键联系：中缀 A+B*(C−D)−E/F 的后缀是 ABCD−*+EF/−，⚠️ 它与该表达式树的后序遍历序列一致。

💡 顺带记：前缀 = 先序遍历，后缀 = 后序遍历，中缀 = 中序遍历。

★ 考过 2025

回源 · PDF 第 102 页 · b_102_16

中缀转后缀的手算三步？　★1考¶

① 按运算优先级对整个表达式逐层加括号
② 把每个运算符移到其所在括号的右括号之后，形成"左操作数右操作数运算符"
③ 删除所有括号

例 A+B*(C−D)−E/F： - 加括号 ((A+(B*(C−D)))−(E/F)) - 移运算符、去括号 → ABCD−*+EF/−

★ 考过 2024

回源 · PDF 第 103 页 · b_103_1

中缀转后缀的机器算法（栈规则）？¶

从左至右扫描，用一个运算符栈： - 操作数 → 直接加入后缀表达式 - 界限符："(" 直接入栈；")" ⚠️ 不入栈，不断弹出栈顶运算符加入后缀表达式，直到遇到 "(" 并将其弹出丢弃 - 运算符： - ⚠️ 优先级高于栈顶，或栈顶为 "(" → 直接入栈 - ⚠️ 优先级低于或等于栈顶 → 依次弹出栈中运算符加入后缀表达式，直到栈空 / 栈顶为 "(" / 遇到优先级更低的运算符，再把当前运算符入栈 - 扫描完毕 → 把栈中剩余运算符依次弹出加入后缀表达式

💡 关键分界："低于或等于"就要先弹 —— 等号这里最容易错。

回源 · PDF 第 103 页 · b_103_10

后缀表达式求值时哪个是左操作数？　★1考¶

从左至右扫描： - 操作数 → 压栈 - 操作符 → 弹出两个操作数，⚠️ 先弹出的是右操作数 Y，后弹出的是左操作数 X，执行 X Y，结果压回栈中 - 处理完毕，栈顶元素即为最终结果

⚠️ 顺序千万别反 —— 对减法除法这类不满足交换律的运算，弹反了答案就错。

💡 教材例：ABCD−*+EF/− 的求值共 12 步，中间结果依次为 R1=C−D、R2=B*R1、R3=A+R2、R4=E/F、R5=R3−R4。

★ 考过 2018

回源 · PDF 第 104 页 · b_104_2

什么是栈的深度？怎么求？　★3考¶

栈的深度 = 栈中元素的最大个数。

⚠️ 题目常见形式：给出入栈和出栈序列，要求计算栈所需的最大容量；⚠️ 有时以中缀与后缀表达式的形式间接提供。

解法：手工模拟转换或求值过程，记录过程中栈内元素的最大值。

★ 考过 2009、2012、2025

回源 · PDF 第 103 页 · b_103_17

递归必须满足哪两个条件？效率为什么低？¶

递归体（递归表达式）：描述问题如何分解为更小规模的同类子问题
边界条件（递归出口）：⚠️ 确保递归在有限步内终止

⚠️ 递归定义不能是循环或无终止的。

两个缺陷： - ⚠️ 递归深度过大容易导致栈溢出 —— 因为每层调用的返回地址、局部变量、形参都保存在递归工作栈中 - ⚠️ 效率低下的主要原因是存在大量重复计算

💡 教材例（斐波那契 F(5)）：F(3) 算 2 次，F(2) 算 3 次，F(1) 调 5 次，F(0) 调 3 次。

⚠️ 重要结论：任何递归算法均可转换为非递归算法，通常需借助显式栈模拟递归调用过程。

回源 · PDF 第 105 页 · b_105_2

二叉树层次遍历的三步？¶

① 将根结点入队
② 队列为空则遍历结束，否则执行 ③
③ 取出队首结点并访问；有左孩子则左孩子入队，有右孩子则右孩子入队；返回 ②

💡 为什么用队列：在处理当前层的同时把下一层元素按序加入待处理队列，FIFO 特性天然保存了后续待处理元素的顺序。

回源 · PDF 第 105 页 · b_105_8

队列在计算机系统中的两类应用？　★2考¶

解决主机与外设速度不匹配：⚠️ 打印数据缓冲区实际上就是一个队列 —— 主机把数据依次写入缓冲区，满了就暂停输出转向其他任务；打印机按 FIFO 逐个取出打印，打完向主机请求新数据
解决多用户资源竞争：把 CPU 请求按时间顺序排成队列 —— 每次把 CPU 分配给队首用户，程序结束或用完时间片后出队，再分配给新队首；⚠️ 复杂系统还可引入多队列机制按优先级调度

★ 考过 2009、2016

回源 · PDF 第 106 页 · b_106_3

3.4 数组和特殊矩阵¶

数组和线性表是什么关系？它支持哪些操作？¶

数组是由 n（n ≥ 1）个相同类型元素组成的有限序列，下标的取值范围称为维界。

⚠️ 数组是线性表的推广：一维数组可视为一个线性表；二维数组可视为其元素为定长一维数组的线性表。

⚠️ 关键限制：数组一旦定义，维数与维界即固定不变 → 除初始化和销毁外，数组仅支持存取元素和修改元素两种基本操作（不能插入删除）。

回源 · PDF 第 112 页 · b_112_7

一维和二维数组的地址公式？　★1考¶

一维 A[0…n−1]，每个元素占 L 个单元： LOC(aᵢ) = LOC(a₀) + i × L
二维（按行优先），行列下标范围 [0, h₁]、[0, h₂]： LOC(a_{i,j}) = LOC(a_{0,0}) + [i × (h₂+1) + j] × L

⚠️ 按行优先：先行后列 —— 先存行号小的；同一行内先存列号小的。 ⚠️ 公式里的 (h₂+1) 是每行的元素个数，做题时若下标从 1 开始要相应调整。

★ 考过 2021

回源 · PDF 第 113 页 · b_113_4

按列优先的地址公式？¶

按列优先：先列后行 —— 先存列号小的；同一列内先存行号小的。 LOC(a_{i,j}) = LOC(a_{0,0}) + [j × (h₁+1) + i] × L

💡 对照记：按行优先乘的是"每行元素个数 (h₂+1)"，按列优先乘的是"每列元素个数 (h₁+1)"，且 i、j 互换位置。

例 A[2][3] 按列优先的存放次序：a₀₀ a₁₀ a₀₁ a₁₁ a₀₂ a₁₂。

回源 · PDF 第 113 页 · b_113_5；PDF 第 113 页 · b_113_11

什么是压缩存储？什么是特殊矩阵？¶

压缩存储：⚠️ 为多个值相同的元素只分配一个存储空间，对零元素不分配存储空间
特殊矩阵：具有大量相同元素或零元素，且分布有规律的矩阵 —— 对称矩阵、上（下）三角矩阵、对角矩阵

压缩方法：只存一份实际数据，其余通过下标映射访问。

回源 · PDF 第 113 页 · b_113_16；PDF 第 113 页 · b_113_19

对称矩阵压缩后的下标公式？　★2考¶

n 阶对称矩阵满足 a_{i,j} = a_{j,i}，元素分为上三角区、主对角线、下三角区三部分。 ⚠️ 压缩存储于一维数组 B[n(n+1)/2]，通常只存下三角部分（含主对角线）。

下标公式（数组下标从 0 开始，i、j 从 1 开始）：

\[k = \begin{cases} \dfrac{i(i-1)}{2} + j - 1, & i \ge j \\[6pt] \dfrac{j(j-1)}{2} + i - 1, & i < j \end{cases}\]

💡 推导逻辑：a_{i,j} 前面有第 1 行 1 个 + 第 2 行 2 个 + … + 第 i−1 行 i−1 个，再加本行的 j−1 个。 ⚠️ i < j 时（上三角区）用对称性 a_{i,j} = a_{j,i}，把 i、j 对调代入即可。

⚠️ 记法约定：A[n][n] 等价于 A[0…n−1][0…n−1]（下标从 0）；A[1…n][1…n] 表示下标从 1；矩阵元素 a_{i,j} 的行号列号通常从 1 开始。

★ 考过 2018、2020

回源 · PDF 第 113 页 · b_113_21

三角矩阵为什么要多一个存储单元？　★1考¶

⚠️ 三角矩阵的另一半是同一个常量，需要额外存储该常量一次 → 压缩存储在 B[n(n+1)/2 + 1] 中（对比对称矩阵是 B[n(n+1)/2]，不加 1）。

下三角矩阵（上三角区全为常量）：

\[k = \begin{cases} \dfrac{i(i-1)}{2} + j - 1, & i \ge j \\[6pt] \dfrac{n(n+1)}{2}, & i < j\ (\text{常量位置}) \end{cases}\]

上三角矩阵（下三角区全为常量）：

\[k = \begin{cases} \dfrac{(i-1)(2n-i+2)}{2} + (j-i), & i \le j \\[6pt] \dfrac{n(n+1)}{2}, & i > j\ (\text{常量位置}) \end{cases}\]

💡 上三角公式的推导：第 1 行 n 个、第 2 行 n−1 个 … 第 i−1 行 n−i+2 个，本行再走 j−i 个。

★ 考过 2011

回源 · PDF 第 114 页 · b_114_18

三对角矩阵的正反下标公式？　★1考¶

三对角矩阵：⚠️ 当 |i − j| > 1 时 a_{i,j} = 0，非零元素仅集中在以主对角线为中心的 3 条对角线上。

按行优先存入一维数组 B，a₁,₁ 存于 B[0]： - 正推：k = 2i + j − 3 - 反推：i = ⌊(k+1)/3⌋ + 1，j = k − 2i + 3

教材验算：k=0 → i=1, j=1（a₁,₁）；k=2 → i=2, j=1（a₂,₁）；k=4 → i=2, j=3（a₂,₃）。

★ 考过 2016

回源 · PDF 第 115 页 · b_115_15

稀疏矩阵存三元组时还要存什么？　★2考¶

稀疏矩阵：非零元素个数 t 远小于总元素个数 s（如 100×100 的矩阵只有不到 100 个非零元素）。

因为非零元素分布无规律，光存值不够，还要记行列 → 三元组（行标 i，列标 j，值 a_{i,j}）。

⚠️ 两种存储方式：数组存储（简单直接，插入删除效率低）；十字链表存储（适用于频繁插入删除）。 ⚠️ 无论哪种方式，都必须额外保存矩阵的行数、列数和非零元素个数。 ⚠️ 稀疏矩阵压缩存储后便失去了随机存取特性。

★ 考过 2017、2023

回源 · PDF 第 116 页 · b_116_1

【原书试题精选与答案方法】第3章¶

2009、2020 统考：怎样用“逐步模拟”求栈的最大容量和出栈结果？¶

2009 第 26 题选 C，最小容量为 3；2020 第 30 题选 D，出栈序列为 \(b,c,e\)。

最大容量题：把 Push 记为栈深 \(+1\)、Pop 记为栈深 \(-1\)，逐步执行；过程中出现的最大栈深就是最小容量。2009 题按目标出队序列反推栈的出栈次序，最大深度为 3。
给定操作序列题：维护“栈内元素”和“已出栈元素”两列。2020 题依次执行操作后，三次 Pop 得到 \(b,c,e\)。

⚠️ 队列只保持出队次序与入队次序一致；题目中“出栈后立即入队”时，给出的出队序列也就是栈的出栈序列。

回源 · PDF 第 84 页 · b_84_7；PDF 第 84 页 · b_84_8；PDF 第 84 页 · b_84_10；PDF 第 84 页 · b_84_11；PDF 第 85 页 · b_85_3；PDF 第 85 页 · b_85_4；PDF 第 85 页 · b_85_6

2010、2011、2013、2022 统考：受约束的出栈序列怎样快速判断？¶

答案：2010 选 D；2011 选 B（4 种）；2013 选 C（\(n-1\) 种）；2022 选 D。

2010：连续 Pop 产生的片段必按入栈顺序的逆序出现；题目不许连续 3 次 Pop，出现长度至少为 3 的连续逆序片段即可判非法。
2011：\(d\) 首先出栈后，\(c,b,a\) 的相对出栈顺序锁死为 \(c,b,a\)；新元素 \(e\) 可插入这条序列的 4 个空位，因此有 4 种。
2013：已知 \(P_2=3\)，分别构造 \(P_1=1\) 与 \(P_1=2\)，可知 \(P_3\) 能取 1、2 及 \(4\sim n\)，即除 3 外的 \(n-1\) 个数。
2022：同一入栈序列既可“进一个出一个”得到相同序列，也可“全进再全出”得到倒序，所以 in 与 out 可能互为倒序。

💡 局部分析的核心：某元素出栈时，仍留在它下面的较早入栈元素，其以后出栈的相对次序必然逆置。

回源 · PDF 第 84 页 · b_84_12；PDF 第 84 页 · b_84_13；PDF 第 84 页 · b_84_14；PDF 第 84 页 · b_84_15；PDF 第 84 页 · b_84_17；PDF 第 85 页 · b_85_0；PDF 第 85 页 · b_85_1；PDF 第 85 页 · b_85_2；PDF 第 85 页 · b_85_7；PDF 第 85 页 · b_85_8

综合应用题 01～02：指定开头或指定序列时，如何判出栈可能性？¶

第 01 题：\(C,D\) 先出栈后，栈中固定为“底 \(A,B\) 顶”，只需决定尚未入栈的 \(E\) 在何时进出。共有

\[CDEBA,\quad CDBEA,\quad CDBAE.\]

第 02 题：

\(BCAED\) 可以由“\(A\) 入，\(B\) 入出，\(C\) 入出，\(A\) 出，\(D,E\) 入，\(E,D\) 出”得到；
\(DBACE\) 不可能：\(D\) 首先出栈时，\(A,B,C\) 已在栈中，之后必须先出 \(C\)，不可能让 \(B,A\) 越过它。

💡 方法不是凭直觉看排列，而是锁定第一个较晚入栈却先出栈的元素，检查压在它下面的元素是否仍保持逆序约束。

回源 · PDF 第 85 页 · b_85_10；PDF 第 85 页 · b_85_11；PDF 第 85 页 · b_85_13；PDF 第 85 页 · b_85_14；PDF 第 85 页 · b_85_15；PDF 第 85 页 · b_85_16

综合应用题 03：怎样用“前缀和”判定一串 I/O 操作是否合法？¶

把入栈 I 记为 \(+1\)，出栈 O 记为 \(-1\)，扫描操作串并维护余额 \(cnt\)：

任意前缀都必须满足 \(cnt\ge 0\)，否则发生空栈出栈；
扫描结束必须满足 \(cnt=0\)，否则终态不是空栈。

原书四个序列中 A、D 合法，B、C 非法。算法只扫描一次，时间复杂度 \(O(n)\)，除计数器外空间复杂度 \(O(1)\)。

⚠️ 只检查 I 与 O 总数相等不够；例如一开始就 O，总数即使最终相等也已经非法。

回源 · PDF 第 85 页 · b_85_17；PDF 第 85 页 · b_85_18；PDF 第 85 页 · b_85_19；PDF 第 86 页 · b_86_0；PDF 第 86 页 · b_86_3

综合应用题 04：单链表中的字符怎样用半栈判回文？¶

原书方法只把前一半字符压栈，再让链表指针扫描后一半：

前 \(\lfloor n/2\rfloor\) 个字符依次入栈；
若 \(n\) 为奇数，跳过正中结点；
后半段每访问一个字符，就与栈顶比较并出栈；一旦不等立即失败；
链表到尾且栈恰好为空，才是中心对称。

时间复杂度 \(O(n)\)，辅助空间 \(O(n)\)（实际使用约 \(n/2\) 个字符）。

💡 比“全部入栈再重新扫描链表”的方法少一次完整扫描；奇数长度时，中心字符不参与配对。

回源 · PDF 第 86 页 · b_86_4；PDF 第 86 页 · b_86_5；PDF 第 86 页 · b_86_6；PDF 第 86 页 · b_86_7；PDF 第 87 页 · b_87_0；PDF 第 87 页 · b_87_1

综合应用题 05：两个共享栈的 Push/Pop 边界怎样统一处理？¶

令 \(S_1\) 从左向右增长，\(S_2\) 从右向左增长：

初始：\(top_1=-1,\ top_2=maxsize\)；
栈满：\(top_2-top_1=1\)；
\(S_1\) 入栈用 stack[++top1]=x，出栈用 stack[top1--]；
\(S_2\) 入栈用 stack[--top2]=x，出栈用 stack[top2++]；
\(S_1\) 空为 \(top_1=-1\)，\(S_2\) 空为 \(top_2=maxsize\)。

四种操作时间复杂度均为 \(O(1)\)。共享的价值是两栈能动态借用对方的空闲区，但 ⚠️ 入栈仍须先判满，出栈仍须分别判空。

回源 · PDF 第 87 页 · b_87_2；PDF 第 87 页 · b_87_3；PDF 第 87 页 · b_87_6；PDF 第 87 页 · b_87_7；PDF 第 87 页 · b_87_8；PDF 第 87 页 · b_87_10；PDF 第 87 页 · b_87_11；PDF 第 87 页 · b_87_13；PDF 第 88 页 · b_88_0

2011、2014 统考：循环队列先看 front/rear 指向哪里，怎样定初值与空满？¶

2011 第 21 题选 B：\(front=0,rear=n-1\)；2014 第 22 题选 A。

2011 题规定非空时 front 指队首元素、rear 指队尾元素，且第一个元素要落在 A[0]。入队前 rear 必先按模加 1，所以 rear 初值取 \(n-1\)，front 保持 0。
2014 题规定 end1 指队首元素、end2 指队尾后一个位置，并牺牲一个单元：队空为 \(end1=end2\)，队满为

\[end1=(end2+1)\bmod M.\]

⚠️ front、rear 的初值和公式都不是脱离定义固定背诵的；必须从“指向元素本身还是下一空位”“移动发生在读写前还是后”推出来。

回源 · PDF 第 98 页 · b_98_17；PDF 第 98 页 · b_98_18；PDF 第 98 页 · b_98_19；PDF 第 98 页 · b_98_20；PDF 第 99 页 · b_99_0；PDF 第 99 页 · b_99_1

2010、2018、2021 统考：双端队列与“队列+栈”的输出序列怎样验？¶

答案：2010 选 C；2018 选 C；2021 选 D。

2010 输出受限双端队列：第一个元素入队后，第二个元素无论从哪端入都与它相邻；目标序列若破坏这种不可跨越的邻接关系即可排除。
2018 队列+栈：若为了先输出 3 而把 1、2 依次压栈，之后栈必先弹 2 再弹 1，所以不可能再输出 \(\dots,1,2\)。
2021 输入受限双端队列：固定哪端只入后，对每个选项反向构造入队端；A、B、C 都能构造，D 不能。

💡 这类题数据很小，王道答案采用代入构造/排除。只要某选项能写出一条合法操作序列，它就是“可能”；找不到时再用不可逆的相对次序作否证。

回源 · PDF 第 98 页 · b_98_14；PDF 第 98 页 · b_98_15；PDF 第 98 页 · b_98_16；PDF 第 99 页 · b_99_2；PDF 第 99 页 · b_99_3；PDF 第 99 页 · b_99_4；PDF 第 99 页 · b_99_5

综合应用题 01：不牺牲数组单元时，tag 循环队列怎样判空判满？¶

设置 tag 记录最近一次造成 front 与 rear 相遇的是哪类操作：

初始化：\(front=rear=0,tag=0\)；
入队成功后置 \(tag=1\)，出队成功后置 \(tag=0\)；
队空：\(front=rear\land tag=0\)；
队满：\(front=rear\land tag=1\)。

入队与出队仍分别按模推进 rear、front，时间复杂度均为 \(O(1)\)，并能利用数组全部单元。

口诀：“删了还相等是空，加了还相等是满。”

回源 · PDF 第 99 页 · b_99_8；PDF 第 99 页 · b_99_9；PDF 第 99 页 · b_99_10；PDF 第 99 页 · b_99_11；PDF 第 99 页 · b_99_12；PDF 第 99 页 · b_99_13；PDF 第 99 页 · b_99_14；PDF 第 100 页 · b_100_0

综合应用题 02：一个辅助栈怎样把队列原地逆置？¶

先把队列元素全部出队并依次压栈，再把栈中元素全部弹出并重新入队：

\[Q\xrightarrow{\text{逐个出队入栈}}S\xrightarrow{\text{逐个出栈入队}}Q.\]

队列第一次转移保持原顺序，栈的 LIFO 在第二次转移时完成逆序。若有 \(n\) 个元素，时间复杂度 \(O(n)\)，辅助空间 \(O(n)\)。

⚠️ 不能只靠队列自身的入队、出队操作完成逆置，因为 FIFO 不会改变相对次序。

回源 · PDF 第 100 页 · b_100_1；PDF 第 100 页 · b_100_2；PDF 第 100 页 · b_100_3；PDF 第 100 页 · b_100_4

综合应用题 03：两个栈怎样模拟一个队列？¶

按原书约定，\(S_1\) 负责入队，\(S_2\) 负责出队：

EnQueue(x)：优先压入 \(S_1\)；若 \(S_1\) 满且 \(S_2\) 空，可先把 \(S_1\) 全部倒入 \(S_2\) 再压入；若 \(S_1\) 满且 \(S_2\) 非空，则判队满。
DeQueue(x)：若 \(S_2\) 非空，直接弹出；若 \(S_2\) 空而 \(S_1\) 非空，先把 \(S_1\) 全倒入 \(S_2\) 再弹出。
QueueEmpty()：两个栈同时为空。

关键限制：⚠️ 只有 \(S_2\) 为空时才能把 \(S_1\) 整体转入，否则会破坏先入先出次序。 一次整体搬运为 \(O(n)\)；不搬运时单次操作为 \(O(1)\)。

回源 · PDF 第 100 页 · b_100_5；PDF 第 100 页 · b_100_6；PDF 第 100 页 · b_100_7；PDF 第 100 页 · b_100_8；PDF 第 100 页 · b_100_9；PDF 第 100 页 · b_100_10；PDF 第 100 页 · b_100_11；PDF 第 100 页 · b_100_12；PDF 第 100 页 · b_100_13；PDF 第 101 页 · b_101_0；PDF 第 101 页 · b_101_1；PDF 第 101 页 · b_101_2

2019 统考综合题：怎样设计“空间只增不减、结点循环复用”的队列？¶

按王道答案，选用带 front、rear 的单向循环链表，并把 rear 所指结点保留为下一次待写的空结点：

初态只有一个空结点，\(front=rear\)；
队空：\(front=rear\)；“队满”判据为 \(front=rear\to next\)，它表示除 rear 这一个保留空结点外，已无额外可复用结点；
入队遇到这个“满”状态，就在 rear 后新申请一个结点作为新的保留空结点；随后把数据写入旧 rear，再令 \(rear=rear\to next\)；
出队读取 front 所指数据，再令 \(front=front\to next\)，旧结点留在环中等待复用。

这样只在没有额外可复用结点时扩容，已出队空间不释放而会再次使用；入队、出队始终为 \(O(1)\)。

回源 · PDF 第 101 页 · b_101_3；PDF 第 101 页 · b_101_4；PDF 第 101 页 · b_101_5；PDF 第 101 页 · b_101_6；PDF 第 101 页 · b_101_8；PDF 第 101 页 · b_101_10；PDF 第 101 页 · b_101_11

2009、2015、2016、2017 统考：系统应用、递归栈与多队列怎样判断？¶

答案：2009 选 B；2015 选 A；2016 选 C（4 条轨道）；2017 选 C。

2009 打印缓冲区要保持写入顺序，逻辑结构是 FIFO 队列。
2015 递归调用栈按调用先后压入，栈底到栈顶为 main() → S(1) → S(0)；活动记录保存返回点、局部变量、实参等。
2016 多轨道本质是多队列：同一轨道中先进入的编号必须小于后进入的编号，才能按 \(1\sim9\) 输出；按最省轨道分配至少需 4 条。
2017：消除递归不一定必须显式用栈，入栈序列不能唯一决定出栈序列，栈只允许在一端操作；仅“函数调用用栈保存必要信息”正确。

⚠️ 不要把“递归通常用栈实现”偷换成“任何递归转非递归都必须用栈”；尾递归、单向递归可能直接改写为迭代。

回源 · PDF 第 110 页 · b_110_1；PDF 第 110 页 · b_110_2；PDF 第 111 页 · b_111_2；PDF 第 111 页 · b_111_3；PDF 第 111 页 · b_111_4；PDF 第 111 页 · b_111_5；PDF 第 111 页 · b_111_6；PDF 第 111 页 · b_111_7；PDF 第 111 页 · b_111_8；PDF 第 111 页 · b_111_9

2012、2014、2018、2024 统考：表达式题怎样统一到“运算符栈规则”？¶

答案：2012 选 A（最大 5 个）；2014 选 B；2018 选 B（15）；2024 选 A。

中缀转后缀时，操作数直接输出；( 入栈；遇 ) 弹到 (；当前运算符优先级低于或等于栈顶时先弹栈。
2012 最大深度只需追踪尚未确定次序的运算符，原书逐步模拟得最大为 5。
2014 扫描到 \(f\) 时，栈底到栈顶是 + ( - *。
2018 求值必须记住先弹出的是右操作数 \(a\)，后弹出的是左操作数 \(b\)，执行 \(b\ op\ a\)；三轮结果为 \(5,3,15\)。
2024 可按“加括号→运算符移到右括号后→去括号”手算，也可画表达式树后序遍历，得到选项 A。

💡 “栈深”问的是过程中的最大同时在栈数量，不是表达式里运算符总数。

回源 · PDF 第 110 页 · b_110_3；PDF 第 110 页 · b_110_4；PDF 第 110 页 · b_110_5；PDF 第 110 页 · b_110_6；PDF 第 110 页 · b_110_7；PDF 第 110 页 · b_110_8；PDF 第 110 页 · b_110_9；PDF 第 110 页 · b_110_10；PDF 第 111 页 · b_111_0；PDF 第 111 页 · b_111_1；PDF 第 111 页 · b_111_10；PDF 第 111 页 · b_111_11；PDF 第 111 页 · b_111_12；PDF 第 111 页 · b_111_14；PDF 第 111 页 · b_111_15

2025 统考：括号栈容量题为什么只看最大嵌套深度？¶

答案 D。 扫描括号串时，每遇一个尚未匹配的左括号就入栈，遇对应右括号才出栈，因此任一时刻的栈深等于“当前未闭合括号数”。

A、B、C 的最大嵌套深度均不超过 3；
D 的括号骨架为 \([([()])]\)，最大嵌套深度为 4，容量 3 时第四个左括号无法入栈。

⚠️ 题目中的普通字符和运算符都不占这个括号栈；只提取括号骨架再数最大前缀余额即可。

回源 · PDF 第 111 页 · b_111_16；PDF 第 111 页 · b_111_17；PDF 第 112 页 · b_112_0

综合应用题 01：三类括号匹配算法必须检查哪三个失败出口？¶

从左到右扫描到 \0：左括号直接入栈；右括号到来时必须依次检查：

栈是否为空——空栈却遇右括号，失败；
栈顶类型是否对应——()、[]、{} 任一错配，失败；
扫描结束后栈是否为空——仍有左括号未闭合，失败。

三项均通过才返回 true。时间复杂度 \(O(n)\)，最坏辅助空间 \(O(n)\)。

💡 原书核心方法是“左括号入栈、右括号与栈顶配对”；实际写代码时要在 Pop 前补上判空，避免把空栈出栈写成未定义行为。

回源 · PDF 第 112 页 · b_112_2；PDF 第 112 页 · b_112_3；PDF 第 112 页 · b_112_4

2016、2018、2020、2021 统考：矩阵下标与地址题怎样统一计算？¶

答案：2016 选 B（87）；2018 选 A（50）；2020 选 C（22）；2021 选 B（300）。

2016 三对角矩阵：0 下标数组中 \(k=2i+j-3\)，故 \(m_{30,30}\) 在 \(N[87]\)；也可数“首行 2 个 + 中间 28 行各 3 个 + 本行前 1 个”。
2018 上三角按行优先：\(m_{6,6}\) 前有 \(12+11+10+9+8=50\) 个元素，所以其下标为 50。
2020 对称矩阵：先用对称性把 \(m_{7,2}\) 换成已存区域的 \(m_{2,7}\)；上三角按列优先，前面共有 22 个元素，故下标为 22。
2021 二维数组：\(220-100=120=3n+3\)，解得每行 39 个元素；\(A[5][5]\) 地址为 \(100+5\times39+5=300\)。

⚠️ 每题先写清四件事：矩阵下标起点、数组下标起点、存上/下三角、按行/列优先。

回源 · PDF 第 118 页 · b_118_19；PDF 第 118 页 · b_118_20；PDF 第 118 页 · b_118_21；PDF 第 118 页 · b_118_22；PDF 第 119 页 · b_119_1；PDF 第 119 页 · b_119_2；PDF 第 119 页 · b_119_3；PDF 第 119 页 · b_119_8；PDF 第 119 页 · b_119_9；PDF 第 119 页 · b_119_10；PDF 第 119 页 · b_119_11；PDF 第 119 页 · b_119_12；PDF 第 119 页 · b_119_13；PDF 第 119 页 · b_119_14；PDF 第 119 页 · b_119_15；PDF 第 119 页 · b_119_16；PDF 第 119 页 · b_119_17

2017、2023 统考：稀疏矩阵压缩存储究竟还要保存什么？¶

2017 第 12 题选 A：三元组表和十字链表；2023 第 16 题选 A：仅行数、列数。

三元组结点保存 (row, col, value)；十字链表把行链与列链结合，适合频繁插入、删除。
仅有三元组无法恢复矩阵边界：两个大小不同的矩阵可能有完全相同的非零三元组，因此至少还要保存总行数和总列数。
非零元素个数也常作为结构元数据保存，但 2023 题的四个判断项中，必须额外保存的是 I、III。

⚠️ 压缩后的稀疏矩阵通常失去随机存取特性；邻接矩阵的 \(O(n^2)\) 空间也不适合作为稀疏矩阵的压缩结构。

回源 · PDF 第 119 页 · b_119_6；PDF 第 119 页 · b_119_7；PDF 第 119 页 · b_119_18；PDF 第 119 页 · b_119_19；PDF 第 119 页 · b_119_20

【原书归纳总结与思维拓展】第3章¶

栈序列题有哪些原书反复使用的通法？¶

原书答案给出四层方法，按题目规模从快到稳选用：

总数：固定入栈序列的合法出栈序列数是 Catalan 数 \(\frac1{n+1}\binom{2n}{n}\)；\(n\) 很小时可直接枚举。
判合法：逐项模拟 Push/Pop，无法让目标元素来到栈顶即非法。
局部逆序约束：某元素先出时，压在其下面且尚未出的元素只能逆序出来。
盯住最后入栈元素：它一旦出栈，会把其下方栈顶关系锁死，常能迅速排除选项。

💡 计数题若指定某个开头，先锁定留栈元素的固定逆序链，再把后来元素插入可行空位，比从全部 Catalan 序列中筛选更快。

回源 · PDF 第 82 页 · b_82_18；PDF 第 82 页 · b_82_19；PDF 第 82 页 · b_82_20；PDF 第 82 页 · b_82_21；PDF 第 82 页 · b_82_22；PDF 第 82 页 · b_82_23；PDF 第 83 页 · b_83_11；PDF 第 83 页 · b_83_18

循环队列题为什么必须“先定指针口径，再写公式”？¶

原书答案反复提醒：front、rear 可以指向元素本身，也可以指向前一/后一位置；数组也可能写成 A[n] 或 A[0...n]。

稳妥步骤：

把题目的数组容量写成 \(M\)；A[n] 的容量是 \(n\)，A[0...n] 的容量是 \(n+1\)。
画一个空队、一个元素、满队三个特例，按题意执行一次入队和出队。
再写模运算与空满条件，不从熟悉模板硬套。

⚠️ “循环队列”特指顺序存储空间的逻辑回绕，不等于“用循环单链表表示的队列”；front/rear 的初值也不是固定常数。

回源 · PDF 第 97 页 · b_97_8；PDF 第 97 页 · b_97_9；PDF 第 97 页 · b_97_10；PDF 第 97 页 · b_97_11；PDF 第 97 页 · b_97_16；PDF 第 97 页 · b_97_17；PDF 第 97 页 · b_97_18；PDF 第 97 页 · b_97_19；PDF 第 98 页 · b_98_19；PDF 第 98 页 · b_98_20

递归题怎样计算调用次数和实际执行顺序？¶

先画递归调用树：每次函数调用对应一个结点，递归表达式产生的子调用按代码从左到右连边。

调用总次数 = 调用树结点数；
第几个函数被调用 = 调用树的先序访问次序；
判断效率时还要观察相同参数的子树是否重复出现，重复计算通常使递归版本更慢；
每层调用的实参、局部变量和返回地址进入系统栈。

⚠️ 先算内层实参函数，再调用外层函数；如 func(func(5))，必须先完成内层整棵调用树。

回源 · PDF 第 109 页 · b_109_10；PDF 第 109 页 · b_109_11；PDF 第 109 页 · b_109_12；PDF 第 109 页 · b_109_13；PDF 第 109 页 · b_109_14；PDF 第 109 页 · b_109_15；PDF 第 109 页 · b_109_16

特殊矩阵压缩题怎样用“平移、画图、特值”防下标错位？¶

原书不建议只死背公式，而建议：

平移：把未存区域的对称元素移到实际存储的三角区；
画图计数：先数完整的前几行/列，再数当前行/列内的偏移；
代特殊值：用 \(a_{1,1}\)、\(a_{n,n}\) 或紧邻边界的元素检查公式；
最后校正下标起点：矩阵和一维数组可能分别从 0 或 1 开始，结果常只差 1。

💡 先算“它是压缩序列中的第几个元素”，再把“第几个”转换为数组下标，能显著减少 \(+1/-1\) 混乱。

回源 · PDF 第 118 页 · b_118_1；PDF 第 118 页 · b_118_2；PDF 第 119 页 · b_119_4；PDF 第 119 页 · b_119_5

栈、队列算法大题需要把全部 ADT 接口都重写一遍吗？¶

不需要。 原书归纳指出，栈和队列在算法题中多作为辅助结构，答题时可直接声明结构并嵌入核心操作。例如顺序栈：

ElemType stack[MaxSize];
int top = -1;
stack[++top] = x;   // 入栈
x = stack[top--];   // 出栈

写题时只需补齐与本题相关的判空、判满和边界处理。链栈也可只定义结点并写必要指针语句；从统考侧重看，应优先熟练顺序栈。

⚠️ 简写不等于省略安全条件：凡可能空栈出栈、满栈入栈或删除最后一个链队结点，都要明确处理。

回源 · PDF 第 120 页 · b_120_0；PDF 第 120 页 · b_120_1；PDF 第 120 页 · b_120_2；PDF 第 120 页 · b_120_3；PDF 第 120 页 · b_120_4

怎样让一个栈在 \(O(1)\) 时间完成 Push、Pop 和 min？¶

使用两个同步栈：

主栈保存真实数据；
辅助栈在每一层保存“截至这一层的最小值”；
压入 \(x\) 时，辅助栈同步压入 \(\min(x,\text{当前最小值})\)；
弹出主栈顶时，辅助栈也同步弹出；
min() 直接读取辅助栈顶，复杂度 \(O(1)\)。

三个操作都是 \(O(1)\)，代价是额外 \(O(n)\) 空间。这是典型的以空间换时间，并且通过“每层保存前缀最小值”保证弹出最小元素后仍能立刻恢复旧最小值。

回源 · PDF 第 120 页 · b_120_5；PDF 第 120 页 · b_120_6；PDF 第 120 页 · b_120_7；PDF 第 120 页 · b_120_8

【易混点】第3章成对概念对照¶

概念 A	概念 B	一句话切分
栈 LIFO	队列 FIFO	一端进出 vs 一端进另一端出
top = −1	top = 0	指向栈顶元素本身（`++S.top` 入栈）vs 指向栈顶下一位置（`S.top++` 入栈）
顺序栈	共享栈	单栈受数组上界约束 vs 两栈底在两端、判满 top1−top0==1
顺序栈	链栈	可能栈上溢 vs 不存在栈满问题
假溢出	真溢出	rear 到头但数组仍有空位 vs 空间真的用完
牺牲单元法	size 法 / tag 法	(rear+1)%MaxSize==front vs 靠 size 或 tag 区分空满
队列长度公式	—	(rear − front + MaxSize) % MaxSize
输入受限双端队列	输出受限双端队列	做不到 4,2,3,1 和 4,2,1,3 vs 做不到 4,1,3,2 和 4,2,3,1
中缀	后缀	需要括号、人易读 vs 无须括号、机器易算
前缀/中缀/后缀	先序/中序/后序	表达式树的三种遍历一一对应
后缀求值弹栈	—	⚠️ 先弹出的是右操作数，后弹出的是左操作数
对称矩阵 B[n(n+1)/2]	三角矩阵 B[n(n+1)/2+1]	不用存常量 vs 要多存一个常量
按行优先	按列优先	乘 (h₂+1) vs 乘 (h₁+1) 且 i、j 互换
特殊矩阵	稀疏矩阵	分布有规律、可公式映射 vs 无规律、存三元组且失去随机存取

【必背数字】第3章¶

数字	含义
C(2n,n)/(n+1)	n 个元素的出栈序列总数（Catalan）；n=3→5、n=4→14、n=5→42
top==−1 / top==MaxSize−1 / top+1	顺序栈空 / 满 / 栈长（top 初值 −1 时）
top1 − top0 == 1	共享栈判满
(rear+1)%MaxSize==front	循环队列判满（牺牲一个单元法）
(rear − front + MaxSize)%MaxSize	循环队列元素个数
4! − 14 = 10	输入序列 1,2,3,4 中纯栈得不到的序列数
4,2,3,1	输入受限与输出受限双端队列都得不到的序列
LOC(a₀) + iL	一维数组地址
[i(h₂+1)+j]L / [j(h₁+1)+i]L	二维数组按行优先 / 按列优先
i(i−1)/2 + j − 1	对称矩阵（下三角）下标
(i−1)(2n−i+2)/2 + (j−i)	上三角矩阵下标
k = 2i + j − 3	三对角矩阵正推下标
i = ⌊(k+1)/3⌋+1，j = k−2i+3	三对角矩阵反推
行数、列数、非零元素个数	稀疏矩阵除三元组外必存的三项

【口诀速记】第3章¶

维度	口诀	解释
两种受限表	栈 LIFO，队 FIFO	一端进出 vs 一端进另一端出
顺序栈	先看 top 指哪	top=−1 指元素本身（++S.top 入栈）；top=0 指下一位置（S.top++ 入栈）
循环队列	删了还相等是空，加了还相等是满	tag 标志位法；牺牲单元法是 (rear+1)%MaxSize==front
队列长度	加表长再取模	(rear − front + MaxSize) % MaxSize
后缀求值	先弹右，后弹左	执行 X ⟨op⟩ Y，先弹出的是右操作数 Y
表达式与树	前中后 = 先中后序	前缀=先序遍历，中缀=中序，后缀=后序
矩阵压缩	对称不加一，三角要加一	B[n(n+1)/2] vs B[n(n+1)/2+1]（多存一个常量）
三对角矩阵	2i + j − 3	正推下标；反推 i=⌊(k+1)/3⌋+1，j=k−2i+3

回源 · PDF 第 75 页 · b_75_3；PDF 第 75 页 · b_75_4

【解题路线】第3章：栈队列数组题怎么下手¶

① 出栈序列题：问合法性 → 直接模拟入出栈；问总数 → Catalan 数 C(2n,n)/(n+1)
② 顺序栈判空判满 → ⚠️ 先看题目约定 top 指向栈顶元素本身还是下一个位置，两套条件完全不同
③ 循环队列 → ⚠️ 先确认用哪种方案：牺牲一个单元（(rear+1)%MaxSize==front）/ size 成员 / tag 标志位
④ 表达式题：中缀转后缀手算三步（加括号 → 运算符移到右括号后 → 去括号）；⚠️ 后缀求值时先弹出的是右操作数
⑤ 矩阵压缩 → ⚠️ 先确定下标从 0 还是从 1，再套公式；对称矩阵 B[n(n+1)/2]，三角矩阵要多一个单元存常量

💡 数组题的通用检查：算完下标代入一两个边界元素（如 a₁,₁ 和 aₙ,ₙ）验算一遍，比重推公式快。

回源 · PDF 第 75 页 · b_75_5；PDF 第 75 页 · b_75_6

第3章 栈、队列和数组