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

问题描述

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

Suppose we have two stacks and no other temporary variable.

是否可能只使用两个堆栈构造队列数据结构？

Is to possible to "construct" a queue data structure using only the two stacks?

推荐答案

保留2个堆栈，让我们称之为收件箱和发件箱。

Keep 2 stacks, let's call them inbox and outbox.

入队：

• 将新元素推入收件箱

• Push the new element onto inbox

出队

Dequeue:

• 如果发件箱为空，请重新填写通过从收件箱中弹出每个元素，并将其推送到发件箱

• If outbox is empty, refill it by popping each element from inbox and pushing it onto outbox

流行并从发件箱返回顶部元素

使用此方法，每个元素将在每个堆栈中完全一次 - 这意味着每个元素将被推送两次并弹出两次，从而获得摊销的常数时间操作。

Using this method, each element will be in each stack exactly once - meaning each element will be pushed twice and popped twice, giving amortized constant time operations.

Java中的一个实现：

Here's an implementation in 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();
    }

}

这篇关于如何使用两个堆栈实现队列？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！