设栈S和队列Q初始状态为空，元素a b c d e f g依次进入栈S。要求每个元素出栈后立即进入队列Q，若7个元素出队列顺序为b d f e c a g，则栈S容量最小应该是（）。
- 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。
你可能感兴趣的试题
-
- A.V(S2)和P(S4)
- B.P(S2)和V(S4)
- C.P(S2)和P(S4)
- D.V(S2)和V(S4)
- 查看答案
-
- A.V（S1）P（S2）和V（S3）
- B.P（S1）V（S2）和V（S3）
- C.V（S1）V（S2）和V（S3）
- D.P（S1）P（S2）和V（S3）
- 查看答案
-
- A.P（S4）和V（S4）V（S5）
- B.V（S5）和P（S4）P（S5）
- C.V（S3）和V（S4）V（S5）
- D.P（S3）和P（S4）V（P5）
- 查看答案
-
- A.P(S3)和V(S4)V(S5)
- B.V(S3)和P(S4)P(S5)
- C.P(S3)和P(S4)P(S5)
- D.V(S3)和V(S4)V(S5)
- 查看答案
-
- A.P（S2）和P（S4）
- B.P（S2）和V（S4）
- C.V（S2）和P（S4）
- D.V（S2）和V（S4）
- 查看答案