Implementierung Stapel eine Warteschlange Pseudo-Code

Question

mit Ich bin verwirrt auf den folgenden Pseudo-Code

■ einen Stapel Implementierung einer einzigen Warteschlange verwenden. Schreiben Sie speziell Pseudocode für Push- und Popup-Vorgänge auf einem Stapel mit Enqueue und aus der Warteschlange Warteschlange Operationen. Stellen Sie sich vor, dass Ihnen die Queue-Klasse zugewiesen wurde. Wir werden eine einzige Warteschlange verwenden q. Betrachten wir die Vorderseite der Warteschlange ist die Oberseite des Stapels

push (x)

s = q.size() 
q.enqueue(x) 
for(int i = 0; i < s; i++) 
q.enqueue(q.dequeue()) 

pop() 
if q.isEmpty() 
“Exception” 
return q.dequeue() 

I erkennen, dass der Boden des Stapels der Rückseite der Warteschlange ist. Wenn wir also in die Warteschlange einsteigen, muss es auf den unteren Teil des Stapels gehen. Also müssen wir alles vom Stapel entfernen und den Gegenstand hineinschieben, dann alles zurückstellen. Ich verstehe nicht das "für (int i = 0; i < s; i ++) q.enqueue (q.dequeue())" Ich nehme an, dass das tut, worüber ich spreche, aber kann jemand mich durch es gehen? Vielen Dank!

Answer 1

Ein Stapel ist eine Datenstruktur, in der das letzte einzufügende Element als erstes zurückgegeben wird (LIFO). Eine einfache Warteschlange (FIFO) ist eine Struktur, die Elemente in der Reihenfolge zurückgibt, in der sie eingefügt wurden.

Die Schleife, nach der Sie fragen, führt die Neuordnung der Warteschlange durch, sodass das Element, das gerade eingefügt wurde, nun als erstes zurückgegeben wird. Genauer gesagt löscht es alle anderen Elemente und stellt sie in eine Warteschlange, wodurch das Element, das gerade eingefügt wurde, als erstes zurückgegeben wird. Alle anderen Elemente wurden nach dem eingefügten Element in die Warteschlange gestellt, was bedeutet, dass das eingefügte Element jetzt als erstes aus der Warteschlange entfernt wird.

Answer 2

Analysieren Sie, wie sich die Warteschlange innerhalb der for-Schleife ändert. Code kommt noch hinzu, neues Element und schreibt den Rest)

s = q.size() .   // Initial queue: (in) -> A -> B -> C -> (out) 
q.enqueue(x)     //   (in) -> D -> A -> B -> C -> (out) 
for(int i = 0; i < s; i++) 
    q.enqueue(q.dequeue()) // i == 0: (in) -> C -> D -> A -> B -> (out) 
           // i == 1: (in) -> B -> C -> D -> A -> (out) 
           // i == 2: (in) -> A -> B -> C -> D -> (out) 
pop() 
if q.isEmpty() 
    “Exception” 
return q.dequeue() 

Answer 3

Sagen wir Sie bereits 3 Werte hinzugefügt haben:

6 7 8 

Mit einer Warteschlange, können Sie nur auf der linken Seite hinzufügen können, und nehmen Sie nur auf die Recht.

Mit einem Stapel, möchten Sie auf der rechten Seite hinzuzufügen, und auf der rechten Seite zu nehmen, das heißt das Ziel, den nächsten Wert zu addieren ist (9) auf der rechten Seite, wie folgt aus:

6 7 8 9 

Aber, mit einer Warteschlange, können Sie nur auf der linken Seite hinzufügen:

9 6 7 8 

Also, was Sie tun wollen, ist Zyklus die vorbestehenden Werte (6 7 8) von rechts nach links, einer nach dem anderen, mit gültigen Warteschlangenaktionen:

┌─> 8 9 6 7 ─┐ 
└───────────────┘ 

┌─> 7 8 9 6 ─┐ 
└───────────────┘ 

┌─> 6 7 8 9 ─┐ 
└───────────────┘ 

So zu tun, dass für die Werte bereits existierenden, können Sie die Größe der Warteschlange vor nehmen den neuen Wert hinzufügen, fügen Sie dann den neuen Wert und letzten Wert nach vorne rückt so oft wie benötigt, dh size mal.