设栈S和队列Q的初始状态为空,元素e1,e2,e3,e4,e5,e6依次通过栈S,一个元素出栈后即进入队列Q,若6个元素出队的序列是e2,e4,e3,e6,e5,e1,则栈的容量至少应该是 。
3
4
栈:12 (2) -> 1 (1) -> 134 (3) -> 1 (1) -> 156 (3)然后全部出栈入队即可得到序列243651,所以栈的最小容量为3
2
1 5 6 3 4 2
StarrySkying 回复 StarrySkying: 没看题我去
栈是后进先出的,队列是先进先出的。
出列的顺序是a2 ,a3 ,a4 ,a6, a5, a1,那么出栈的顺序也是a2 ,a4 ,a3,a6, a5, a1
所以进栈的顺序为:a1,a2,a3,a4,a5,a6
出栈是:a2,a4,a3,a6,a5,a1
计算栈的容量:
第一步: a1、a2进栈,此时栈中元素为2。
第二步:根据进栈出栈顺序,a2出栈,a3进栈,此时栈中元素为2。
第三步:a3出栈,a4进栈,a4出栈,此时栈中元素为1。
第四步:a5进栈, a6进栈,此时栈中元素为3。
第五步:a6出栈,a5出栈,a1出栈,此时栈中元素为0。
可见,栈中元素最多的时候为3个,所以栈容量至少为3。
答案:3
用户登录可进行刷题及查看答案
登录后提交答案