NOIP 普及组初赛 · NOIP 2017 普及组初赛试题 第 16 题

对于入栈顺序为 $a, b, c, d, e, f, g$ 的序列，下列（ ）不可能是合法的出栈序列。

这题考栈的后进先出特性。拿到序列别慌，脑子里虚拟一个栈，按入栈顺序 a 到 g 一个个往里推，每推一个就看看栈顶是不是当前要出的那个元素，是就弹出，不是就继续推，直到推完或发现栈顶对不上，直接判非法。

最容易栽跟头的是不模拟过程，光凭直觉觉得“d 出来了，b 和 c 还在，应该能先出 b 吧”，忽略了栈里 c 压在 b 上面，c 必须先出。还有人会把合法序列和非法序列搞混，或者用卡特兰数公式去套选项，结果越算越乱。记住，判断合法性的唯一硬道理就是按顺序模拟，任何一步栈顶不对上当前要出的元素，序列立马挂掉。

考点与概念

本题核心考查栈（Stack）的后进先出（LIFO）特性以及出栈序列合法性判断。栈是一种受限的线性表，只能在一端（栈顶）进行插入（push）和删除（pop）操作。这意味着，后进入栈的元素，必须先于先进入的元素被弹出。

命题视角

NOIP 初赛这类概念题，命题人喜欢用“序列合法性”来考察对数据结构本质的理解。他们不会直接问“栈是什么”，而是把一堆打乱的序列扔出来，让你判断哪个“不可能”发生。这其实是在测试你是否有动态模拟的能力——能不能在脑海里（或草稿纸上）一步步还原操作过程，而不是死记硬背结论。