GESP 六级 · GESP 202409 C++ 六级 第 3 题

有 $6$ 个元素，按照 $6,5,4,3,2,1$ 的顺序进入栈 $S$，下列（ ）的出栈序列是不能出现的。

栈是后进先出（LIFO）结构。入栈push，出栈pop。常用于括号匹配、表达式求值、函数调用栈。

注意栈空时执行pop操作会导致下溢（underflow）。C++ STL stack 的 top() 在栈空时行为未定义。

【考点】栈的基本操作｜栈的出栈序列判断｜三元素相对位置模式

1. 考纲定位：GESP六级数据结构和算法模块，直接考察栈的LIFO特性与输出序列可行性判定。命题人卡住的是考生对"已入栈元素必须按逆序弹出"的直觉缺失——多数人会误以为任意排列都可能。

2. 解题思维：看到固定入栈顺序（6→5→4→3→2→1），先模拟：维护一个栈和一个入栈指针。输出某元素x时，若栈顶为x直接弹出；否则不断入栈直到x出现，若入栈耗尽仍栈顶≠x则不可能。更高效的判据是"三元素模式"：对任意i<j<k，若k在输出中出现在i之前，则i必须出现在j之后，否则违反LIFO。

3. 陷阱拆解：A和B均按此规则可构造；C中k=6在i=1之前出现，但j=5却在1之前输出（6→5→1），违反三元素条件，故不可能。D满足所有三元组约束，是可行的。常见错误是忽略入栈顺序固定，以为可以随意重排；或误判栈顶元素，以为入栈后能立即弹出深层元素。

4. 反命题思维：若把入栈顺序改为1→2→3→4→5→6，则原不可能序列C会变成可行，而原可行序列可能变为不可能。刷到这类题时先问："命题人给了什么固定入栈顺序？"这决定了哪些相对位置被锁定。