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

Question

假设我们有两个堆栈并且没有其他临时变量。

是否可以仅使用两个堆栈来“构建”队列数据结构？

Answer 1

保留 2 个堆栈，我们称它们为 inbox 和 outbox。

排队:

• 将新元素推送到收件箱

出列:

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

  /li>

• 从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();
    }

}