如何实现用两叠一个队列？ [英] How to implement a queue using two stacks?

问题描述

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

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.

队列：
  - 将新元素添加到收件箱

Queue:
- Push the new element onto inbox

出列：
  - 如果发件箱是空的，由收件箱弹出的每个元素，将其推到斟满发件箱
  - 弹出并从返回的顶级元素发件箱

Dequeue:
- If outbox is empty, refill it by popping each element from inbox and pushing it onto outbox
- Pop and return the top element from 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();
    }

}

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