Implement Queue Using Stacks

+10

Erstelle eine FIFO-Warteschlange, deren einziger Speicher aus zwei Stapeln besteht. Ein Stapel darf ein Element nur oben hinzufügen, das oberste Element entfernen, das oberste Element lesen und angeben, ob er leer ist. Die Warteschlange unterstützt push x (fügt x hinten hinzu), pop (entfernt das vorderste Element und gibt es zurück), peek (gibt das vorderste Element zurück) und empty (ist die Warteschlange leer?).

Du erhältst die Operationen der Reihe nach in ops, wobei args[i] den Wert für ein push und 0 für jede andere Operation enthält. Führe sie auf einer Warteschlange aus, die anfangs leer ist, und gib für jede Operation einen String zurück: "null" für ein push, die Zahl als Text für ein pop oder peek und "true" oder "false" für empty.

Funktion

queueOps(ops: string-array, args: integer-array) → string-array

opsstring-array: die Operationen in der Reihenfolge, in der sie ausgeführt werden
argsinteger-array: der Wert für jeden Push, 0 für jede andere Operation
Gibt zurückstring-array: eine Antwort pro Operation, als Text

Einschränkungen

1 ≤ ops.length ≤ 2000
args.length == ops.length
Jedes ops[i] ist push, pop, peek oder empty.
-10⁹ ≤ args[i] ≤ 10⁹ bei einem Push und args[i] == 0 bei jeder anderen Operation.
pop und peek werden nur aufgerufen, wenn die Warteschlange mindestens ein Element enthält.

Beispiele

Eingabe: ops = ["push", "push", "peek", "pop", "empty"]args = [1, 2, 0, 0, 0]
Ausgabe: ["null", "null", "1", "1", "false"]
Erklärung: Nachdem 1 und dann 2 eingefügt wurden, ist 1 vorne, also geben peek und pop beide "1" zurück. Die 2 ist noch enthalten, daher gibt empty "false" zurück.

Eingabe: ops = ["push", "push", "pop", "push", "pop", "pop", "empty"]args = [4, 7, 0, 9, 0, 0, 0]
Ausgabe: ["null", "null", "4", "null", "7", "9", "true"]
Erklärung: Das erste Entfernen gibt 4 zurück, das älteste Element. 9 kommt hinzu, während 7 noch wartet, und wird nach 7 ausgegeben, weil es danach hinzugekommen ist. Die Warteschlange ist dann leer, also lautet die letzte Antwort "true".

Eingabe: ops = ["empty", "push", "peek", "pop", "empty"]args = [0, -3, 0, 0, 0]
Ausgabe: ["true", "null", "-3", "-3", "true"]
Erklärung: Die Warteschlange ist anfangs leer, daher lautet die erste Antwort "true". Eine negative Zahl wird wie jede andere gespeichert: peek und pop geben beide "-3" zurück, und danach ist die Warteschlange wieder leer.

+15 versteckte Tests beim Einreichen

Weiterführende Frage

Wie würdest du eine back-Operation hinzufügen, die das neueste Element in O(1) zurückgibt, ohne die amortisierte Schranke der anderen Operationen zu verletzen?

Lösung

Ein Stapel gibt Elemente in der umgekehrten Reihenfolge zurück, in der sie hinzugefügt wurden, eine Warteschlange hingegen in derselben Reihenfolge. Wenn man einen Stapel in einen zweiten Stapel umfüllt, wird die Reihenfolge erneut umgekehrt, wodurch aus der Stapelreihenfolge eine Warteschlangenreihenfolge wird. Die entscheidende Frage ist, wann umgefüllt werden soll: Bei jeder Operation kostet das jedes Mal O(n), während beim Umfüllen erst dann, wenn der zweite Stapel leer ist, jedes Element nur einmal verschoben wird.

Ordne bei jedem Push den gesamten Stack neu

Idee

Bewahre alle Elemente in einem Stapel, main, auf, angeordnet so, dass das älteste Element oben liegt. Dann sind pop, peek und empty einzelne Stapeloperationen.

Der Aufwand entfällt auf push. Ein neues Element gehört nach unten, unter alles, was bereits wartet, und ein Stapel kann nur oben etwas hinzufügen. Verschiebe also alle Elemente von main auf den zweiten Stapel, helper, lege das neue Element auf den leeren main und verschiebe alles zurück. Jede Verschiebung kehrt die Reihenfolge um, zwei Verschiebungen stellen sie wieder her, und das neue Element landet ganz unten.

Das ist korrekt, aber bei jedem Push wird jedes gespeicherte Element zweimal bewegt. Das Pushen von 1.000 Elementen hintereinander kostet etwa 2 × (0 + 1 + ... + 999), also fast eine Million Verschiebungen, während eine echte Warteschlange 1.000 Schritte benötigt.

Algorithmus

Verwende zwei Stapel: main mit dem ältesten Element oben und einen leeren helper.
Für push x: Lege jedes Element von main auf helper, lege x auf main und lege dann jedes Element von helper zurück auf main.
Für pop und peek: Entferne das oberste Element von main oder lies es aus.
Für empty: Gib an, ob main leer ist.
Halte jede Antwort als Text fest und gib die Liste zurück.

class TwoStackQueue:
    def __init__(self):
        self.main = []    # the oldest item is on top
        self.helper = []

    def push(self, x):
        # Move everything aside, put x at the bottom, move everything back.
        while self.main:
            self.helper.append(self.main.pop())
        self.main.append(x)
        while self.helper:
            self.main.append(self.helper.pop())

    def pop(self):
        return self.main.pop()

    def peek(self):
        return self.main[-1]

    def empty(self):
        return not self.main


def queueOps(ops, args):
    queue = TwoStackQueue()
    result = []
    for op, arg in zip(ops, args):
        if op == "push":
            queue.push(arg)
            result.append("null")
        elif op == "pop":
            result.append(str(queue.pop()))
        elif op == "peek":
            result.append(str(queue.peek()))
        else:
            result.append("true" if queue.empty() else "false")
    return result

Inbox- und Outbox-Stacks mit verzögerter Übertragung

Idee

Gib den Stapeln getrennte Aufgaben. Jedes Element wird mit inbox in O(1) hinzugefügt. Pop- und Peek-Operationen lesen aus outbox, dessen oberstes Element immer das älteste Element in der Warteschlange ist.

Wenn outbox leer ist und eine Pop- oder Peek-Operation ausgeführt wird, gieße den gesamten Inhalt von inbox hinein. Das neueste Element wird zuerst von inbox genommen und landet daher ganz unten in outbox, während das älteste oben landet. Gieße nur um, wenn outbox leer ist: Solange sich darin noch Elemente befinden, sind sie älter als alles in inbox und müssen daher zuerst entnommen werden. Im zweiten Beispiel werden 4 und 7 vor dem ersten Pop umgegossen; 9 wartet dann in inbox, bis 7 entnommen wurde.

Ein einzelner Pop kann viele Elemente bewegen, aber zähle stattdessen den Aufwand pro Element: Jeder Wert wird einmal auf inbox gelegt, einmal nach outbox verschoben und einmal entnommen. n Operationen kosten daher insgesamt O(n), also amortisiert O(1) pro Operation. Die Warteschlange ist leer, wenn beide Stapel leer sind.

Algorithmus

Halte zwei leere Stapel bereit: inbox und outbox.
Für push x: Lege x auf inbox.
Für pop oder peek: Wenn outbox leer ist, lege jedes Element von inbox auf outbox. Entferne dann das oberste Element von outbox oder lies es aus.
Für empty: Gib an, ob beide Stapel leer sind.
Halte jede Antwort als Text fest und gib die Liste zurück.

class TwoStackQueue:
    def __init__(self):
        self.inbox = []    # new items go on top
        self.outbox = []   # the oldest item is on top

    def push(self, x):
        self.inbox.append(x)

    def _refill(self):
        # Only when the outbox is empty: pouring the inbox over reverses it,
        # so the oldest item lands on top.
        if not self.outbox:
            while self.inbox:
                self.outbox.append(self.inbox.pop())

    def pop(self):
        self._refill()
        return self.outbox.pop()

    def peek(self):
        self._refill()
        return self.outbox[-1]

    def empty(self):
        return not self.inbox and not self.outbox


def queueOps(ops, args):
    queue = TwoStackQueue()
    result = []
    for op, arg in zip(ops, args):
        if op == "push":
            queue.push(arg)
            result.append("null")
        elif op == "pop":
            result.append(str(queue.pop()))
        elif op == "peek":
            result.append(str(queue.peek()))
        else:
            result.append("true" if queue.empty() else "false")
    return result

Stolperfallen und Grenzfälle

Die meisten Fehler entstehen dadurch, dass zum falschen Zeitpunkt umgeschichtet oder nur ein Stapel geprüft wird.

inbox in outbox umschichten, während outbox noch Elemente enthält. Die neuen Elemente landen auf den älteren und werden zuerst entnommen, wodurch die Reihenfolge der Warteschlange durcheinandergerät. Im zweiten Beispiel käme 9 vor 7 heraus.
Allein anhand von outbox melden, dass die Warteschlange empty ist. Direkt nach einem Push liegt das neue Element in inbox, daher ist die Warteschlange nicht leer, auch wenn outbox leer ist.
Vergessen, dass peek dieselbe Umfüllung wie pop benötigt. Bei einem Peek direkt nach den ersten Pushes ist outbox leer.
Eine Warteschlange aus einer Bibliothek verwenden oder den untersten Wert eines Stapels per Index auslesen. Es geht darum, die Reihenfolge einer Warteschlange ausschließlich mit Stapeloperationen zu erreichen.
Zahlen oder boolesche Werte statt Text zurückgeben. Jede Antwort ist eine Zeichenkette, einschließlich "null" bei einem Push.

Häufige Fragen4

Wie hoch ist die Zeitkomplexität einer Warteschlange, die aus zwei Stapeln aufgebaut ist?

Push hat O(1). Pop und Peek haben amortisiert O(1): Bei einem Aufruf kann jedes Element von einem Stapel auf den anderen verschoben werden, aber jedes Element wird während seiner Lebensdauer höchstens einmal verschoben, sodass n Operationen insgesamt O(n) kosten. Zusammen enthalten die beiden Stapel jedes Element genau einmal, daher beträgt der Speicherbedarf O(n).

Was bedeutet amortisiertes O(1) hier?

Das bedeutet, dass die durchschnittlichen Kosten pro Operation über die gesamte Folge hinweg konstant sind, auch wenn eine einzelne Operation langsam sein kann. Ein Pop, bei dem 1.000 Elemente umgeschüttet werden, wird durch die 1.000 kostengünstigen Pushes davor ausgeglichen, denn diese Elemente werden nie wieder umgeschüttet. Keine Folge von n Operationen kostet mehr als etwa 4n Stapelschritte.

Warum brauchst du zwei Stapel und nicht einen?

Ein einzelner Stapel gibt nur sein neuestes Element frei, eine Warteschlange benötigt jedoch das älteste. Um den untersten Eintrag eines Stapels zu erreichen, muss alles darüber entfernt werden, und diese Elemente müssen irgendwo zwischengelagert werden – dafür dient der zweite Stapel. Beim Verschieben der Elemente wird ihre Reihenfolge umgekehrt, und genau durch diese Umkehrung wird aus „das Neueste zuerst“ „das Älteste zuerst“.

Kannst du stattdessen einen Stapel mithilfe von Warteschlangen implementieren?

Ja, aber die üblichen Methoden bringen keine amortisierte Einsparung. Eine gängige Methode verwendet eine Warteschlange: Nachdem ein neues Element hinzugefügt wurde, nimmst du jedes ältere Element von vorne und fügst es hinten wieder hinzu, sodass das neue Element schließlich vorne liegt. Dadurch ist push O(n) und pop O(1).

Python

def queueOps(ops, args):
    # Schreibe hier den Code

Testfälle

Fall 1

Fall 2

Fall 3

Eingabe

ops = ["push", "push", "peek", "pop", "empty"]
args = [1, 2, 0, 0, 0]

Erwartet

["null", "null", "1", "1", "false"]