Angenommen, wir haben zwei Stapel und keine andere temporäre Variable.
Ist es möglich, eine Warteschlangendatenstruktur nur mit den beiden Stapeln zu "konstruieren"?
algorithm
data-structures
stack
queue
Nitin
quelle
quelle
A - So kehren Sie einen Stapel um
Um zu verstehen, wie eine Warteschlange mit zwei Stapeln erstellt wird, sollten Sie wissen, wie Sie einen Stapel kristallklar umkehren. Denken Sie daran, wie der Stapel funktioniert. Er ist dem Geschirrstapel in Ihrer Küche sehr ähnlich. Das zuletzt gewaschene Gericht befindet sich oben auf dem sauberen Stapel, der als L ast I n F irst O bezeichnet wird in der Informatik ut (LIFO) bezeichnet wird.
Stellen wir uns unseren Stapel wie eine Flasche vor;
Wenn wir die Ganzzahlen 1,2,3 drücken, befindet sich 3 oben auf dem Stapel. Da 1 zuerst gedrückt wird, wird 2 oben auf 1 gesetzt. Zuletzt wird 3 oben auf den Stapel gelegt, und der letzte Status unseres Stapels, der als Flasche dargestellt wird, ist wie folgt.
Jetzt haben wir unseren Stapel so dargestellt, dass eine Flasche mit den Werten 3,2,1 gefüllt ist. Und wir wollen den Stapel umkehren, so dass das obere Element des Stapels 1 und das untere Element des Stapels 3 ist. Was können wir tun? Wir können die Flasche nehmen und sie verkehrt herum halten, damit sich alle Werte in der Reihenfolge umkehren?
Ja, das können wir, aber das ist eine Flasche. Um den gleichen Prozess durchzuführen, benötigen wir einen zweiten Stapel, in dem die ersten Stapelelemente in umgekehrter Reihenfolge gespeichert werden. Lassen Sie uns unseren bestückten Stapel links und unseren neuen leeren Stapel rechts platzieren. Um die Reihenfolge der Elemente umzukehren, werden wir jedes Element vom linken Stapel entfernen und auf den rechten Stapel verschieben. Sie können auf dem Bild unten sehen, was passiert, wenn wir dies tun.
Wir wissen also, wie man einen Stapel umkehrt.
B - Verwenden von zwei Stapeln als Warteschlange
Im vorherigen Teil habe ich erklärt, wie wir die Reihenfolge der Stapelelemente umkehren können. Dies war wichtig, da die Ausgabe genau in umgekehrter Reihenfolge einer Warteschlange erfolgt, wenn Elemente in den Stapel verschoben und eingefügt werden. Lassen Sie uns anhand eines Beispiels das Array von Ganzzahlen
{1, 2, 3, 4, 5}
auf einen Stapel verschieben. Wenn wir die Elemente{5, 4, 3, 2, 1}
einfügen und drucken, bis der Stapel leer ist, erhalten wir das Array in der umgekehrten Reihenfolge der Push-Reihenfolge. Beachten Sie, dass bei derselben Eingabe die Ausgabe in die Warteschlange gestellt wird, bis die Warteschlange leer ist wird sein{1, 2, 3, 4, 5}
. Es ist also offensichtlich, dass bei derselben Eingabereihenfolge von Elementen die Ausgabe der Warteschlange genau umgekehrt ist wie die Ausgabe eines Stapels. Da wir wissen, wie man einen Stapel mit einem zusätzlichen Stapel umkehrt, können wir eine Warteschlange mit zwei Stapeln erstellen.Unser Warteschlangenmodell besteht aus zwei Stapeln. Ein Stapel wird für die
enqueue
Operation verwendet (Stapel Nr. 1 links wird als Eingabestapel bezeichnet), ein anderer Stapel wird für diedequeue
Operation verwendet (Stapel Nr. 2 rechts wird als Ausgabestapel bezeichnet). Schauen Sie sich das Bild unten an.Unser Pseudocode ist wie folgt;
Warteschlangenbetrieb
Warteschlangenbetrieb
Lassen Sie uns die Ganzzahlen in die Warteschlange stellen
{1, 2, 3}
. Ganzzahlen werden auf den Eingangsstapel ( Stapel Nr. 1 ) auf der linken Seite verschoben.Was passiert dann, 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 in der Ausgabe extrahiert, damit die Elemente des Eingangsstapels wird umgekehrt. Vor der Rückgabe eines Werts lautet der Status der Warteschlange wie folgt:
Überprüfen Sie die Reihenfolge der Elemente im Ausgabestapel (Stapel 2). Es ist offensichtlich, dass wir die Elemente aus dem Ausgabestapel entfernen können, sodass die Ausgabe dieselbe ist, als ob wir uns aus einer Warteschlange entfernt hätten. Wenn wir also zwei Dequeue-Operationen ausführen, erhalten wir
{1, 2}
jeweils zuerst. Dann ist Element 3 das einzige Element des Ausgabestapels, und der Eingabestapel ist leer. Wenn wir die Elemente 4 und 5 in die Warteschlange stellen, lautet der Status der Warteschlange wie folgt:Jetzt ist der Ausgabestapel nicht leer, und wenn wir eine Dequeue-Operation ausführen, werden nur 3 aus dem Ausgabestapel entfernt. Dann wird der Zustand wie folgt gesehen;
Wenn wir zwei weitere Dequeue-Operationen ausführen, prüft die Warteschlange bei der ersten Dequeue-Operation erneut, ob der Ausgabestapel leer ist, was wahr ist. Ziehen Sie dann die Elemente des Eingabestapels heraus und verschieben Sie sie in den Ausgabestapel, bis der Eingabestapel leer ist. Der Status der Warteschlange lautet dann wie folgt.
Leicht zu sehen ist die Ausgabe der beiden Dequeue-Operationen
{4, 5}
C - Implementierung einer Warteschlange mit zwei Stapeln
Hier ist eine Implementierung in Java. Ich werde die vorhandene Implementierung von Stack nicht verwenden, daher wird das Beispiel hier das Rad neu erfinden.
C - 1) MyStack-Klasse: Eine einfache Stack-Implementierung
C - 2) MyQueue-Klasse: Warteschlangenimplementierung mit zwei Stapeln
C - 3) Demo-Code
C - 4) Probenausgabe
quelle
Sie können sogar eine Warteschlange mit nur einem Stapel simulieren. Der zweite (temporäre) Stapel kann durch den Aufrufstapel rekursiver Aufrufe der Einfügemethode simuliert werden.
Das Prinzip bleibt beim Einfügen eines neuen Elements in die Warteschlange gleich:
Eine Warteschlangenklasse, die nur einen Stapel verwendet, lautet wie folgt:
quelle
n items
Verwendung der obigen Datenstruktur in die Warteschlange einzufügen . die Summe(1 + 2 + 4 + 8 + .... + 2(n-1))
ergibt~O(n^2)
. Ich hoffe du verstehst, worum es geht.Die zeitliche Komplexität wäre jedoch schlimmer. Eine gute Warteschlangenimplementierung erledigt alles in konstanter Zeit.
Bearbeiten
Ich bin mir nicht sicher, warum meine Antwort hier abgelehnt wurde. Wenn wir programmieren, ist uns die Zeitkomplexität wichtig, und die Verwendung von zwei Standardstapeln zum Erstellen einer Warteschlange ist ineffizient. Es ist ein sehr gültiger und relevanter Punkt. Wenn jemand anderes das Bedürfnis hat, dies weiter abzustimmen, würde mich interessieren, warum.
Ein bisschen mehr Details : Warum die Verwendung von zwei Stapeln schlechter ist als nur eine Warteschlange: Wenn Sie zwei Stapel verwenden und jemand die Warteschlange aufruft, während der Postausgang leer ist, benötigen Sie eine lineare Zeit, um zum Ende des Posteingangs zu gelangen (wie Sie sehen können) in Daves Code).
Sie können eine Warteschlange als einfach verknüpfte Liste implementieren (jedes Element zeigt auf das nächst eingefügte Element), wobei Sie einen zusätzlichen Zeiger auf das zuletzt eingefügte Element für Pushs behalten (oder es zu einer zyklischen Liste machen). Das Implementieren von Warteschlangen und Warteschlangen in dieser Datenstruktur ist in konstanter Zeit sehr einfach. Das ist im schlimmsten Fall eine konstante Zeit, die nicht abgeschrieben wird. Und da die Kommentare nach dieser Klarstellung zu fragen scheinen, ist die konstante Zeit im ungünstigsten Fall strikt besser als die amortisierte konstante Zeit.
quelle
Die zu implementierende Warteschlange sei q und die zur Implementierung von q verwendeten Stapel seien Stapel1 und Stapel2.
q kann auf zwei Arten implementiert werden:
Methode 1 (indem der enQueue-Betrieb teuer wird)
Diese Methode stellt sicher, dass sich das neu eingegebene Element immer oben in Stapel 1 befindet, sodass die deQueue-Operation nur aus Stapel 1 angezeigt wird. Um das Element oben auf Stapel1 zu platzieren, wird Stapel2 verwendet.
Methode 2 (Durch kostspielige DeQueue-Operation)
Bei dieser Methode wird im En-Queue-Betrieb das neue Element oben in Stapel1 eingegeben. Wenn im De-Queue-Betrieb Stapel2 leer ist, werden alle Elemente nach Stapel2 verschoben und schließlich wird der Anfang von Stapel2 zurückgegeben.
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 Elemente nur verschiebt, wenn stack2 leer ist.
quelle
Eine Lösung in c #
quelle
Zwei Stapel in der Warteschlange sind als Stapel1 und Stapel2 definiert .
Enqueue: Die euqueued-Elemente werden immer in stack1 verschoben
Dequeue: Die Oberseite von stack2 kann herausspringen, da es das erste Element ist, das in die Warteschlange eingefügt wird, wenn stack2 nicht leer ist. Wenn stack2 leer ist, werden alle Elemente aus entfernt stack1 entfernt und einzeln in stack2 verschoben . Das erste Element in einer Warteschlange wird in den unteren Bereich von Stack1 verschoben . Es kann direkt nach dem Poppen und Drücken herausspringen, da es sich oben auf Stapel2 befindet .
Das Folgende ist der gleiche C ++ - Beispielcode:
Diese Lösung ist ausgeliehen von meinem Blog . Eine detailliertere Analyse mit schrittweisen Betriebssimulationen finden Sie auf meiner Blog-Webseite.
quelle
Sie müssen alles vom ersten Stapel entfernen, um das untere Element zu erhalten. Legen Sie sie dann bei jeder "Dequeue" -Operation alle wieder auf den zweiten Stapel.
quelle
Für C # -Entwickler ist hier das komplette Programm:
quelle
Implementieren Sie die folgenden Operationen einer Warteschlange mithilfe von Stapeln.
push (x) - Schieben Sie das Element x in den hinteren Bereich der Warteschlange.
pop () - Entfernt das Element vor der Warteschlange.
peek () - Holen Sie sich das vordere Element.
empty () - Gibt zurück, ob die Warteschlange leer ist.
quelle
quelle
Eine Implementierung einer Warteschlange mit zwei Stapeln in Swift:
quelle
Sie erhalten zwar viele Beiträge zum Implementieren einer Warteschlange mit zwei Stapeln: 1. Entweder indem Sie den enQueue-Prozess viel teurer machen. 2. Oder indem Sie den deQueue-Prozess viel teurer machen
https://www.geeksforgeeks.org/queue-using-stacks/
Ein wichtiger Weg, den ich aus dem obigen Beitrag herausgefunden habe, war das Erstellen einer Warteschlange mit nur der Stapeldatenstruktur und dem Rekursionsaufrufstapel.
Man kann zwar argumentieren, dass buchstäblich immer noch zwei Stapel verwendet werden, aber im Idealfall wird nur eine Stapeldatenstruktur verwendet.
Nachfolgend finden Sie die Erklärung des Problems:
Deklarieren Sie einen einzelnen Stapel zum Aktivieren und Deaktivieren der Daten und verschieben Sie die Daten in den Stapel.
Während deQueueing eine Grundbedingung hat, bei der das Element des Stapels eingeblendet wird, wenn die Größe des Stapels 1 beträgt. Dadurch wird sichergestellt, dass während der deQueue-Rekursion kein Stapelüberlauf auftritt.
Während des DeQueueing werden zuerst die Daten vom oberen Rand des Stapels eingeblendet. Idealerweise ist dieses Element das Element, das sich oben auf dem Stapel befindet. Rufen Sie nun rekursiv die Funktion deQueue auf und schieben Sie das oben platzierte Element zurück in den Stapel.
Der Code sieht wie folgt aus:
Auf diese Weise können Sie eine Warteschlange mithilfe einer einzelnen Stack-Datenstruktur und des Rekursionsaufrufstapels erstellen.
quelle
Unten finden Sie die Lösung in Javascript-Sprache mit ES6-Syntax.
Stack.js
QueueUsingTwoStacks.js
Unten ist die Verwendung:
index.js
quelle
stack1
. Wenn Sie erneut zu gehendequeue
, verschieben Sie sie in Elementestack2
und stellen sie vor das, was bereits vorhanden war.Ich werde diese Frage in Go beantworten, da Go nicht viele Sammlungen in seiner Standardbibliothek hat.
Da ein Stack sehr einfach zu implementieren ist, dachte ich, ich würde versuchen, zwei Stacks zu verwenden, um eine Warteschlange mit zwei Enden zu erstellen. Um besser zu verstehen, wie ich zu meiner Antwort gekommen bin, habe ich die Implementierung in zwei Teile geteilt. Der erste Teil ist hoffentlich leichter zu verstehen, aber unvollständig.
Es sind im Grunde zwei Stapel, bei denen wir zulassen, dass der Boden der Stapel voneinander manipuliert wird. Ich habe auch die STL-Namenskonventionen verwendet, bei denen die traditionellen Push-, Pop- und Peek-Operationen eines Stapels ein Front / Back-Präfix haben, unabhängig davon, ob sie sich auf die Vorder- oder Rückseite der Warteschlange beziehen.
Das Problem mit dem obigen Code ist, dass er den Speicher nicht sehr effizient nutzt. Tatsächlich wächst es endlos, bis Ihnen der Platz ausgeht. Das ist wirklich schlimm. Die Lösung hierfür besteht darin, den unteren Rand des Stapelbereichs nach Möglichkeit einfach wiederzuverwenden. Wir müssen einen Versatz einführen, um dies zu verfolgen, da ein Slice in Go nach dem Schrumpfen nicht mehr vorne wachsen kann.
Es sind viele kleine Funktionen, aber von den 6 Funktionen sind 3 nur Spiegel der anderen.
quelle
Hier ist meine Lösung in Java mit Linkedlist.
}}
Hinweis: In diesem Fall ist der Pop-Vorgang sehr zeitaufwändig. Daher werde ich nicht vorschlagen, eine Warteschlange mit zwei Stapeln zu erstellen.
quelle
Mit
O(1)
dequeue()
, was der Antwort von Pythonquick entspricht :Mit
O(1)
enqueue()
(dies wird in diesem Beitrag nicht erwähnt, also diese Antwort), das auch Backtracking verwendet, um das unterste Element in die Luft zu sprudeln und zurückzugeben.Offensichtlich ist es eine gute Codierungsübung, da sie ineffizient, aber dennoch elegant ist.
quelle
** Einfache JS-Lösung **
quelle
Für jede Enqueue-Operation fügen wir oben im Stapel1 hinzu. Für jede Warteschlange leeren wir den Inhalt von Stapel1 in Stapel2 und entfernen das Element oben im Stapel. Die Zeitkomplexität beträgt O (n) für die Warteschlange, da wir den Stapel1 in Stapel2 kopieren müssen. Die zeitliche Komplexität der Warteschlange entspricht der eines regulären Stapels
quelle
if (stack2 != null)
ist immer wahr, weil erstack2
im Konstruktor instanziiert wird.Warteschlangenimplementierung mit zwei java.util.Stack-Objekten:
quelle
return inbox.isEmpty() && outbox.isEmpty()
undreturn inbox.size() + outbox.size()
, respectively. Der Code von Dave L. löst bereits eine Ausnahme aus, wenn Sie sich aus einer leeren Warteschlange entfernen. Die ursprüngliche Frage betraf nicht einmal Java. Es ging um Datenstrukturen / Algorithmen im Allgemeinen. Die Java-Implementierung war nur eine zusätzliche Illustration.