结构推理
有6个元素A,B,C,D,E,F依次入栈,允许任何时候出栈,能否得到下列的各个出栈序列,若能,给出出栈操作的过程,若不能,简述其理由。
(1) CDBEFA(2)ABEDFC(3)DCEABF(4)BAEFCD
【正确答案】第(1)个序列可以得到,操作过程为:Push(S,A),Push(S,B),Push(S,C),Pop(S),Push(S,D),Pop(S),Pop(S),Push(S,E),Pop(S),Push(S,F),Pop(S),Pop(S)。
第(2)个序列可以得到,操作过程为:Push (S,A),Pop(S),Push(S,B),Pop(S),Push(S,C),Push(S,D),Push(S,E),Pop(S),Pop(S),Push(S,F),Pop(S),Pop(S)。
第(3)个序列不可以得到,因为按照栈的后进先出或者称先进后出的原则,当A,B,C,D相继入栈,再进行两次出栈时,A和B仍在栈中,此后只能B在A前面出栈,而在此序列
中出现了A先于B出栈的情况,所以说此序列是错误的。
第(4)个序列不可以得到,因为在某一时刻,C和D同在栈中,并且D是栈顶,此后只能D先于C出栈,而在此序列中出现了C先于D出栈的情况,所以是错误的。
【答案解析】