某堆栈的输入序列为l,2,3,4,下面的四个序列中不可能的输出序列是 ______。A.1,3,2,4B.3,4,2,1C.4,

Question

某堆栈的输入序列为l，2，3，4，下面的四个序列中不可能的输出序列是 ______。

A．1，3，2，4

B．3，4，2，1

C．4，3，1，2

D．2，3，4，1

Answer 1

正确答案：C
解析：若某堆栈的输入序列为1，2，3，4，按照堆栈出栈操作的原则不可能得到的出栈序列是4，3，1，2。这是因为出栈允许的第一个元素为4，必须做如下操作：首先依次将1，2，3，4进栈，然后将此时的栈顶元素4出栈，此后的栈顶元素是3；继续将3出栈(存储器此时的出栈序列为4，3)，按照题目的要求，出栈序列的下一个新元素应该是1，而此时新的栈顶元素为2，而不是1。因此由于得不到元素1，所以不能够得到序列4，3，1，2。