设栈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
用户登录可进行刷题及查看答案
The road of your choice, you have to go on !
粤ICP备16082171号-1
登录后提交答案