题19

题19

题目

某栈的输入序列为 ,下面的 4 个序列中,不可能为其输出序列的是 ( )
A.
B.
C. ,,,
D.

分析

后进来的一定要先出去

解

C
对于 ,可能的顺序是 入, 出, 入, 出, 入, 出, 入, 出。
对于 ，可能的顺序是 a入，B入，C入，C 出， 出，d入，d 出， 出。对于 ，可能的顺序是a入，a出，b入， 入， 出， 出， 入， 出。 没有对应的序列。
【另解】若出栈序列的第一个元素为 ,则出栈序列只能是 。
该思想通常也适用于出栈序列的局部分析: 如 12345 入栈, 问出栈序列 34152 是否正确?
如何分析?
若第一个出栈元素是 3, 则此时 12 必停留在栈中, 它们出栈的相对顺序只能是 21 , 所以 34152 错误。