首页 > 试题广场 >

题目来源于王道论坛 设栈S和队列Q的初始状态均为

[单选题]
题目来源于王道论坛

设栈S和队列Q的初始状态均为空,元素a,b,c,d,e,f,g依次进入栈S。若每个元素出栈后立即进入队列Q,且7个元素出队的顺序是b,d,c,f,e,a,g,则栈S的容量至少是()。


  • 1
  • 2
  • 3
  • 4
推荐

解析:

由于队列的特点是先进先出,即栈S的出栈顺序就是队Q的出队顺序。故本题只需注意栈的特点是先进后出。出入栈的详细过程见下表。

序号

说明

栈内

栈外

序号

说明

栈内

栈外

1

a入栈

a


8

e入栈

ae

bdc

2

b入栈

ab


9

f入栈

aef

bdc

3

b出栈

a

b

10

f出栈

ae

bdcf

4

c入栈

ac

b

11

e出栈

a

bdcfe

5

d入栈

acd

b

12

a出栈


bdcfea

6

d出栈

ac

bd

13

g入栈

g

bdcfea

7

c出栈

a

bdc

14

g出栈


bdcfeag

栈内的最大深度为3,故栈S的容量至少是3。

【另解】元素的出栈顺序是b,d,c,f,e,a,g,可推出进栈出栈顺序为Push(S,a),Push(S,b),Pop(S,b),Push(S,c),Push(S,d),Pop(S,d),Pop(S,c),Push(S,e),Push(S,f),Pop(S,f),Pop(S,e),Pop(S,a),Push(S,g),Pop(S,g)。假设初始所需容量为0,每做一次Push进行一次“+1”操作,每做一次Pop进行一次“-1”操作,记录容量的最大值为3,所以选C。


发表于 2018-09-11 19:02:43 回复(0)
元素a沉底了,然后d和c要一起出去,所以Stack从下往上分别是a c d,至少要三个位置。
发表于 2022-02-26 21:30:44 回复(2)
首先我们要了解的是栈和队列表达的算法思想,栈是先进后出,队列是先进先出,
根据题意,abcdefg依次进栈,而出队顺序是bdcfeag,由此,我们联想元素进栈时也在出栈和入队,
所以我们根据最终的出队顺序推出进栈顺序的出栈和入队。
进栈a→ab   b出栈    b入队出队     出队顺序  b     S(1)
进栈abcd    dc出栈   dc入队出队   出队顺序 bdc   S(2)
进栈adcdef  fe出栈   fe入队出队   出队顺序 bdcfe S(3)
然后依次进栈出栈入队出队    出队顺序bdcfeag
但每一次顺序需要变动的时候,栈的容量变化加一
发表于 2019-10-15 18:02:18 回复(0)
在本子上画一下,最长的时候是aef,长度为3
发表于 2022-01-08 17:52:46 回复(1)
答案错了 模拟一遍是3
发表于 2019-12-16 20:50:43 回复(0)