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

要了解如何使用两个堆栈构造队列,您应该了解如何反转堆栈清晰.记住堆栈是如何工作的,它非常类似于厨房的碟子堆栈.最后洗涤盘将在清洁堆栈的顶部,其被称作大号 AST 我 Ñ ˚F开始步骤ö在计算机科学UT(LIFO).

让我们想象我们的堆栈就像下面的瓶子;

如果我们分别推动整数1,2,3,那么3将位于堆栈的顶部.因为1会先被推,然后2将被放在1的顶部.最后,3将被放在堆栈的顶部,我们的堆栈的最新状态表示为一个瓶子将如下所示;

现在我们将表示为瓶子的堆栈填充值3,2,1.我们想要反转堆栈,使堆栈的顶部元素为1,堆栈的底部元素为3.我们能做什么？我们可以将瓶子倒置并将其倒置,以便所有值按顺序颠倒？

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

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

在前一部分中,我已经解释了如何反转堆栈元素的顺序.这很重要,因为如果我们将元素推送到堆栈,输出将完全按队列的相反顺序排列.想一个例子,让我们把整数数组推{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}

这是Java中的一个实现.我不打算使用Stack的现有实现,所以这里的例子将重新发明轮子;

public class MyStack {

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

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

    private Node head;
    private int size;

    public void push(T e) {
        Node 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 temp = head; temp != null; temp = temp.next)
                System.out.printf("%s ", temp.data);

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

public class MyQueue {

    private MyStack inputStack;      // for enqueue
    private MyStack 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;
    }

}

public class TestMyQueue {

    public static void main(String[] args) {
        MyQueue 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());
    }

}

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

您甚至可以仅使用一个堆栈来模拟队列.第二个(临时)堆栈可以通过对insert方法的递归调用的调用堆栈来模拟.

将新元素插入队列时,原则保持不变:

您需要将元素从一个堆栈传输到另一个临时堆栈,以反转它们的顺序.

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

然后将元素传回原始堆栈

新元素将位于堆栈的底部,最旧的元素位于顶部(首先被弹出)

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

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

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

但是,时间的复杂性会更糟.良好的队列实现可以在恒定时间内完成所有任

编辑

不知道为什么我的答案在这里被低估了.如果我们编程,我们关心时间复杂度,并使用两个标准堆栈来制作队列是低效的.这是一个非常有效和相关的观点.如果其他人觉得需要更多地投票,我会有兴趣知道原因.

更详细一点:为什么使用两个堆栈比一个队列更糟糕:如果你使用两个堆栈,而有人在发件箱为空时调用出队,你需要线性时间到达收件箱的底部(如你所见)在戴夫的代码中).

您可以将队列实现为单链接列表(每个元素指向下一个插入的元素),保留指向最后插入元素的额外指针以进行推送(或使其成为循环列表).在此数据结构上实现队列和出列很容易在恒定时间内完成.这是最坏情况下的常数时间,而非摊销.而且,由于评论似乎要求澄清,最坏情况下的常数时间绝对优于摊销的常数时间.

让队列实现为q,用于实现q的栈是stack1和stack2.

q可以通过两种方式实现:

方法1(通过使enQueue操作成本高昂)

此方法确保新输入的元素始终位于堆栈1的顶部,因此deQueue操作只是从stack1弹出.要将元素放在stack1的顶部,使用stack2.

enQueue(q, x)
1) While stack1 is not empty, push everything from stack1 to stack2.
2) Push x to stack1 (assuming size of stacks is unlimited).
3) Push everything back to stack1.
deQueue(q)
1) If stack1 is empty then error
2) Pop an item from stack1 and return it.

方法2(通过使deQueue操作成本高昂)

在此方法中,在队列操作中,新元素输入stack1的顶部.在去队列操作中,如果stack2为空,则将所有元素移动到stack2,最后返回stack2的顶部.

enQueue(q,  x)
 1) Push x to stack1 (assuming size of stacks is unlimited).

deQueue(q)
 1) If both stacks are empty then error.
 2) If stack2 is empty
   While stack1 is not empty, push everything from stack1 to stack2.
 3) Pop the element from stack2 and return it.

方法2肯定比​​方法1好.方法1在enQueue操作中移动所有元素两次,而方法2(在deQueue操作中)移动元素一次并仅在stack2为空时移动元素.