试题-假设栈S和队列Q的初始状态为空，元素a、b、c、d、e、f依次通过S和Q，即每一个元素必须先进栈，之后再出栈进入队列。若这6个元素出队的顺序

题目

假设栈S和队列Q的初始状态为空，元素a、b、c、d、e、f依次通过S和Q，即每一个元素必须先进栈，之后再出栈进入队列。若这6个元素出队的顺序是b、d、c、f、e、a，则栈S的容量至少应该为______。

A.3

B.4

C.5

D.6

解答

正确答案是 A

队列是先进先出的，出对顺序等于入队顺序，可以吧队列忽略，等价于问题

若这6个元素出队的顺序是b、d、c、f、e、a，则栈S的容量至少应该为______。

b出栈前栈中有元素a,b此时栈大小为2

d出栈前栈中有元素a,c,d此时栈大小为3

c出栈前栈中有元素a,c此时栈大小为2

f出栈前栈中有元素a,e,f此时栈大小为3

e出栈前栈中有元素a,e此时栈大小为2

a出栈前栈中有元素a此时栈大小为1

所以栈容量至少为3

C 3条回复评论

假期

Aaaaaaaa

发表于 2021-02-04 23:45:48

甜恩

出队序列=入队序列=出栈序列

发表于 2018-10-12 11:58:11

wqy*

画一个栈和一个队列的示意图就明白了，首先a,b依次入栈，将b弹出栈，b入队列，接下来c,d依次入栈，然后c,d依次出栈并进入队列，接下来e,f依次入栈，然后将栈中的f,e,a依次弹出栈并入队列，这个过程中栈中元素最多时有3个，所以栈的长度至少为3.

发表于 2018-10-12 11:58:05

问题信息

分类：UI专业知识 - 色彩

难度: