CSP-J 入门级 · CSP 2026 入门级第一轮 第 4 题

【单选】初始时栈为空，将 1、2、3、4 依次入栈，入栈过程中允许随时出栈。下列出栈序列中不可能出现的是（ ）。

出入栈序列可以看成"堆栈筛"：某个数要先出栈，就必须先把它压进去；一旦它出栈，比它晚压入的数只能压在它上面。

只检查"3 在 1 前面出现"这类表面特征，而没有真正模拟压栈顺序；也容易忽略"入栈过程中允许随时出栈"意味着可以边压边弹。

解析

本题考查栈的后进先出（LIFO）性质。判断某个出栈序列是否可行，最可靠的办法是"模拟 + 反证"。

合法性的判定法则

入栈顺序固定为 1,2,3,4。出栈序列合法的充要条件是：序列中不存在这样的三元组 i<j<k，使得出栈值满足 v_k < v_i < v_j（即"大、小、更小"的交叉模式）。直观理解：若 a 先于 b 出栈且 a<b，那么 b 出栈时 a 已在栈中且位于 b 下方……等价地，常见判定法是"每个元素之后出现的比它小的元素必须是降序"。

逐项验证

• A. 2，4，3，1：压 1、压 2 → 弹 2；压 3、压 4 → 弹 4、弹 3；弹 1。✓ 可行
• B. 1，2，3，4：压 1 弹 1，压 2 弹 2，压 3 弹 3，压 4 弹 4。✓ 可行
• C. 3，1，2，4：要第一个弹出 3，必须把 1、2、3 全部压栈，此时栈内自底向上是 1,2,3。弹出 3 后栈顶是 2，因此下一个只能是 2 或继续压入 4 后再弹。1 被压在 2 下面，绝不可能先于 2 弹出。✗ 不可能
• D. 1，4，3，2：压 1 弹 1；压 2、3、4 → 弹 4、弹 3、弹 2。✓ 可行

答案 C。

拓展

如果一个出栈序列中，某个较小的数 x 出现在较大的数 y 之后（x<y 且 x 后于 y 出栈），那么所有 (x, y) 之间的数必须以递减顺序出现在 x 之前——这就是常说的"Catalan 序列"判别法。n 个元素的合法出栈序列总数为卡特兰数 C_n = (2n)! / (n!(n+1)!)，本题 n=4 时共 14 种。