2010 年第 1 题我做过两遍都选错。题目是：a, b, c, d, e, f 依次进栈，允许进栈退栈交替，但不允许连续三次退栈，问哪个出栈序列不可能得到。
第一遍我挨个检查"是不是合法出栈序列"，查完发现四个全都合法，当场傻眼。第二遍我才发现自己压根没看那个限制条件——D 选项 a,f,e,d,c,b 本身完全合法，但它的操作是"进一个出一个，然后连着退五次"，违反了"不能连续三次退栈"。
命题人故意给了一个双重条件：先要它是合法出栈序列，再要它满足额外限制。我第一遍只做了第一步。
这类题在 408 里特别多——栈和队列几乎年年考，而且年年都在第 2 题那个位置（跟时间复杂度占第 1 题一样有规律）。这篇把它拆成六类题型，每类给判定规则。
〇、先花两分钟：栈和队列到底是什么
栈：只能从一头进出。最后放进去的，最先拿出来（后进先出，LIFO）。
队列：从一头进、另一头出。先来的先走（先进先出，FIFO）。
两个类比：
-
栈 = 一摞盘子。你只能往顶上放，也只能从顶上拿。想拿最底下那个，得先把上面的全搬走。
-
队列 = 食堂排队。先来的先打饭，后来的排队尾，谁也不能插队。
术语（不用背，看到认识就行）：
-
Push / Pop：栈的进 / 出
-
栈顶：能操作的那一端
-
队头 / 队尾：队列的出的一端 / 进的一端
-
循环队列：用数组实现时，把数组首尾接成一个圈，避免"假溢出"
⚠️ 一个必须分清的点：栈是"一端"操作，不是"两端"。真题专门考过这句话（2017(2) 的 IV 就是错的）。双端队列才是两端。
栈与队列的结构对照、栈容量求法与循环队列公式
一、第一层：判断题（送分，但有人丢）
真题 408 真题 2009 年第 1 题：
主机与打印机速度不匹配，设一个打印数据缓冲区，它的逻辑结构是？
打印机要按原来的顺序打印，不能先来的后打。所以需要先进先出 → 队列。如果用栈，先进去的数据反而最后才打印，顺序就乱了。
答案 B：队列。
真题 408 真题 2017 年第 2 题（四条叙述选错误的）：
| 叙述 | 对不对 | 为什么 |
|---|---|---|
| I. 非递归重写递归程序必须用栈 | ❌ | 斐波那契数列用循环就能算，不需要栈 |
| II. 函数调用时系统要用栈保存信息 | ✅ | 这是栈最经典的用途（详见第九节） |
| III. 确定入栈次序就能确定出栈次序 | ❌ | 进栈退栈可以交替：1、2 入栈后 pop,pop 得 2,1；push,pop,push,pop 得 1,2 |
| IV. 栈允许在两端操作 | ❌ | 只有一端。两端那是双端队列 |
错误的是 I、III、IV → 答案 C。
二、题型一：判定出栈序列合不合法（两步法）
规则（背下来，30 秒出答案）：
对每个要出栈的元素 x：如果 x 不在栈顶，就把入栈序列里 x 前面的还没入栈的元素依次入栈；然后看 x 是不是在栈顶。是就弹出，不是就判定失败。
补一条秒杀技巧（来自 2010(1) 的另解）：
出栈序列中，若出现长度 ≥ 3 的连续下降段（相对入栈顺序），在没有额外限制时是合法的；但如果题目加了"不允许连续 k 次退栈"，那么连续下降段长度 ≥ k 的序列就不行。
真题 408 真题 2010 年第 1 题（就是开头那道）：
-
选项 D
a,f,e,d,c,b的操作是in, out, in, in, in, in, in, out, out, out, out, out——连续 5 次 out，违反"不允许连续三次退栈"。 -
用技巧看：入栈顺序是 a<b<c<d<e<f，而
f,e,d,c,b是连续 5 个逆序，长度 5 ≥ 3 → 不行。
答案 D。
⚠️ 关键提醒：A、B、C 三个选项都是合法出栈序列，它们只是恰好没有 ≥3 的连续逆序段。所以这题不能只查合法性——这是我第一遍做错的原因。
三、题型二：求栈容量至少是多少（加减法）
方法：按出栈顺序写出 Push / Pop 操作序列，遇到 Push 就 +1、遇到 Pop 就 −1，全程的最大值就是所需容量。
真题 408 真题 2009 年第 2 题：
元素 a~g 依次进栈 S，出栈后立即进队列 Q，出队顺序是
b,d,c,f,e,a,g，栈 S 的容量至少是？
队列是先进先出，所以出队顺序 = 出栈顺序。倒推出操作序列：
| 步骤 | 操作 | 栈内（底→顶） | 深度 |
|---|---|---|---|
| 1 | Push a | a | 1 |
| 2 | Push b | a b | 2 |
| 3 | Pop b | a | 1 |
| 4 | Push c | a c | 2 |
| 5 | Push d | a c d | 3 ← 最大 |
| 6 | Pop d | a c | 2 |
| 7 | Pop c | a | 1 |
| 8 | Push e | a e | 2 |
| 9 | Push f | a e f | 3 |
| 10 | Pop f | a e | 2 |
| 11 | Pop e | a | 1 |
| 12 | Pop a | 空 | 0 |
| 13 | Push g | g | 1 |
| 14 | Pop g | 空 | 0 |
最大深度 3 → 答案 C：3。
一句话记住：容量 = 出栈过程中栈里最多同时装了几个。画个深度曲线，取最高点。
四、题型三：出栈序列有多少个（卡特兰数）
n 个不同元素依次入栈，合法出栈序列的总数是第 n 个卡特兰数：
C_n = (1/(n+1)) × C(2n, n)
前几项要记：C₁=1，C₂=2，C₃=5，C₄=14，C₅=42。
真题 408 真题 2015 年第 2 题：
先序序列为 a,b,c,d 的不同二叉树有多少棵？
这题看着是树的题，其实是栈的题：前序序列相当于入栈次序，中序序列相当于出栈次序，两者一一对应。所以问题等价于"以 a,b,c,d 为入栈次序，出栈序列有几个"：
C_4 = (1/5) × C(8,4) = 70/5 = 14
答案 B：14。
真题 408 真题 2011 年第 2 题（计数，不用公式）：
a,b,c,d,e 依次进栈，所有出栈序列中以 d 开头的有几个？
d 第一个出栈 → a、b、c 必须先入栈并停在栈里，d 入栈后立刻出栈。此时栈里从顶到底是 c、b、a，所以它们仨的出栈顺序被锁死为 c, b, a。
剩下 e 可以在 d _ c _ b _ a _ 这四个空位里任选一个插入 → 4 种。
答案 B：4。
真题 408 真题 2013 年第 2 题：
入栈序列 1,2,…,n，出栈序列 p₁…pₙ，若 p₂ = 3，则 p₃ 有多少种可能取值？
p₁ 只能是 1 或 2（3 之前入栈的数）：
-
若 p₁ = 1，则 p₃ 可以是 2，也可以是 4,5,…,n
-
若 p₁ = 2，则 p₃ 可以是 1，也可以是 4,5,…,n
合起来：除 3 之外的所有数都可能 → n − 1 种。
答案 C：n − 1。
五、题型四：队列的变体（双端队列）
408 爱考"受限"的队列，一共两种：
| 变体 | 允许的操作 | 真题 |
|---|---|---|
| 输出受限双端队列 | 两端都能进，只能一端出 | 2010(2) |
| 输入受限双端队列 | 只能一端进，两端都能出 | 2021(2) |
真题 408 真题 2021 年第 2 题（输入受限）：
一端仅能入队，另一端既能入队又能出队。入队序列 1,2,3,4,5，哪个出队序列得不到？
关键观察：1 和 2 必然相邻。因为每次入队只有两个选择（从左进或从右进），而 2 紧跟 1 入队——不管 2 从哪边进，都会挨着 1。
看选项 D：4,1,3,2,5 —— 1 和 2 中间夹着 3，不相邻 → 不可能。
答案 D。
真题 408 真题 2010 年第 2 题（输出受限，就是上面表格那个）：
两端入队、一端出队，入队 a,b,c,d,e，哪个出队序列得不到？
同样的道理：a 入队后 b 紧跟入队，a 和 b 在队列中必然相邻（不管各自从哪端进）。
选项 C d,b,c,a,e 里 b 和 a 中间夹着 c → 不可能。答案 C。
一句话记住：先入队的两个元素必然相邻，拿这条去排除选项，十秒出答案。
六、题型五：循环队列的下标与判空判满
这是最容易算错的一类，因为约定不统一。做题第一步：看清楚题干说 front / rear 各自指向哪。
真题 408 真题 2011 年第 3 题：
循环队列存于 A[0..n−1]，非空时 front 指向队头元素、rear 指向队尾元素。初始为空，要求第一个入队的元素存在 A[0]，则初始 front、rear = ?
入队操作是先 rear = (rear+1) % n，再把元素放到 A[rear]。要让第一个元素落在 A[0]，入队后 rear 必须等于 0 → 入队前 rear = n−1。
front 指向队头元素，第一个元素在 A[0] → front = 0。
答案 B：0，n−1。
⚠️ 最常见的错选是 A（0, 0）——那样第一个元素会被放到 A[1]。
真题 408 真题 2014 年第 3 题：
end1 指向队头元素，end2 指向队尾元素的后一个位置，队列最多容纳 M−1 个元素。判空、判满条件是？
-
队空：两个指针重合 →
end1 == end2 -
队满：end2 再走一步就追上 end1 →
end1 == (end2 + 1) mod M
答案 A。
⚠️ 为什么最多只放 M−1 个？因为要牺牲一个位置来区分"空"和"满"——否则 end1 == end2 会同时表示空和满，分不清。
三个必背公式（设数组大小为 M）：
入队：rear = (rear + 1) % M 出队：front = (front + 1) % M 元素个数：(rear - front + M) % M
七、题型六：多队列调度（火车轨道问题）
真题 408 真题 2016 年第 3 题：
入口到出口之间有 n 条轨道，列车从左往右行驶。9 列车驶入次序
8,4,2,5,3,9,1,6,7，期望驶出次序1~9，n 至少是？
每条轨道是一个队列（先进先出），所以同一条轨道里，后进去的编号必须比前面的大（否则出不来）。问题变成：把序列分成最少几个"递增组"。
有个非常好用的结论：
最少需要的轨道数 = 最长下降子序列的长度
在 8,4,2,5,3,9,1,6,7 里找最长下降子序列：8, 4, 2, 1 ——长度 4（另一条 8,5,3,1 也是 4）。
答案 C：4。
一种可行的分配方案（验证用）：
| 轨道 | 列车（按驶入顺序） | 出队后能否满足 1~9 |
|---|---|---|
| 轨道 1 | 8, 9 | 8 在 9 前 ✓ |
| 轨道 2 | 4, 5, 6, 7 | 递增 ✓ |
| 轨道 3 | 2, 3 | 递增 ✓ |
| 轨道 4 | 1 | ✓ |
一句话记住：看到"多条队列/轨道，求最少几条"，就去找最长下降子序列。
八、栈的应用一：中缀转后缀
规则（一句话）：优先级高的先输出——扫描到操作符时，把栈里优先级 ≥ 它的都弹出去，再把自己压进去；遇到 ( 直接压，遇到 ) 一直弹到 (。
优先级：* / > + - > (
真题 408 真题 2024 年第 2 题：
x + y * (z - u) / v的后缀表达式是？
用表达式树做更快（就是把操作符当根、操作数当叶子，然后后序遍历）：
+ / \ x / / \ * v / \ y - / \ z u
后序遍历（左→右→根）：x, y, z, u, -, *, v, /, + → xyzu-*v/+
答案 A。
⚠️ 选择题强烈建议用表达式树 + 后序遍历，比模拟栈快得多，而且不容易错。只有问"栈里最多装了几个""扫到某字符时栈里是什么"时才需要真的模拟栈（如 2012(2) 答案 5、2014(2) 答案 +(-*）。
九、栈的应用二：递归调用栈与括号匹配
递归调用栈：函数调用时，系统把当前函数的现场压栈，被调用的函数返回后再出栈恢复。
真题 408 真题 2015 年第 1 题：
int S(int n) { return (n <= 0) ? 0 : S(n-1) + n; }
void main() { cout << S(1); }
调用顺序是 main() → S(1) → S(0)。栈底是最先调用的，栈顶是最后调用的 → 自栈底到栈顶：main() → S(1) → S(0)。
答案 A。
括号匹配：遇到左括号压栈，遇到右括号弹栈。栈的最大深度就是表达式的最大嵌套层数。
真题 408 真题 2025 年第 2 题：
符号栈初始为空、容量为 3，哪个表达式不能实现匹配？
数每个选项的最大嵌套层数：
-
A
(a+[b+(c+d)e]+f)+g-h→ 最深 3 ✓ -
B
[a*((b+c)/(d-e)+f/g)]-h→ 最深 3 ✓ -
C
[a*(b-(c-d)*e/(f+g))-h]→ 最深 3 ✓ -
D
[a-(b+[c*(d+e)-f]+g+h)]→ 扫到d时栈里是[ ( [ (共 4 个 ✗
答案 D。
十、20 道题考在哪（栈与队列类）
本文引用的题库中，标签属于栈/队列/入栈出栈序列/中缀转后缀的单选共 20 道：
| 年份题号 | 考什么 | 属于哪类 | 答案 |
|---|---|---|---|
| 2009(1) | 缓冲区用什么结构 | 概念 | B 队列 |
| 2009(2) | 栈容量至少多少 | 题型二 | C 3 |
| 2010(1) | 不允许连续三次退栈 | 题型一 | D |
| 2010(2) | 输出受限双端队列 | 题型四 | C |
| 2011(2) | 以 d 开头的序列个数 | 题型三 | B 4 |
| 2011(3) | 循环队列初始指针 | 题型五 | B 0,n−1 |
| 2012(2) | 中缀转后缀，栈最多几个 | 应用一 | A 5 |
| 2013(2) | p₂=3 时 p₃ 取值个数 | 题型三 | C n−1 |
| 2014(2) | 扫到 f 时栈内元素 | 应用一 | B +(-* |
| 2014(3) | 循环队列判空判满 | 题型五 | A |
| 2015(1) | 递归调用栈顺序 | 应用二 | A |
| 2015(2) | 先序序列对应二叉树数 | 题型三（卡特兰） | B 14 |
| 2016(3) | 火车轨道至少几条 | 题型六 | C 4 |
| 2017(2) | 栈的叙述正误 | 概念 | C |
| 2018(2) | 队列+栈组合输出序列 | 题型一 | C |
| 2020(2) | 给定 Push/Pop 求输出 | 题型一 | D |
| 2021(2) | 输入受限双端队列 | 题型四 | D |
| 2022(2) | 入栈出栈序列的叙述 | 概念 | D |
| 2024(2) | 中缀转后缀 | 应用一 | A |
| 2025(2) | 括号匹配栈容量 | 应用二 | D |
命题规律，四条：
-
位置极固定：20 道里有 12 道是当年的第 2 题，另有 5 道是第 3 题。拿到卷子先看第 2 题，八成是栈或队列。
-
"栈容量"和"出栈序列合法性"是双子星，几乎隔年轮换考（2009、2010、2011、2013、2018、2020、2022 都在这两类里）。
-
队列偏爱考"受限"版本（2010、2014、2021），纯队列概念只考过一次（2009(1)）。
-
中缀转后缀三年一考（2012、2014、2024），且近年更爱问"结果是什么"而不是"栈里是什么"。
口径说明：依据
zhenti_all.json中subject=数据结构的 187 道单选，按标签「栈 / 队列 / 入栈出栈序列 / 中缀转后缀 / 缓冲区」筛出 20 道。考频仅供参考，★ 少不等于不考。
十一、易错点清单
-
只查出栈序列合法性，忘了题目的额外限制（2010(1) 的"不允许连续三次退栈"）——题干里的每一句都要用上。
-
栈容量算成"元素总数"——是"同时最多装几个"，画深度曲线取最高点（2009(2)）。
-
循环队列初始值选 0,0——要看入队是"先移动指针再存"还是"先存再移动"（2011(3)）。
-
忘了循环队列要牺牲一个位置——最多放 M−1 个，否则空和满分不清（2014(3)）。
-
把栈当成两端操作——栈只有一端，两端是双端队列（2017(2) IV）。
-
认为确定入栈次序就确定出栈次序——进栈退栈可交替，出栈序列不唯一（2017(2) III）。
-
卡特兰数公式记错——是
1/(n+1) × C(2n,n)，不是1/n；前五项建议背下来：1, 2, 5, 14, 42。 -
中缀转后缀时括号处理错——遇到
)要一直弹到弹出(为止，(本身不输出。 -
递归调用栈方向搞反——栈底是最先调用的
main()，栈顶是最后调用的（2015(1)）。
速查表（文末收藏版）
三条性质
| 结构 | 操作端 | 顺序 |
|---|---|---|
| 栈 | 只有一端 | 后进先出 LIFO |
| 队列 | 一头进一头出 | 先进先出 FIFO |
| 双端队列 | 两端 | 看题目怎么限制 |
六类题型的判定规则
| 题型 | 一句话解法 |
|---|---|
| 出栈序列合法性 | 逐个模拟：不在栈顶就继续入栈，仍不在顶 → 失败 |
| 栈容量 | Push +1、Pop −1，取最大值 |
| 序列个数 | 卡特兰数 1/(n+1)·C(2n,n)：1, 2, 5, 14, 42 |
| 双端队列 | 先入的两个元素必然相邻，用这条排除 |
| 循环队列 | 先看清 front/rear 指向哪；入队先移指针再存 |
| 多轨道调度 | 最长下降子序列的长度 = 最少轨道数 |
循环队列三个公式
入队：rear = (rear + 1) % M 出队：front = (front + 1) % M 个数：(rear - front + M) % M 队空：front == rear 队满：front == (rear + 1) % M （牺牲一个位置）
中缀转后缀
优先级：* / > + - > ( 扫到操作符 → 弹出栈里优先级 >= 它的 → 自己入栈 扫到 ( → 直接入栈；扫到 ) → 一直弹到 ( 选择题最快做法：画表达式树 → 后序遍历
做题三问
-
题干有没有额外限制（"不允许连续 k 次退栈"）？
-
front / rear 各自指向的是"元素"还是"后一个位置"？
-
问的是"结果"还是"过程中的栈状态"？
本文依据
-
真题数据：
zhenti_all.json（2009—2025 年 799 题），本文引用的 20 道单选均与库中题干、选项、答案逐条核对；栈容量、出栈序列计数、火车轨道分配等结论均经本文自行演算验证 -
考点范围：408 考试大纲「数据结构 · 三、栈和队列」（栈与队列的基本性质、顺序与链式存储、循环队列、栈的应用）
-
说明：2015(2) 标签为「卡特兰数」，本质考查"前序序列与出栈序列的对应关系"，本文归入题型三；大题原文未收录在该题库中，本文不引用大题题干
-
考频统计：按题库标签筛出，口径见第十节说明，仅供参考
转载自 CSDN-专业IT技术社区
原文链接：https://blog.csdn.net/m0_56226131/article/details/169058499
