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

admin2010-02-13 55

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

选项 A、6
B、4
C、3
D、2

答案C

解析栈的特点是先进后出，队列的特点是先进先出。所以，如果一个元素序列先进入栈，再进入队列，那么，出队的序列，与入栈序列是逆序。队列不影响元素顺序。
所以，下面使用图来模拟输入和输出顺序，只给出栈的变化。
①根据题意，元素e1、e2、e3、e4、e5和e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的序列是e2、e4、e3、e6、e5、e1，那么，通过出队次序可以看出，首先是e2，说明e1、e2顺序入栈。后来e2出栈，e1还在栈中。
如图8-4所示。