设栈S和队列Q的初始状态为空,元素e1、e2、e3、e4、e5、e6依次通过栈S,一个元素出栈后即进入队列Q,若六

Question

设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5、e6依次通过栈S，一个元素出栈后即进入队列Q，若六个元素出队的顺序是e2、e4、e3、e6、e5、e1，则栈S的容量至少应该是 ______。

A．6

B．4

C．3

D．2

Answer 1

正确答案：C
解析：栈的特点是先进后出，由出栈顺序e2、e4、e3、e6、e5、e1可知：e2出栈前，栈里的元素为e2、e1，共2个元素；e4出栈前，栈里的元素为e4、e3、e1，共3个元素；e3出栈前，栈里的元素为e3、e1，共2个元素：e6出栈前，栈里的元素为e6、e5、e1，共3个元素；e5出栈前，栈里的元素为e5、e1，共2个元素；毫无疑问，栈的最小容量应为3。