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

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

admin2010-02-13  62
问题 设栈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所示。
   
   ②第2个输出元素是e4，那么，说明此时在栈中，还有e1、e3。如图8-5所示。
   
   ③第3个输出元素是e3，直接出栈即可。如图8-6所示。
   
   ④第4个输出元素是e6，说明在e3出栈后，e5、e6顺序入栈。e6出栈后，栈中剩下e5和e1。顺序出栈即可。如图8-7所示。
   
   根据前面对入栈、出栈过程的模拟，可以看出，栈s的容量至少为3。选项C为正确答案。
转载请注明原文地址:https://www.kaotiyun.com/show/5ZjZ777K
本试题收录于： 程序员上午基础知识考试题库软考初级分类
0

程序员上午基础知识考试

软考初级

相关试题推荐
随机试题
最新回复(0)