题22

题22

题目

已知栈的入栈序列是 ,其出栈序列为 ,则 不可能是
A. 2,4
B. 2,1
C.
D.

分析

逐个判断每个选项可能的入栈出栈顺序。
对于 ,可能的顺序是 入, 出, 入, 出, 入, 3 出, 4 入, 4 出。
对于 B, 可能的顺序是 1 入, 2 入, 3 入, 3 出, 2 出, 4 入, 4 出, 1 出。
对于 D, 可能的顺序是 1 入, 1 出, 2 入, 3 入, 3 出, 2 出, 4 入, 4 出。
C 没有对应的序列, 因为当 4 在栈中时,意味着前面的所有元素 都已在栈中或曾经入过栈,此时若 4 第二个出栈,即栈中还有两个元素,且这两个元素是有序的 (对应入栈顺序),只能为 ,若是序列 , 则 3 已在 位置出栈,不可能再在 位置出栈,若是 和 这种情况中的任意一种,则 3 一定是下一个出栈元素,即 一定是 3,所以 不可能是 3 。

解

C
【另解】对于 为最后一个入栈元素 4,则只有 或 出栈的元素有可能为 3 (请读者分两种情况自行思考),而 绝不可能为 3 。读者在解答此类题时,一定要注意出栈序列中的 “最后一个入栈元素”, 这样可以节省答题的时间。