Was sind Stapel und Warteschlange?
Ein Stapel (englisch Stack) ist eine Sammlung, bei der immer der zuletzt abgelegte Wert zuerst wieder herauskommt. Eine Warteschlange (englisch Queue) arbeitet umgekehrt: Wer zuerst kommt, wird zuerst bedient. Mit diesen zwei Strukturen lösen Sie Rückgängig-Funktionen, Klammerprüfungen und Druckaufträge.
Die Zurück-Taste im Browser nimmt immer die zuletzt besuchte Seite. Der Kopierer in der Bibliothek druckt die Aufträge in der Reihenfolge, in der sie ankamen.
Am Ende dieser Lektion
Notiz
Ich kann einen Stapel und eine Warteschlange einsetzen, um ein Problem zu lösen.
Schlüsselwörter
| Begriff | Was er bedeutet | Beispiel |
|---|---|---|
| Stapel | eine Sammlung, aus der zuerst der neueste Wert kommt | |
| Warteschlange | eine Sammlung, aus der zuerst der älteste Wert kommt | |
| LIFO | zuletzt hinein, zuerst heraus (Regel des Stapels) | |
| FIFO | zuerst hinein, zuerst heraus (Regel der Warteschlange) | |
| push | einen Wert oben auf den Stapel legen | verlauf.append(x) |
| pop | den obersten Wert vom Stapel nehmen | verlauf.pop() |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Ein Stapel gibt den neuesten Wert zuerst her
Ein Stapel hat zwei Handgriffe. Mit push legen Sie einen Wert oben drauf. Mit pop nehmen Sie den obersten wieder herunter. Sie kommen nur an die Spitze heran, so wie bei einem Tellerstapel in der Mensa. In Python ist eine Liste mit append und pop ein Stapel.
Beispiel: der Verlauf einer Zurück-Taste
| Befehl | Stapel danach (oben rechts) | Ergebnis |
|---|---|---|
| push Startseite | Startseite | Keines |
| push Mensaplan | Startseite, Mensaplan | Keines |
| push Bibliothek | Startseite, Mensaplan, Bibliothek | Keines |
| pop | Startseite, Mensaplan | Bibliothek |
| pop | Startseite | Mensaplan |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Rückgängig mit einem Stapel
# Ein Stapel als Rueckgaengig-Verlauf: das Neueste kommt zuerst.
verlauf = []
verlauf.append("Titel getippt")
verlauf.append("Absatz eingefuegt")
verlauf.append("Bild geloescht")
while len(verlauf) > 0:
print("Rueckgaengig:", verlauf.pop())
# Haengen Sie vor der Schleife einen vierten Schritt an.
Ein Stapel im Terminal
Der Befehl tac gibt die Zeilen von hinten nach vorn aus. Das ist die Reihenfolge, in der ein Stapel sie hergibt. Der zweite Befehl legt drei Zahlen auf einen Stapel, nimmt zwei herunter und gibt aus, was herauskam und wie viel blieb.
Zeilen in Stapelreihenfolge ausgeben
printf 'Startseite\nMensaplan\nBibliothek\n' | tacHier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Zweimal pop auf einem kleinen Stapel
python3 -c "s = []; s.append(1); s.append(2); s.append(3); print(s.pop(), s.pop(), len(s))"Hier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Eine Warteschlange bedient den ältesten Wert zuerst
Eine Warteschlange hat zwei Enden. Hinten reihen Sie mit enqueue einen Wert ein. Vorn nehmen Sie mit dequeue den ältesten heraus. So geht es am Kopierer zu: Wer zuerst kam, wird zuerst bedient. Bei einer Python-Liste ist pop(0) langsam, weil alle Werte nachrücken. Das kennen Sie aus Lektion 1.
Stapel und Warteschlange im Vergleich
| Eigenschaft | Stapel | Warteschlange |
|---|---|---|
| Regel | LIFO | FIFO |
| Wert hinein | push, oben | enqueue, hinten |
| Wert heraus | pop, oben | dequeue, vorn |
| Beispiel | Rückgängig, Zurück-Taste | Druckaufträge, Kasse |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Druckaufträge in einer Warteschlange
# Eine Warteschlange: der aelteste Auftrag wird zuerst gedruckt.
auftraege = ["Hausarbeit.pdf", "Poster.pdf", "Skript.pdf"]
while len(auftraege) > 0:
naechster = auftraege.pop(0)
print("Drucke", naechster)
# Haengen Sie vorher einen vierten Auftrag mit append an.
Den ältesten Auftrag herausnehmen
printf 'Hausarbeit\nPoster\nSkript\n' | head -n 1Hier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Ein Stapel prüft Klammern
In einem Ausdruck wie (a + [b * c]) muss jede Klammer richtig geschlossen werden. Gehen Sie von links nach rechts. Eine öffnende Klammer legen Sie auf den Stapel. Bei einer schließenden nehmen Sie die oberste herunter. Sie muss zur selben Art gehören. Am Ende muss der Stapel leer sein.
Beispiel: die Klammern in ([]) prüfen
| Zeichen | Aktion | Stapel danach |
|---|---|---|
| ( | push | ( |
| [ | push | ( [ |
| ] | pop ergibt [, passt | ( |
| ) | pop ergibt (, passt | leer, also richtig |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Ein häufiger Fehler
Warnung
Viele denken, es genüge, öffnende und schließende Klammern zu zählen. ([)] hat von jeder Art ein Paar und ist trotzdem falsch. Die Reihenfolge zählt. Darum braucht die Prüfung einen Stapel und keinen Zähler.