CSP-J 2022 第一轮 第 2 题：判断非法的出栈序列

题目

有 $6$ 个元素，按照 $6,5,4,3,2,1$ 的顺序进入栈 $S$，请问下列哪个出栈序列是非法的（ ）。

选项

• A. $5,4,3,6,1,2$
• B. $4,5,3,1,2,6$
• C. $3,4,6,5,2,1$
• D. $2,3,4,1,5,6$

答案

C

题解

答案是 C。

栈的特点是 后进先出，而且入栈和出栈可以交替进行。判断时，要看想弹出的元素是不是在栈顶。

看 C：$3,4,6,5,2,1$。

1. 为了先弹出 $3$，必须依次将 $6,5,4,3$ 入栈。此时栈内从底到顶是：

$$6,\ 5,\ 4,\ 3$$

1. 弹出 $3$，再弹出 $4$，栈内从底到顶剩下：

$$6,\ 5$$

1. 此时栈顶是 $5$，必须先弹出 $5$，才能弹出 $6$，但 C 要求先弹出 $6$，所以不可能。

其余三个选项都可以通过合法的入栈、出栈操作实现，因此选 C。