单选题 栈S和队列Q的初始状态皆为空，元素a1，a2，a3，a4，a5和a6依次通过S栈，一个元素出栈后即进入队列Q，若6个元素出队列的顺序是a3，a4，a2，a1，a5，a6，则栈S至少应该容纳______个元素。
  • A.6
  • B.4
  • C.3
  • D.2
【正确答案】 C
【答案解析】[解析] 模拟一下入栈出栈过程，如下表。选取模拟过程中栈内元素个数最大的值，便为该题答案，因此本题选C。
操作 栈 输出
push a1
push a1、a2
push a1、a2
pop a1、a2 a3
push a1、a2、a4 a3
pop a1、a2 a3、a4
pop a1 a3、a4、a2
pop a3、a4、a2、a1
push a5 a3、a4、a2、a1
pop a3、a4、a2、a1、a5
push a6 a3、a4、a2、a1、a5
pop a3、a4、a2、a1、a5、a6