#栈、队列和数组

#考点定位

• 所属大纲章节：栈和队列的基本概念与实现、栈和队列的应用、特殊矩阵的压缩存储
• 常见题型：选择题（出栈序列合法性、循环队列判满判空与元素个数计算、共享栈、矩阵下标换算、数组地址计算）；大题中作为辅助结构出现（树的遍历、图的 DFS/BFS）
• 考查频率：高。循环队列与特殊矩阵下标几乎隔年一道选择题

工程直觉迁移：栈和队列就是你天天用的调用栈与消息队列，概念零成本；增量全部在循环队列边界方案与矩阵压缩下标公式这类需要精确记忆推导的内容上。

#栈、队列与循环队列的严格定义

• 栈：只允许在一端进行插入和删除操作的线性表，后进先出（LIFO）。可操作的一端称栈顶，另一端称栈底；入栈（进栈）与出栈均在栈顶进行——这也决定了"进栈和出栈可以交替进行"的序列合法性考法。
• 队列：只允许在一端（队尾，rear）插入、另一端（队头，front）删除的线性表，先进先出（FIFO）。
• 顺序队列与假溢出：队列顺序存储时，front/rear 指针只增不减，rear 到达数组末端即报"满"，但 front 之前出队腾出的空间无法被队尾复用——数组前部明明有空位却不能再入队，称为假溢出。
• 循环队列：将存储数组逻辑上视为首尾相接的环，front/rear 越过数组末端后回绕到 0（指针移动用取模实现），从而消除假溢出。判满判空的三种方案见下文对比表。

#核心讲解：栈的应用

#表达式求值（中缀 → 后缀/前缀）

规则要点（选择题常给一个中缀式问转换结果或问某时刻栈内容）：

• 中缀转后缀：操作数直接输出；运算符按优先级入栈，栈内优先级 $\ge$ 当前运算符的先弹出输出；左括号入栈，右括号触发弹栈直到左括号。
• 后缀表达式求值：操作数栈，遇运算符弹出两个（先弹出的是右操作数），结果回栈。
• 中缀求值需两个栈（操作数栈 + 运算符栈）；后缀求值只需一个栈。

例：A + B * (C - D) - E / F 转后缀为 A B C D - * + E F / -。

坑：同级运算符从左到右（a - b + c 转后缀是 a b - c +，不是 a b c + -）；幂运算右结合（低频）。

分步栈演示：A + B * (C - D) - E / F 转后缀（待动画化）：

#递归与栈深度

• 递归调用由运行时栈支撑：每层调用压入一个活动记录（参数、返回地址、局部变量）。
• 栈的深度 = 递归的最大嵌套层数，即空间复杂度来源。选择题问"函数递归 n 层，栈中活动记录个数"，注意是"最深时刻"的个数。
• 经典考法：单链表逆序打印（尾递归形式）递归深度 $n$；快速排序最坏（有序序列）递归深度 $n$、平均 $\log n$；二分查找递归深度 $\log n$。
• 递归转非递归：简单尾递归可用循环消除；一般情况显式栈模拟（二叉树非递归遍历，见后续章节）。

#缓冲区与其他应用

队列：操作系统设备缓冲、打印任务队列、页面置换的 FIFO 算法（这就是 LRU 对比的老对手）、图的 BFS。栈：括号匹配、进制转换、迷宫求解（DFS）、函数调用。选择题常问"下列场景适合用栈/队列的是"，判断特征：后进先出/回溯 → 栈；先进先出/公平排队 → 队列。

#循环队列判满判空三种方案对比（高频）

队头指针 front、队尾指针 rear 的约定是入队先存再 rear 后移，出队先取再 front 后移（408 主流约定，做题先看题面约定！），MaxSize 为数组容量。

判满条件详解：

• 方案 ①：留 data[rear] 所指位置为空不用，使满与空的 front/rear 关系可区分。容量 m 的循环队列最多存 m - 1 个元素（选择题白送分）。
• 方案 ③：tag = 1 表示上次操作是入队——入队后 front == rear 只可能是队满；tag = 0 表示上次是出队——出队后 front == rear 只可能是队空。

#计算题套路

套路 1：给 front/rear 求元素个数。一律用 $(\text{rear} - \text{front} + \text{MaxSize}) \% \text{MaxSize}$（方案 ①）。例：MaxSize = 8，front = 3，rear = 5 → 个数 2；rear = 2 → 个数 $(2-3+8)\%8 = 7$。

套路 2：入队/出队后指针位置。入队：rear = (rear + 1) % MaxSize；出队：front = (front + 1) % MaxSize。给"连续入队 x 次出队 y 次"的序列，从初始状态逐步推，注意每步判断是否越界判满（题目常设"队满时入队失败"的分支）。

套路 3：判断方案等价性。选择题给出某代码片段的判满判空写法，问对应哪种方案或问哪里有 bug——对照上表逐条核对。

分步演示（MaxSize = 5，方案 ①，front = rear = 0 起始，待动画化）：

#栈与队列的链式实现

链栈：带头结点的单链表做栈，头端做栈顶（压入/弹出均在头部，$O(1)$）；基本无栈满问题（除非内存耗尽）。选择题坑：若把栈顶设在链尾，压入需先遍历到尾，$O(n)$，错误设计。

链队：带头结点的单链表，front 指向头结点、rear 指向尾结点：

• 入队：rear->next = s; rear = s; $O(1)$
• 出队：p = front->next; front->next = p->next; 若出队后队空，必须 rear = front，否则 rear 悬空——这是链队选择题与代码题的高频陷阱

对比记忆：顺序队列的问题（假溢出）由循环队列解决；链队的天然优势是无假溢出、无判满烦恼，代价是每个元素的指针开销。

#双端队列

两端均可插入删除的受限线性表，两个常考变种：

考法：给入队序列 1,2,3,4，问哪些输出序列可能。技巧：先算栈的合法输出序列（子集，双端队列能力 ≥ 栈），再模拟：受限端多出的那个方向提供"额外自由度"。例如输入受限队列中，1 4 2 3 是可能的（1 出，2、3 从自由端入但不出，4 入后从受限端先删 4 再 2、3），而栈做不到。此类题选项逐个模拟，无捷径，注意"两端"都可能成为出口。

#共享栈

两个栈共享一个长度 m 的数组空间，栈底分设两端：栈 1 底在下标 0，栈 2 底在下标 m-1，向中间增长。

• 判满：top1 + 1 == top2（两栈顶相邻，中间无空隙）。约定 top1 = -1 时栈 1 空，top2 = m 时栈 2 空。
• 判空：top1 == -1 && top2 == m（各自独立判断）。
• 优点：两个栈空间互补，只有两者之和超过 m 才溢出，空间利用率高于各自独立分配。
• 适用前提：两栈规模此消彼长（如符号表/临时变量区）。只能两个栈共享，三个及以上无法这样高效（要顺序栈就有"中间栈被夹死"问题，需用堆/链式管理）。

#特殊矩阵压缩存储的下标计算

设矩阵下标从 1 开始（做题先确认题面约定，408 也可能用 0 起），存储数组下标从 0 开始。推导比背公式重要，考试允许现场推，但推错一次全题皆错。

#对称矩阵 $A_{n \times n}$（$a_{ij} = a_{ji}$）

只存下三角（含对角线），按行优先。第 $i$ 行（下三角部分）存 $i$ 个元素，故存储前 $i-1$ 行共 $\frac{i(i-1)}{2}$ 个。

$a_{ij}\ (i \ge j):\quad k = \frac{i(i-1)}{2} + j - 1;\qquad a_{ij}\ (i < j):\ \text{按 } a_{ji} \text{ 取}$

分步推导演示（$n=4$，$a_{32}$）：

验证：存序为 $a_{11}, a_{21}, a_{22}, a_{31}, \boxed{a_{32}}, \ldots$，数组下标 0,1,2,3,4 ✓。总元素数 $\frac{n(n+1)}{2}$。

上三角公式（按行优先存上三角，$i \le j$）：前 $i-1$ 行共 $\frac{(i-1)(2n-i+2)}{2}$ 个，行内第 $j-i+1$ 个：

$k = \frac{(i-1)(2n-i+2)}{2} + (j-i)$

#三角矩阵

下三角矩阵（上三角为常数 c）：存储同对称矩阵下三角，末尾多存一个 c，故 $k = \frac{i(i-1)}{2} + (j-1)$（$i \ge j$），$i < j$ 时 $k = \frac{n(n+1)}{2}$（常数的下标）。选择题常拿"常数存在哪/占几个单元"设坑：只占 1 个单元，在最后。

#三对角矩阵（带状矩阵）

$a_{ij}$ 非零当且仅当 $|i - j| \le 1$，共 $3n - 2$ 个非零元。按对角线顺序（行优先逐行、每行最多 3 个）存入数组，推导：第 $i$ 行非零元最多 3 个，但第 1 行只有 2 个，故前 $i-1$ 行共 $3(i-1) - 1$ 个；$a_{ij}$ 在第 $i$ 行内是第 $j - i + 2$ 个（$j \in \{i-1, i, i+1\}$ 对应 $1, 2, 3$）：

$k = 3(i-1) - 1 + (j - i + 2) - 1 = 2i + j - 3$

分步推导演示（$n \ge 3$，$a_{43}$，即 $i=4, j=3$）：

反向问法（给 k 求 i, j）：由 $k = 2i + j - 3$ 与 $|i-j|\le1$ 联立，或先估 $i \approx \lfloor(k+1)/3\rfloor + 1$ 再校验。

#稀疏矩阵

非零元个数远小于总元素数。两种存储：

• 三元组顺序表：(row, col, value) 按行优先排列，另存矩阵行列数与非零元个数。考点：失去随机存取特性（按坐标取元素需在三元组中查找）；三元组无法直接进行"按列"的高效转置（引出快速转置，低频）。
• 十字链表：每行每列各一条链，每个非零元结点挂进行链与列链，适合矩阵运算中非零元动态增删。

选择题坑：稀疏矩阵压缩后"能/不能随机存取"——不能；"减少了存储空间吗"——当非零元很少时是，但若非零元接近 $n^2$ 反而更费。

#二维数组地址计算（通用）

行优先：$\text{Loc}(a_{ij}) = \text{base} + [(i - l_1) \times n_2 + (j - l_2)] \times L$，其中 $n_2$ 为列数，$L$ 为元素大小，$l_1, l_2$ 为下标下界（C 从 0，Fortran/题面可能从 1）。列优先公式对称交换。做题第一步永远是把题面的下标下界归一化。

#例题（模拟题）

例 1：循环队列存储于数组 Q[0..m-1]，front 指向队头元素、rear 指向队尾元素的下一位置（方案 ① 约定），初始 front = rear = 0。当 front < rear 时，队列中元素个数为（ ）

A. rear - front B. rear - front + 1 C. rear - front - 1 D. m - rear + front

解答：方案 ① 下个数公式为 $(\text{rear} - \text{front} + m) \% m$；front < rear 时无回绕，取模退化直接等于 rear - front。选 A。错因提醒：若 rear 已回绕（rear < front），个数是 $m - \text{front} + \text{rear}$，不要把无回绕结论硬套。

例 2：$n$ 阶对称矩阵按行优先压缩存储下三角（含对角线），$a_{54}$ 在存储数组中的下标（数组下标从 0 起）为（ ）

A. 12 B. 13 C. 14 D. 15

解答：前 4 行共 $\frac{4\times5}{2} = 10$ 个，第 5 行第 4 个元素 → $10 + 4 - 1 = 13$。选 B。

#常见坑

1. front/rear 约定不唯一：有教材 rear 指向队尾元素本身（而非下一位置），此时个数公式变为 $(\text{rear} - \text{front} + 1 + m) \% m$。一切以题面约定为准，动笔前先把题面的入队出队伪代码读一遍。
2. 方案 ① 的容量是 MaxSize - 1："数组大小 m 的循环队列最多存 m - 1 个元素"，逆命题（"最多存 m-1 个"推方案 ①）也考。
3. 出栈序列合法性：$n$ 个元素合法出栈序列数是卡特兰数 $\frac{1}{n+1}\binom{2n}{n}$（$n=4$ 时 14，$n=5$ 时 42，可作选择题选项）；判断具体序列用模拟法：每个出栈元素之后的更小元素必须按降序出现。
4. 共享栈判满是 top1 + 1 == top2，不是 top1 == top2（那是留一格思想但两栈生长方向不同，top1 == top2 时已重叠出一个元素冲突）。
5. 矩阵下标公式推算时，$i < j$ 的对称矩阵元素要先换成下三角再代公式，直接代入会得到错误下标。

#自测

1. 循环队列 MaxSize = 6，方案 ①，front = 4, rear = 1，元素个数？还能入队几个元素？
2. 中缀 (a + b) * c - d 的后缀表达式？
3. 5 阶下三角矩阵（常数 c 存于末尾），$a_{52}$ 的存储下标（0 起）？常数 c 的下标？
4. 6 阶三对角矩阵非零元个数？$a_{56}$（$i=5, j=6$）的存储下标？
5. 共享栈 top1 = 3, top2 = 7（数组 0..9），还能为栈 1 压入几个元素？

答案与简析

1. 个数 $(1 - 4 + 6) \% 6 = 3$；判满后空位 $6 - 1 - 3 = 2$ 个，还能入 2 个。
2. a b + c * d -。
3. 前 4 行 $\frac{4\times5}{2} = 10$，$k = 10 + 2 - 1 = 11$；常数 c 下标 $\frac{5\times6}{2} = 15$。
4. $3n - 2 = 16$ 个；$k = 2\times5 + 6 - 3 = 13$。
5. 压入条件 top1 + 1 < top2 逐次判断：4, 5, 6 共 3 个（top1 到 6 时 top1+1 == top2 判满）。

下一步：进入 04-串与KMP，或先做 01-线性表与栈队列-章节测。