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

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

---

保留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();
    }

}

---

A - 如何反转堆栈

要了解如何使用两个堆栈构建队列，您应该了解如何将透明堆栈反转。 请记住堆叠是如何工作的，它与厨房的盘子非常相似。 最后洗涤盘将在清洁堆栈的顶部，其被称作计算机科学大号 AST I N 开始步骤øUT（LIFO）。

让我们想像我们的堆栈像一个瓶子如下;

如果我们分别推入整数1,2,3，那么3将位于堆栈顶部。 因为1会先被推动，然后2会被放在1的顶部。最后，3将被放在堆栈的顶部，并且我们的堆栈的最新状态将如下所示;

现在我们将我们的堆栈表示为一个瓶子，其值为3,2,1。 我们想要反转堆栈，以使堆栈的顶层元素为1，堆栈的底层元素为3.我们可以做什么？ 我们可以拿起瓶子并倒过来，这样所有的数值都应该颠倒过来？

是的，我们可以做到这一点，但这是一个瓶子。 为了做同样的过程，我们需要第二个堆栈，它将以相反的顺序存储第一个堆栈元素。 让我们把我们填充的堆栈放到左边，我们新的空堆栈放在右边。 为了颠倒这些元素的顺序，我们将弹出左堆栈中的每个元素，并将它们推送到正确的堆栈。 你可以看到下面的图片会发生什么，

所以我们知道如何反转堆栈。

B - 使用两个栈作为队列

在前面的部分中，我已经解释了如何颠倒堆栈元素的顺序。 这很重要，因为如果我们将元素推送到堆栈并将其弹出，则输出将与队列完全相反。 以一个例子为例，让我们将整数数组{1, 2, 3, 4, 5}推入堆栈。 如果我们弹出元素并打印它们直到堆栈为空，我们将按照推送顺序的相反顺序获取数组，这将是{5, 4, 3, 2, 1}请记住，对于相同的输入，如果我们将队列出队，直到队列为空，输出将为{1, 2, 3, 4, 5} 。 所以很显然，对于相同的元素输入顺序，队列的输出与堆栈的输出完全相反。 由于我们知道如何使用额外的堆栈来反转堆栈，我们可以使用两个堆栈来构建一个队列。

我们的队列模型将由两个堆栈组成。 一个堆栈将用于enqueue操作（堆栈＃1在左边，将被称为输入堆栈），另一个堆栈将用于dequeue操作（堆栈＃2在右边，将被称为输出堆栈）。 看看下面的图片;

我们的伪代码如下所示;

---

入队操作

Push every input element to the Input Stack

出队操作

If ( Output Stack is Empty)
    pop every element in the Input Stack
    and push them to the Output Stack until Input Stack is Empty

pop from Output Stack

---

让我们分别排列整数{1, 2, 3} 。 整数将被压入位于左侧的输入堆栈 （ 堆栈＃1 ）;

那么如果我们执行一个出队操作会发生什么？ 无论何时执行出队操作，队列都将检查输出堆栈是否为空（请参阅上面的伪代码）。如果输出堆栈为空，则将在输出中提取输入堆栈，以便元素输入堆栈将被颠倒。 在返回值之前，队列的状态如下所示;

检查输出堆栈（堆栈＃2）中元素的顺序。 很显然，我们可以从输出堆栈弹出元素，以便输出与从队列中出队时相同。 因此，如果我们执行两个出队操作，首先我们将分别得到{1, 2} 。 然后元素3将是输出堆栈的唯一元素，并且输入堆栈将为空。 如果我们排队元素4和5，那么队列的状态将如下;

现在输出堆栈不是空的，如果我们执行出队操作，则只有3个会从输出堆栈弹出。 那么国家将被视为如下。

同样，如果我们再执行两次出队操作，则在第一次出队操作时，队列将检查输出堆栈是否为空，这是真的。 然后弹出输入堆栈的元素并将它们推送到输出堆栈，直到输入堆栈为空，那么队列的状态如下所示;

很容易看到，两个出队操作的输出将是{4, 5}

C - 构造两个栈的队列的实现

这是Java中的一个实现。 我不打算使用Stack的现有实现，因此这里的示例将重新发明轮子;

C - 1）MyStack类：简单堆栈实现

public class MyStack<T> {

    // inner generic Node class
    private class Node<T> {
        T data;
        Node<T> next;

        public Node(T data) {
            this.data = data;
        }
    }

    private Node<T> head;
    private int size;

    public void push(T e) {
        Node<T> newElem = new Node(e);

        if(head == null) {
            head = newElem;
        } else {
            newElem.next = head;
            head = newElem;     // new elem on the top of the stack
        }

        size++;
    }

    public T pop() {
        if(head == null)
            return null;

        T elem = head.data;
        head = head.next;   // top of the stack is head.next

        size--;

        return elem;
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public void printStack() {
        System.out.print("Stack: ");

        if(size == 0)
            System.out.print("Empty !");
        else
            for(Node<T> temp = head; temp != null; temp = temp.next)
                System.out.printf("%s ", temp.data);

        System.out.printf("n");
    }
}

C - 2）MyQueue类：使用两个堆栈实现队列

public class MyQueue<T> {

    private MyStack<T> inputStack;      // for enqueue
    private MyStack<T> outputStack;     // for dequeue
    private int size;

    public MyQueue() {
        inputStack = new MyStack<>();
        outputStack = new MyStack<>();
    }

    public void enqueue(T e) {
        inputStack.push(e);
        size++;
    }

    public T dequeue() {
        // fill out all the Input if output stack is empty
        if(outputStack.isEmpty())
            while(!inputStack.isEmpty())
                outputStack.push(inputStack.pop());

        T temp = null;
        if(!outputStack.isEmpty()) {
            temp = outputStack.pop();
            size--;
        }

        return temp;
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

}

C - 3）演示代码

public class TestMyQueue {

    public static void main(String[] args) {
        MyQueue<Integer> queue = new MyQueue<>();

        // enqueue integers 1..3
        for(int i = 1; i <= 3; i++)
            queue.enqueue(i);

        // execute 2 dequeue operations 
        for(int i = 0; i < 2; i++)
            System.out.println("Dequeued: " + queue.dequeue());

        // enqueue integers 4..5
        for(int i = 4; i <= 5; i++)
            queue.enqueue(i);

        // dequeue the rest
        while(!queue.isEmpty())
            System.out.println("Dequeued: " + queue.dequeue());
    }

}

C - 4）样本输出

Dequeued: 1
Dequeued: 2
Dequeued: 3
Dequeued: 4
Dequeued: 5

---

你甚至可以使用一个堆栈模拟一个队列。 第二个（临时）堆栈可以通过递归调用insert方法的调用堆栈模拟。

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

您需要将元素从一个堆栈传输到另一个临时堆栈，以颠倒它们的顺序。

然后将要插入的新元素推入临时堆栈

然后将元素传回原始堆栈

新元素将位于堆栈的底部，而最早的元素位于顶部（首先被弹出）

一个Queue类只使用一个Stack，如下所示：

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

链接地址: http://www.djcxy.com/p/39841.html

上一篇: How to implement a queue using two stacks?

下一篇: What's the difference between Program Fixpoint and Function in Coq?