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

是否可以仅使用两个堆栈来"构造"队列数据结构？

解决方案

回答

但是，时间复杂性会更糟。一个好的队列实现可以在固定时间内完成所有工作。

编辑

不知道为什么我的答案在这里被低估了。如果我们进行编程，我们会关心时间的复杂性，并且使用两个标准堆栈来创建队列效率很低。这是非常有效和相关的一点。如果其他人觉得有必要对此进行更多投票，我很想知道为什么。

更多细节：关于为什么使用两个堆栈比仅使用队列更糟糕的原因：如果使用两个堆栈，并且发件箱为空时有人呼叫出队，则需要线性时间才能到达收件箱的底部(如我们所见在Dave的代码中)。

我们可以将队列实现为单链接列表(每个元素都指向下一个插入的元素)，并保留指向最后插入的元素的额外指针以进行推送(或者使其成为循环列表)。在恒定的时间内非常容易在此数据结构上实现队列和出队。那是最坏的固定时间，没有摊销。而且，正如评论所要求的那样，最坏情况下的恒定时间严格比摊销的恒定时间要好。

回答

我们必须将所有内容从第一个堆栈中弹出，以获取底部元素。然后将它们全部放回第二个堆栈，以进行每个"出队"操作。

回答

保留2个堆栈，我们将其称为"收件箱"和"发件箱"。

入队：

• 将新元素推入"收件箱"

出队：

• 如果"发件箱"为空，则通过从"收件箱"中弹出每个元素并将其推到"发件箱"中来重新填充
• 弹出并从"发件箱"中返回顶部元素

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

这是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();
    }

}

回答

我们甚至可以只使用一个堆栈来模拟队列。可以通过对insert方法进行递归调用的调用堆栈来模拟第二个(临时)堆栈。

在队列中插入新元素时，原理保持不变：

• 我们需要将元素从一个堆栈转移到另一个临时堆栈，以颠倒它们的顺序。
• 然后将要插入的新元素推入临时堆栈
• 然后将元素转移回原始堆栈
• 新元素将位于堆栈的底部，而最旧的元素将位于堆栈的顶部(首先弹出)

仅使用一个Stack的Queue类如下：

public class SimulatedQueue<E> {
    private java.util.Stack<E> stack = new java.util.Stack<E>();

    public void insert(E elem) {
        if (!stack.empty()) {
            E topElem = stack.pop();
            insert(elem);
            stack.push(topElem);
        }
        else
            stack.push(elem);
    }

    public E remove() {
        return stack.pop();
    }
}