Wie implementiert man eine Warteschlange mit zwei Stapeln?

In dieser Kolumne wird erläutert, wie Sie zwei Stapel zum Implementieren einer Warteschlange verwenden.

Warteschlange und Stapel sind zwei sehr wichtige Datenstrukturen in Computern („Warteschlange“, „Stapel“). Wir kennen ihre jeweiligen Eigenschaften Beim Stapel handelt es sich um FILO (First In, Last Out). Wie kann man den Stapel also verwenden, um eine Warteschlange zu implementieren? Dies ist eine klassische Interviewfrage, daher werden wir sie in diesem Artikel umsetzen. Bevor wir offiziell beginnen, werfen wir einen Blick auf die gängigen Methoden von Stapeln und Warteschlangen. Zu den häufig verwendeten Methoden von Stack gehören die folgenden: push(): Push-Methode, Elemente oben im Stapel hinzufügen;

pop(): Pop-Methode, Elemente oben im Stapel entfernen und Elemente zurückgeben ;

peek(): Fragt das oberste Element des Stapels ab und entfernt das Element nicht.

Zu den häufig verwendeten Methoden der Warteschlange gehören die folgenden:

• offer(): Einreihmethode, Hinzufügen von Elementen am Ende der Warteschlange;
• poll(): Entnahmemethode, Entfernen und Entfernen von Elementen aus dem Kopf der Warteschlange Das Element zurückgeben;
• peek(): Fragt das Kopfelement der Warteschlange ab und entfernt das Element nicht.

Mit diesem Vorwissen schauen wir uns das heutige Thema an.

Problembeschreibung

• Verwenden Sie zwei Stapel, um eine Warteschlange zu implementieren. Die Warteschlange wird wie folgt deklariert. Bitte implementieren Sie ihre beiden Funktionen appendTail und deleteHead, um die Funktionen des Einfügens einer Ganzzahl am Ende der Warteschlange bzw. des Löschens einer Ganzzahl am Kopf der Warteschlange abzuschließen Warteschlange gibt die deleteHead-Operation -1 zurück.
• Beispiel 1:
• Eingabe:

["CQueue","appendTail","deleteHead","deleteHead"]

[[],[3],[],[]]

Ausgabe: [ null,null,3,-1]

Beispiel 2:

Eingabe:

["CQueue", "deleteHead", "appendTail", "appendTail", "deleteHead", "deleteHead"]

[[],[],[5],[2],[],[]]

Ausgabe: [null,-1,null,null,5,2]

Tipps:

1

Bis zu 10000 Aufrufe von appendTail und deleteHead

leetcode: leetcode-cn.com/problems/yo…

Ideen zur Problemlösung

Die Bedeutung dieser Frage ist eigentlich sehr leicht zu verstehen, nämlich den First-in-Last-out-Stapel in einen First-in-Last-Out-Stapel zu ändern. Tatsächlich wird dies auch in der Frage „Verwenden Sie zwei Stapel, um eine Warteschlange zu implementieren“ angegeben. Die Kernidee dieser Frage ist „Ein Negativ ergibt ein Positiv“. Wir verwenden zunächst einen Stapel, um Elemente zu speichern (zu diesem Zeitpunkt befindet sich das erste eingegebene Element am unteren Rand des Stapels) und verschieben es dann Das Element im ersten Stapel wird in den neuen Stapel verschoben. Das zu diesem Zeitpunkt zuerst eingegebene Element befindet sich oben im Stapel. Wenn der zweite Stapel zum Herausspringen verwendet wird, wird die gesamte Ausführungsreihenfolge als „First-In, First“ festgelegt -aus.

Als nächstes setzen wir den gesamten Prozess grafisch um.

Schritt 1

Schieben Sie zuerst die Elemente in den ersten Stapel, wie in der Abbildung unten gezeigt:

Schritt 2

Verschieben Sie alle Elemente im ersten Stapel in den zweiten Stapel, wie in der Abbildung unten gezeigt. Zeigen Sie:

Schritt 3

Alle Elemente werden aus dem zweiten Stapel entnommen, wie in der Abbildung unten gezeigt:

Zusammenfassung

Wie aus dem obigen Bild ersichtlich ist, ist die Reihenfolge beim Hinzufügen von Elementen 1, 2, 3, und schließlich nach Die Reihenfolge des Aufspringens nach den beiden Stapeln ist ebenfalls 1, 2, 3, sodass wir die Warteschlange (zuerst rein, zuerst raus) über zwei Stapel implementieren.

Implementierungscode

Als nächstes werden wir Code verwenden, um die oben genannten Ideen zu implementieren:

class CQueue {
    Stack<integer> inputStack; // 入栈的容器（添加时操作)
    Stack<integer> outputStack; // 出栈和查询的栈容器

    public CQueue() {
        inputStack = new Stack();
        outputStack = new Stack();
    }    // 添加操作
    public void appendTail(int value) {
        inputStack.push(value);
    }    // 删除操作
    public int deleteHead() {        if (!outputStack.isEmpty()) {            // 出栈容器不为空
            return outputStack.pop();
        } else if (!inputStack.isEmpty()) {            // 入栈 stack 全部转移到出栈 stack
            while (!inputStack.isEmpty()) {
                outputStack.push(inputStack.pop());
            }
        }        return outputStack.isEmpty() ? -1 : outputStack.pop();
    }
}复制代码</integer></integer>

Wir haben den obigen Testcode in LeetCode übermittelt und die Ausführungsergebnisse sind wie folgt:

Hinweise

Es gibt zwei in der gesamter Implementierungsprozess Kleine Details erfordern besondere Aufmerksamkeit:

1. Der erste Stapel ist nur für das Pushen (vorübergehendes Speichern von Daten) verantwortlich, und der zweite Stapel ist nur für das Knallen verantwortlich (die letzte Ausführungssequenz der Warteschlange);
2. Jedes Mal ist Stapel 2 zuständig Wenn nicht alle Daten in Stapel 2 entfernt wurden, können die Elemente von Stapel 1 nicht in Stapel 2 verschoben werden. Dies führt dazu, dass neue Daten aus Stapel 1 angehängt (hinzugefügt) werden Die Elemente zur Ausführungsreihenfolge sind verwirrend.

Zusammenfassung

In diesem Artikel verwenden wir zwei First-In-Last-Out-Stapel und implementieren die First-In-First-Out-Funktion der Warteschlange durch die Idee „Negative machen Positive“. Beim Öffnen des zweiten Stapels sollte besonders darauf geachtet werden, dass die Elemente im ersten Stapel nicht zum zweiten Stapel hinzugefügt werden können, um eine Verwechslung der Programmausführungsreihenfolge zu vermeiden.

Verwandte kostenlose Lernempfehlungen: Java-Grundlagen-Tutorial

Das obige ist der detaillierte Inhalt vonWie implementiert man eine Warteschlange mit zwei Stapeln?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!