Queue mit Stack implementieren

Warteschlange und Stapel sind ziemlich einfache Datenstrukturen, die wir in unserer täglichen Codierung verwenden. Tatsächlich können sie als die am einfachsten zu verwaltenden Strukturen für Daten angesehen werden.

Im gesamten Artikel verwende ich DS, um auf Datenstruktur zu verweisen.

Queue ist ein DS, der nach dem FIFO-Prinzip arbeitet. Die Daten, die zuerst kommen, dürfen zuerst raus. Es gibt viele Möglichkeiten, Warteschlangen zu implementieren. Es steht uns frei, Arrays, verknüpfte Listen und viele andere zu verwenden. Aber hier möchte ich die Implementierung von Queue mithilfe eines anderen DS namens Stack besprechen.

Jetzt wissen wir alle, dass Stack ein DS ist, der nach dem LIFO-Prinzip arbeitet. Ich denke immer darüber nach, Bücher übereinander zu stapeln, Sie können also gerne diese Analogie verwenden, wenn sie Ihnen bei der Visualisierung hilft.

Ich bin bei Hackerrank auf diese Frage gestoßen, wo wir aufgefordert wurden, Queue mit 2 Stacks zu implementieren. Klingt einfach, oder? Nehmen Sie sich einen Moment Zeit und überlegen Sie, wie wir dies erreichen können.

Vielleicht haben Sie sich einige Lösungen ausgedacht, denn es gibt viele Möglichkeiten, dies zu tun. Warum probieren Sie es also nicht direkt aus?

Frage

Jetzt möchte ich denjenigen, die es versucht haben und einen „Timeout-Fehler“ erhalten haben, und denjenigen, die sich nicht die Mühe gemacht haben, es zu versuchen, die einfachste und einfachste Lösung für dieses Problem erklären.

Schauen Sie sich zunächst an, wie der Stack implementiert werden kann.

Wie Sie sehen können, habe ich den Stack mithilfe einer Liste implementiert. Zunächst initialisiert der Konstruktor eine leere Liste. Wir pushen Daten, indem wir sie an das Ende der Liste anhängen. Wenn wir beim Pop-Up keinen Index bereitstellen, wird er am Ende der Liste angezeigt. Somit ist das letzte eingefügte Element das erste, das herausspringt.

Jetzt haben wir auf ähnliche Weise für die Warteschlange zwei verschiedene Stapel initialisiert. Eine für die Warteschlange und eine für die Warteschlange.

Wir verwenden enqueueStack ähnlich wie Stack, nur um Daten am Ende der Liste zu verschieben. Aber für dequeueStack wissen wir, dass die Pop-Funktion von Stack das Element vom letzten entfernt, also tun wir Folgendes: Wir kehren den enqueueStack um und fügen ihn in dequeueStack ein. Somit wird das erste Element von enqueueStack zum letzten Element von dequeueStack, das zweite von enqueueStack wird zum vorletzten von dequeueStack und so weiter. Wenn wir nun die Pop-Funktion für dequeueStack verwenden, wird das erste Element entfernt, das wir verschoben haben, und so die Warteschlange nachahmen.

Machen Sie sich keine Sorgen, wenn das jetzt verwirrend klingt! Sobald Sie den Code sehen, werden Sie erkennen, wovon ich spreche. Schauen Sie es sich doch gleich an!

Sie fragen sich vielleicht, wozu diese zusätzlichen Schecks dienen. Als würde man überprüfen, ob der dequeueStack leer ist oder nicht. Wenn wir es nicht zunächst überprüfen. Die Elemente des enqueueStack werden durch Umkehrung in den dequeueStack übernommen, und was passiert, ist, dass das dequeue Stacks-Element, das zuerst sein sollte, nun das letzte ist. Daher muss dequeueStack zunächst geleert werden, wie im Code gezeigt.

Ähnlich wie hier druckt printFront das Element, das sich an der Spitze der Warteschlange befinden soll.

Nach dieser Implementierung lesen wir die Eingabe von STDIN und drucken die Ausgabe an STDOUT.

Unsere Eingabe sieht ungefähr so ​​aus:

Und die vollständige Hauptfunktion ist:

Ich habe versucht, dies so einfach wie möglich umzusetzen. Möglicherweise gibt es mehrere andere und bessere Möglichkeiten, dies umzusetzen. Einer davon wird hier vorgestellt!

Das obige ist der detaillierte Inhalt vonQueue mit Stack implementieren. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!