问题
单项选择题
一个栈的入栈序列是1,2,3,4,5,则该栈不可能输出的序列是______。
A.5,4,3,2,1
B.4,5,3,2,1
C.4,3,5,1,2
D.1,2,3,4,5
答案
参考答案:C
解析: 此类问题解答的基本原理是:一串数据依次通过一个栈,并不能保证出栈数据的次序总是倒置,可以产生多种出栈序列。一串数据通过一个栈后的次序由每个数据之间的进栈、出栈操作序列决定,只有当所有数据“全部进栈后再全部出栈”才能使数据倒置。事实上,存在一种操作序列——“进栈、出栈、进栈、出栈……”可以使数据通过栈后仍然保持次序不变。将一组数据入栈后,判断题目备选项中的不可能的出栈顺序。上述这类题目有一个解题技巧:在输出序列中任意元素后面不能出现比该元素小并且是升序(指的是元素的序号)的两个元素。