The max capacity of queue that is simulated by two stacks

今天在做面试题目的时候遇到了一道题：使用两个栈来模拟一个队列，栈1容量为m,栈2容量为n,且m>n,
请问这个队列的最大容量是多少？

初始状态:

• $S1.capacity() = m$
• $S2.capacity() = n$
• $Q.size() = 0$

假设$S1$用作队列入队的存储空间，$S2$用作队列出对的缓存空间。

1. 假设现在队列Q进入$n$个元素，如下面这个状态

   

2. 对应的，会在S1入栈$n$个元素

   

3. 将S1中的元素全部出栈，这n个元素被放入栈S2中

   

4. 假设现在再向队列Q中推入$n+1$个元素

   

5. 对应的，向栈S1中入栈$n+1$个元素

   

6. 此时进行出队操作，$E1\sim En$先出队列即：缓存栈S2中元素全部出栈

   

7. 接下来继续出队

   1. 先将S1中出栈n个元素到S2中

      

   2. 队列继续出栈

      1. $E_{n+1}$出队列，对应的栈$S1$出栈最后一个元素
      2. 队列中元素En+2到E2n+1出队，对应栈S2出栈所有元素

从以上操作中可以看出两个栈模拟出的队列的最大容量为$\color{blue}{2n+1}$。再对队列入队的话，就不能得到正常出队序列了。