如何使用两个堆栈实现队列？

Question

假设我们有两个堆栈，没有其他临时变量。是否可以仅使用两个堆栈来“构造”队列数据结构？

Answer 1

保留2叠，我们称它们为inbox和outbox。

入队：

将新元素推到 inbox

出队：

如果outbox为空，则通过从中弹出每个元素inbox并将其推入来重新填充它outbox

弹出并从返回顶部元素 outbox

使用此方法，每个元素将在每个堆栈中恰好出现一次-意味着每个元素将被推入两次并弹出两次，从而提供了摊销的固定时间操作。

这是Java的实现：

public class Queue<E>

{

    private Stack<E> inbox = new Stack<E>();

    private Stack<E> outbox = new Stack<E>();

    public void queue(E item) {

        inbox.push(item);

    }

    public E dequeue() {

        if (outbox.isEmpty()) {

            while (!inbox.isEmpty()) {

               outbox.push(inbox.pop());

            }

        }

        return outbox.pop();

    }

}