● 设栈 S 和队列 Q 的初始状态为空，元素按照 a、b、c、d、e 的次序进入栈 S，当一个元素从栈中出来后立即进入队列 Q。若队列的输出元素序列是 c、d、b、a、e，则元素的出栈顺序是 （58） ，栈 S的容量至少为 （59） 。（58）A. a、b、c、d、eB. e、d、c、b、aC. c、d、b、a、eD. e、a、b、d、c（59）A. 2B. 3C. 4D. 5

本题考查数据结构基础知识。栈的特点是数据在栈顶后进先出，而队列的特点是数据先进先出，队头出，队尾进。根据题目意思，元素abcdefg必须依次进入栈S，出栈后立即进入队列Q。
1.根据7个元素出队列的顺序为bdfecag，可知元素b是第一个出栈的，b出栈之前，栈中肯定有两个元素a与b（b要进栈，a必须先进栈），到此可推出栈的容量至少为2；
2.元素b出栈后栈中还有a，根据7元素出队列顺序，接下来是d出栈，d出栈之前，栈中肯定有三个元素a、c、d（d要进栈，c必须先进栈，而a之前就在栈底），到此可推出栈的容量至少为3；
3.元素d出栈后栈中还有a、c（从栈底至栈顶方向），根据7元素出队列顺序，接下来是f出栈，f出栈之前，栈中肯定有三个元素a、c、e、f（f要进栈，e必须先进栈，而a、c之前就在栈中），到此可推出栈的容量至少为4；
4.元素f出栈后栈中还有a、c、e（从栈底至栈顶方向），根据7元素出队列顺序，接下来是e出栈；
5.元素e出栈后栈中还有a、c（从栈底至栈顶方向），根据7元素出队列顺序，接下来是c出栈；
6.元素c出栈后栈中还有a，根据7元素出队列顺序，接下来是a出栈；
7.元素a出栈后栈为空，根据7元素出队列顺序，接下来是g入栈，然后出栈。根据以上分析，栈的容量最小应为4。

出队的顺序也是出栈的顺序，由此顺序可以推出栈的容量最小值。