E4 栈、队列、链表

对应大纲： 2.1.3-1 线性结构（链表、栈、队列）

⚠️ 这是 S0 让你「不必现在学」的那一块——但初赛里它是高频考点：栈 14/19 套、链表 11/19 套、队列 9/19 套。

📝 好消息：初赛只考性质和判定，不要求你手写链表。 本章 25 分钟就能看完。

一、栈（Stack）

后进先出（LIFO），只有一个开口，从栈顶进、也从栈顶出。

📝 想象一摞盘子：最后放上去的最先拿走。

★ 出栈序列的合法性判定（每年都考）

给定入栈顺序，问某个出栈序列可不可能。

方法一：老实模拟。 拿目标序列比对——栈顶是要的就弹，不是就继续压，压完了还弹不出来就是非法。六个元素十几步，稳。

方法二：口诀（快，但要理解）

出栈序列中，某个数后面所有比它小的数，必须是递减的。

例（CSP 2024 第 13 题）：入栈 $1,2,3,4,5,6$，判断 1 3 5 2 4 6

• $5$ 后面比它小的是 $2, 4$ —— $2$ 在前 $4$ 在后，不递减 → 非法 ✓

⚠️ 千万看清入栈顺序！ CSP 2022 第 2 题的入栈顺序是 $6,5,4,3,2,1$（递减），很容易按习惯当成递增。读题时把入栈序列抄到草稿纸上。

栈的应用（考概念）

后缀表达式（逆波兰式）

求值：遇数字压栈，遇运算符弹两个、算完压回去。

⚠️ 先弹出来的是右操作数！ 写成 (先弹 运算符 后弹) 在减法、除法上立刻错。

还原成中缀：同样的流程，只是把「算」换成「加括号拼起来」。

CSP 2023 第 8 题：6 2 3 + - 3 8 2 / + * 2 ^ 3 + → ((6-(2+3))*(3+8/2))^2+3

📝 前缀 / 中缀 / 后缀 = 表达式树的先根 / 中根 / 后根遍历。

CSP 2022 第 6 题：a+(b-c)*d 的前缀式 = +a*-bcd CSP 2021 第 9 题：a*(b+c)*d 的后缀式 = abc+*d*

⚠️ 读题先圈「前缀」还是「后缀」——选项里一定同时放了两种。

二、队列（Queue）

先进先出（FIFO），一头进（队尾 rear）、另一头出（队头 front）。

📝 想象排队买票：先来的先走。

循环队列的公式（考过）

数组大小 $M$，队头 front、队尾 rear：

• 入队：rear = (rear + 1) % M
• 出队：front = (front + 1) % M
• 队空：front == rear
• 队满：(rear + 1) % M == front ← 会浪费一个格子，用来区分空和满
• 元素个数：(rear - front + M) % M

队列的应用

• BFS（广度优先搜索）——见 L07_广度优先搜索与队列.md
• 各种「排队」「缓冲区」模型

★ 栈 + 队列混合题

⚠️ CSP 2022 第 5 题的关键洞察：队列不改变顺序。

数据依次进栈 → 出栈 → 进队列 → 出队列。已知进栈顺序和出队列顺序，求栈的最小容量。

因为队列先进先出，出队顺序 = 入队顺序 = 出栈顺序——把队列整个划掉，题目就变成纯粹的「已知出栈序列求栈最小容量」，模拟一遍数栈内峰值即可。

📝 看到多个数据结构串联，先找那个「不改变顺序」的把它约掉。

📝 另一个必知结论：用两个栈可以实现一个队列（一个负责进、一个负责出，出栈空了就把进栈全倒过去）。CSP 2022 第 10 题的答案就是「无法用栈实现队列」这句话是错的。

三、链表（Linked List）

struct Node { int data; Node* next; };

每个结点存数据和指向下一个结点的指针，靠指针串起来，在内存里不必连续。

★ 链表 vs 数组（背这张表）

📝 一句话：数组读得快，链表改得快。

⚠️ 「链表不具有的特点」这个问法出现了至少三次（CSP 2019 第 6 题、CSP 2020 第 7 题、CSP 2022 第 4 题），答案永远是**「可随机访问任一元素」**。

种类

★ 指针操作题的通用查法

核心规矩：一旦改了某条指针，它的旧值就找不回来了——所以「还需要用到旧值」的那条指针必须最后改。

头插法（在链表最前面插入新结点）：

Node* newNode = new Node;   // 1. 造新结点
newNode->data = 42;         // 2. 填数据
newNode->next = head;       // 3. 新结点指向原来的头
head = newNode;             // 4. 最后才改 head

⚠️ 最阴的错误是「少了第 4 步」——链表接对了，但 head 还指着老地方，等于白接。指针题一定要问一句：改完之后「入口」还对不对？

在双向循环链表结点 p 之后插入 s（CSP 2022 第 11 题）：

s->next = p->next;       // 1. 先记住原后继
p->next->prev = s;       // 2. 此时 p->next 还是原后继
s->prev = p;             // 3.
p->next = s;             // 4. 最后才改 p->next

⚠️ 如果先做 p->next = s，后面的 s->next = p->next 就变成了 s->next = s——自环。 三个错误选项全是这个毛病的变体。

📝 考场做法：在草稿纸上画四个方框和箭头，按选项的顺序一条条划掉、重画。 二十秒就能看出哪个自环了。

四、题型速查

30 秒自测

1. 栈和队列各是什么「先出」原则？
2. 入栈 $1..6$，出栈序列 1 3 5 2 4 6 可能吗？为什么？
3. 后缀表达式求值时，先弹出来的是左操作数还是右操作数？
4. 前缀表达式对应表达式树的哪种遍历？
5. 循环队列判满的条件是什么？为什么要浪费一个格子？
6. 链表相比数组，快在哪、慢在哪？
7. 头插法的四步，哪一步必须放最后？
8. 能用两个栈实现一个队列吗？