Question

设栈S和队列Q是初始状态为空，元素E1,E2,E3,E4,E5,E6依次通过栈S，一个元素出栈后

设栈S和队列Q是初始状态为空，元素E1,E2,E3,E4,E5,E6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出列的顺序为E2,E4,E3,E6,E5,E1,则栈S的容量至少应该是（）。

Answer 1

答案是3
设栈长度为s，起始为0
因为栈后进先出，队列先进先出。
又因为元素E1.。E6是顺序入栈，那么分析过程如下：
按照出栈过程分析，因为给定出栈顺序：E2,E4,E3,E6,E5,E1,
E2要进栈，所以E1必须进栈，进栈顺序：E1,E2，所以s为2
下面E2出栈，打印出E2，剩余结果为E4,E3,E6,E5,E1,
因为E2出栈了，所以当前栈容量为2，但是只是用了1个，存放E1，下面继续
E3进栈，E4进栈，此时s为3，根据出栈结果，那么E4出栈，E3出栈，此时栈容量为3
但是只有E1在栈中，剩余结果为E6,E5,E1,
同理，E5进栈，E6进栈，此时栈被填满，容量为3，后E6出栈，E5出栈，E1出栈，栈空，容量为3.所以S的容量至少为3.