P94 22栈与队列

来源：百度知道 编辑：UC知道 时间：2024/06/09 06:42:44
设栈S和队列Q的初始状态为空，元素a,b,c,d,e,f依次通过栈S，并且一个元素出栈后即进入队列Q，若出队的顺序为b,d,c,f,e,a,则栈S的容量至少应该为（）
a 3
b 4
c 5
d 6
求详解过程

选择A

队列的处理原则是FIFO(先进先出)，
所以出队的顺序为b,d,c,f,e,a,
则入队的顺序也为b,d,c,f,e,a。

一个元素出栈后即进入队列，所以说明元素的出栈的顺序也为b,d,c,f,e,a，
栈的处理原则是FILO(先进后出)，
所以在栈S的容量最少的情况下，元素入栈/出栈顺序为：
a入栈
b入栈
b出栈 输出b进入队列
c入栈
d入栈
d出栈 输出d进入队列
c出栈 输出c进入队列
e入栈
f入栈
f出栈 输出f进入队列
e出栈 输出e进入队列
a出栈 输出a进入队列

从上面可以看出，栈内最多时为3个元素，所以栈S的容量至少应该为3