数据结构的一道题

Question

设栈 S和队列Q的初始状态为空，元素 a b c d e f g依次进栈 S 。若每个元素出站后立即进去入队列Q ,且7个元素出队顺序是b d c f e a g则栈 S的容量至少多少？ 这是数据结构的题。 给步骤详细点啊。答案是3

Answer 1

首先明确几个概念：栈是先进后出，队列是先进先出；题目中指定了进栈顺序，但没说要连续进栈。(下面箭头图中右代表栈底，左代表栈顶，队列同样)
假如栈的容量是1，则第一个出栈的肯定是a，不符合；
假如栈的容量是2，则a、b进去，b出栈，c进栈，只能c先出栈，d不可能出队顺序在c前
假如栈的容量是3，分析过程如下：
①S：b→a，b出栈，Q：b，S：a
②S：d→c→a，d、c依次出栈，Q：c→d→b，S：a
③S：f→e→a，f、e、a依次出栈，Q：a→e→f→c→d→b，S：null
④S：g，g出栈，Q：g→a→e→f→c→d→b，S：null
Q中元素依次出队，即b→d→c→f→e→a→g

Answer 2

队列的特点是先进先出，所以根据队列的出对顺序可以知道 进队列去的元素顺序是 bdcfeag 。接着看元素进入栈，可以知道 a 进去 b 进去 b出来，（出来后入队，后同）此时容量为二，b出来后b的位置空出，c进去，d进去，此时容量为3，根据队列可以知道，接着d出来，c出来。栈里空出两个位置。然后e进去，f进去，（容量仍然是3）f出来，e出来，此时又空出两个位置，然后a出来，g进去 g出来。整个过程就是这样。所以s的容量至少3