设栈S和队列Q的初始状态为空,元素a b c d e f g依次进入栈S。要求每

考试题库2022-08-02  46

问题 设栈S和队列Q的初始状态为空,元素a b c d e f g依次进入栈S。要求每个元素出栈后立即进入队列Q,若7个元素出队列的顺序为b d f e c a g,则栈S的容量最小应该是(58)。A.5B.4C.3D.2

选项 A.5
B.4
C.3
D.2

答案 B

解析 本题考查数据结构基础知识。栈的特点是数据在栈顶后进先出,而队列的特点是数据先进先出,队头出,队尾进。根据题目意思,元素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。
转载请注明原文地址:https://tihaiku.com/congyezige/2407807.html

最新回复(0)