为什么我们让元素从第2堆推回到第1堆

Question

最近，我遇到了一个关于如何使用2个堆栈构建队列的算法，如下所示：

方法1（通过增加排队操作的成本）：此方法确保最早输入的元素始终位于堆栈1的顶部，以便从堆栈1弹出排队操作。要将元素放置在stack1的顶部，使用stack2。

enQueue(q, x)
  1) While stack1 is not empty, push everything from stack1 to stack2.
  2) Push x to stack1 (assuming size of stacks is unlimited).
  3) Push everything back to stack1.
Here time complexity will be O(n)


deQueue(q)
  1) If stack1 is empty then error
  2) Pop an item from stack1 and return it
Here time complexity will be O(1)

现在这个算法是有意义的，除了第三点关于为什么我们要把所有东西都推回到堆栈1上。为什么我们不能使用堆栈2作为队列（在排队操作期间）

Answer 1

为什么所有的东西都被推到stack1上

这是由这样一个事实驱动的，即当您执行退出队列操作时，您会从堆栈1中弹出一个元素。

假设您有三个相同顺序的推送操作x1、x2、x3。由于出列操作总是从stack1开始，因此必须确保x1位于顶部，x2位于第二位，x3位于第三位。这只能通过第三点来确保。

在算法中，上面提到的入队和出队都在stack1上执行。

为什么我们不能使用堆栈2作为队列（在排队操作期间）

在这种情况下，您必须对堆栈1执行出列操作。

排队（q，x）：

1. 推到堆栈2。O（1）

出列（q）：

>

如果stack1不是空的，那么从stack1弹出。

如果stack1是空的

2.1如果stack2也为空，则抛出一个错误。

2.2将所有从stack2转移到stack1。现在从stack1弹出顶部。由于传输的元素数等于从stack1中弹出的元素数，卸载的摊销复杂度将为O（1）。