Queue und Stack 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 die 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, also können Sie diese Analogie gerne 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 das erreichen könnten.

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

Nun, für diejenigen, die es versucht haben und einen „Timeout-Fehler“ erhalten haben, und für diejenigen, die sich nicht die Mühe gemacht haben, es zu versuchen, möchte ich Ihnen 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. Durch die Umkehrung werden die Elemente des EnqueueStacks in den DequeueStack übernommen, und das Dequeue-Stacks-Element, das ursprünglich als erstes vorhanden sein sollte, ist nun das letzte. Daher muss dequeueStack zunächst wie im Code gezeigt geleert werden.

Ähnlich wie hier druckt printFront das Element, das sich am Anfang der Warteschlange befinden soll.

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

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!