Wie implementiert man eine Warteschlange mit zwei Stapeln?

Question

Angenommen, wir haben zwei Stapel und keine andere temporäre Variable.

Ist es möglich, eine Warteschlangen-Datenstruktur nur mit den beiden Stapeln zu "konstruieren"?

Answer 1

Behalten Sie 2 Stapel, nennen wir sie inbox y outbox .

Enqueue :

• Schieben Sie das neue Element auf inbox

Dequeue :

• Si outbox leer ist, füllen Sie es wieder auf, indem Sie jedes Element aus inbox und schiebt sie auf outbox

• Pop und Rückgabe des obersten Elements von outbox

Bei dieser Methode befindet sich jedes Element genau einmal in jedem Stapel, d. h. jedes Element wird zweimal geschoben und zweimal gepoppt, so dass sich die Operationen in konstanter Zeit amortisieren.

Hier ist eine Implementierung 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();
    }

}

Answer 2

A - Wie man einen Stapel umkehrt

Um zu verstehen, wie man eine Warteschlange mit zwei Stapeln aufbaut, sollte man wissen, wie man einen Stapel glasklar umkehrt. Erinnern Sie sich daran, wie ein Stapel funktioniert, er ist dem Geschirrstapel in Ihrer Küche sehr ähnlich. Das zuletzt gewaschene Geschirr steht oben auf dem sauberen Stapel, den man als L ast I n F irst O ut (LIFO) in der Informatik.

Stellen wir uns unseren Stapel wie eine Flasche vor, wie unten dargestellt;

Wenn wir die Zahlen 1, 2 und 3 einfügen, liegt 3 oben auf dem Stapel. Da 1 zuerst geschoben wird, wird 2 auf 1 gelegt. Schließlich wird 3 auf die Spitze des Stapels gelegt und der letzte Zustand unseres Stapels, der als Flasche dargestellt wird, ist wie unten;

Jetzt haben wir unseren Stapel als Flasche dargestellt, die mit den Werten 3,2,1 gefüllt ist. Und wir wollen den Stapel umkehren, so dass das oberste Element des Stapels die 1 und das unterste Element des Stapels die 3 sein wird. Was können wir tun? Wir können die Flasche nehmen und sie auf den Kopf stellen, so dass alle Werte in umgekehrter Reihenfolge erscheinen?

Ja, das können wir tun, aber das ist eine Flasche. Um den gleichen Prozess durchzuführen, brauchen wir einen zweiten Stapel, der die Elemente des ersten Stapels in umgekehrter Reihenfolge speichert. Legen wir unseren gefüllten Stapel nach links und unseren neuen leeren Stapel nach rechts. Um die Reihenfolge der Elemente umzukehren, werden wir jedes Element aus dem linken Stapel herausnehmen und in den rechten Stapel schieben. Was dabei passiert, können Sie im folgenden Bild sehen;

Wir wissen also, wie man einen Stapel umdreht.

B - Verwendung von zwei Stapeln als Warteschlange

Im vorherigen Teil habe ich erklärt, wie man die Reihenfolge der Stack-Elemente umkehren kann. Das war wichtig, denn wenn wir Elemente auf den Stapel schieben und wieder herausnehmen, wird die Ausgabe genau in der umgekehrten Reihenfolge einer Warteschlange erfolgen. Nehmen wir ein Beispiel und schieben wir das Array der ganzen Zahlen {1, 2, 3, 4, 5} auf einen Stapel. Wenn wir die Elemente auspacken und ausdrucken, bis der Stapel leer ist, erhalten wir das Array in der umgekehrten Reihenfolge der Einschubreihenfolge, also {5, 4, 3, 2, 1} Denken Sie daran, dass die Ausgabe für dieselbe Eingabe, wenn wir die Warteschlange dequeuen, bis die Warteschlange leer ist, wie folgt aussieht {1, 2, 3, 4, 5} . Es ist also offensichtlich, dass die Ausgabe der Warteschlange bei gleicher Eingabereihenfolge der Elemente genau umgekehrt ist wie die Ausgabe eines Stapels. Da wir wissen, wie man einen Stapel mit einem zusätzlichen Stapel umkehren kann, können wir eine Warteschlange mit zwei Stapeln konstruieren.

Unser Warteschlangenmodell wird aus zwei Stapeln bestehen. Ein Stapel wird verwendet für enqueue Operation (Stapel Nr. 1 auf der linken Seite, wird als Eingabestapel bezeichnet), ein anderer Stapel wird für die dequeue Operation (Stapel Nr. 2 auf der rechten Seite, wird als Ausgabestapel bezeichnet). Sehen Sie sich das Bild unten an;

Unser Pseudocode sieht wie folgt aus;

---

Enqueue-Vorgang

Push every input element to the Input Stack

Dequeue-Vorgang

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

---

Lassen Sie uns die ganzen Zahlen in die Warteschlange stellen {1, 2, 3} beziehungsweise. Ganzzahlen werden auf der Eingangsstapel ( Stapel 1 ), die sich auf der linken Seite befindet;

Was wird dann passieren, wenn wir eine Dequeue-Operation ausführen? Immer wenn eine Dequeue-Operation ausgeführt wird, prüft die Warteschlange, ob der Ausgabestapel leer ist oder nicht (siehe Pseudocode oben). Wenn der Ausgabestapel leer ist, wird der Eingabestapel am Ausgang extrahiert, so dass die Elemente des Eingabestapels umgekehrt werden. Bevor ein Wert zurückgegeben wird, wird der Zustand der Warteschlange wie unten dargestellt;

Achten Sie auf die Reihenfolge der Elemente im Ausgabestapel (Stapel Nr. 2). Es ist offensichtlich, dass wir die Elemente aus dem Ausgabestapel herausnehmen können, so dass die Ausgabe dieselbe ist, wie wenn wir sie aus einer Warteschlange herausnehmen. Wenn wir also zwei Dequeue-Operationen ausführen, erhalten wir zunächst {1, 2} beziehungsweise. Dann ist das Element 3 das einzige Element des Ausgabestapels, und der Eingabestapel ist leer. Wenn wir die Elemente 4 und 5 in die Warteschlange stellen, sieht der Zustand der Warteschlange wie folgt aus;

Jetzt ist der Ausgabestapel nicht leer, und wenn wir eine Dequeue-Operation ausführen, werden nur 3 aus dem Ausgabestapel herausgenommen. Dann sieht der Zustand wie unten dargestellt aus;

Wenn wir zwei weitere Dequeue-Operationen ausführen, prüft die Warteschlange bei der ersten Dequeue-Operation, ob der Ausgabestapel leer ist, was der Fall ist. Dann werden die Elemente des Eingabestapels entnommen und in den Ausgabestapel geschoben, bis der Eingabestapel leer ist, dann sieht der Zustand der Warteschlange wie folgt aus;

Es ist leicht zu erkennen, dass die Ausgabe der beiden Dequeue-Operationen wie folgt aussehen wird {4, 5}

C - Implementierung einer mit zwei Stapeln aufgebauten Warteschlange

Hier ist eine Implementierung in Java. Ich werde nicht die bestehende Implementierung von Stack verwenden, so dass das Beispiel hier das Rad neu erfinden wird;

C - 1) Klasse MyStack: Eine einfache Stack-Implementierung

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) Klasse MyQueue: Implementierung einer Warteschlange mit zwei Stapeln

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) Demo-Code

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) Beispielhafte Ausgabe

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

Answer 3

Sie können sogar eine Warteschlange mit nur einem Stapel simulieren. Der zweite (temporäre) Stapel kann durch den Aufrufstapel der rekursiven Aufrufe der Insert-Methode simuliert werden.

Das Prinzip bleibt dasselbe, wenn ein neues Element in die Warteschlange eingefügt wird:

• Sie müssen Elemente von einem Stapel auf einen anderen temporären Stapel übertragen, um ihre Reihenfolge umzukehren.
• Dann schieben Sie das neue Element, das eingefügt werden soll, auf den temporären Stapel
• Übertragen Sie dann die Elemente zurück in den ursprünglichen Stapel
• Das neue Element befindet sich am unteren Ende des Stapels, und das älteste Element liegt oben (es wird als erstes entnommen).

Eine Warteschlangenklasse, die nur einen Stapel verwendet, würde wie folgt aussehen:

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

Answer 4

Die zeitliche Komplexität wäre allerdings noch größer. Eine gute Implementierung einer Warteschlange erledigt alles in konstanter Zeit.

bearbeiten

Ich weiß nicht, warum meine Antwort hier heruntergestuft wurde. Wenn wir programmieren, ist uns die Zeitkomplexität wichtig, und die Verwendung von zwei Standardstapeln zur Bildung einer Warteschlange ist ineffizient. Das ist ein sehr gültiger und relevanter Punkt. Wenn jemand anderes das Bedürfnis hat, dies weiter herunterzustufen, würde es mich interessieren, warum.

Ein wenig mehr Details : Warum die Verwendung von zwei Stapeln schlimmer ist als eine Warteschlange: Wenn Sie zwei Stapel verwenden und jemand dequeue aufruft, während der Postausgang leer ist, benötigen Sie lineare Zeit, um an das Ende des Posteingangs zu gelangen (wie Sie in Daves Code sehen können).

Sie können eine Warteschlange als einfach verknüpfte Liste implementieren (jedes Element verweist auf das nächste eingefügte Element), wobei ein zusätzlicher Zeiger auf das zuletzt eingefügte Element für Pushvorgänge beibehalten wird (oder Sie machen daraus eine zyklische Liste). Die Implementierung von Queue und Dequeue auf dieser Datenstruktur ist sehr einfach und in konstanter Zeit zu bewerkstelligen. Das ist im schlimmsten Fall konstante Zeit, nicht amortisiert. Und da in den Kommentaren anscheinend um diese Klarstellung gebeten wird, ist konstante Zeit im schlimmsten Fall unbedingt besser als amortisierte konstante Zeit.

Answer 5

Die zu implementierende Warteschlange sei q und die zur Implementierung von q verwendeten Stapel seien stack1 und stack2.

q kann implementiert werden in zwei Möglichkeiten:

Methode 1 (enQueue-Operation kostspielig machen)

Diese Methode stellt sicher, dass ein neu eingegebenes Element immer ganz oben auf Stack 1 liegt, so dass die deQueue-Operation nur von Stack1 abgerufen wird. Um das Element an die Spitze von Stack1 zu setzen, wird Stack2 verwendet.

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.

Methode 2 (deQueue-Operation kostspielig machen)

Bei dieser Methode wird das neue Element in der Warteschlange ganz oben auf Stack1 eingetragen. Bei der De-Queue-Operation werden, wenn Stack2 leer ist, alle Elemente auf Stack2 verschoben, und schließlich wird der oberste Punkt von Stack2 zurückgegeben.

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.

Methode 2 ist definitiv besser als Methode 1. Methode 1 verschiebt alle Elemente zweimal in der enQueue-Operation, während Methode 2 (in der deQueue-Operation) die Elemente einmal verschiebt und nur dann verschiebt, wenn stack2 leer ist.