设栈S和队列Q的初始状态均为空,元素a,b,c,d,e,f,g依次进入栈S。若每个元素出栈后立即进入队列Q,且7个元素出队的顺序是b,d,c,f,e,a,g,则栈S的容量至少是()。
1
2
3
4
解析:
序号
说明
栈内
栈外
a入栈
a
8
e入栈
ae
bdc
b入栈
ab
9
f入栈
aef
b出栈
b
10
f出栈
bdcf
c入栈
ac
11
e出栈
bdcfe
5
d入栈
acd
12
a出栈
bdcfea
6
d出栈
bd
13
g入栈
g
7
c出栈
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。
这道题你会答吗?花几分钟告诉大家答案吧!
扫描二维码,关注牛客网
下载牛客APP,随时随地刷题
解析:
序号
说明
栈内
栈外
序号
说明
栈内
栈外
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。