Die Zurück-Taste und die Schlange an der Kasse
Ein Stapel (englisch stack) und eine Warteschlange (englisch queue) sind zwei Arten, Daten zu ordnen. Beim Stapel kommt das Letzte zuerst heraus, bei der Warteschlange das Erste. Mit beiden löst man viele Aufgaben, vom Rückgängig-Knopf bis zu Druckaufträgen.
Die Zurück-Taste deines Browsers merkt sich die Seiten als Stapel. Die Kasse im Supermarkt arbeitet wie eine Warteschlange.
Am Ende dieser Lektion
Notiz
Ich kann einen Stapel und eine Warteschlange mit Listen benutzen.
Schlüsselwörter
| Begriff | Was er bedeutet | Beispiel |
|---|---|---|
| Stapel | eine Datenstruktur: Das zuletzt Hinzugefügte kommt zuerst heraus | |
| Warteschlange | eine Datenstruktur: Das zuerst Hinzugefügte kommt zuerst heraus | |
| Push | etwas oben auf den Stapel legen | append |
| Pop | das oberste Element vom Stapel nehmen | pop() |
| Datenstruktur | eine Art, Daten zu speichern und zu ordnen |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Ein Stapel: zuletzt hinein, zuerst heraus
Stell dir einen Stapel Teller vor. Du legst oben einen Teller drauf und nimmst oben einen weg. An die unteren kommst du erst, wenn die oberen weg sind.
Das Prinzip heißt LIFO, englisch last in, first out. In Python ist append(x) das Push und pop() ohne Zahl das Pop.
Beispiel: Seiten im Browser-Verlauf
| Aktion | Stapel danach (unten bis oben) | Ergebnis |
|---|---|---|
| Push start | start | |
| Push shop | start, shop | |
| Push kasse | start, shop, kasse | |
| Pop | start, shop | kasse (die letzte Seite) |
| Pop | start | shop |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Bevor du anfängst
Notiz
Drück oben in der Leiste auf Lab starten und warte, bis JupyterLab läuft. Die Schaltflächen Ausführen tippen ihren Befehl in das Terminal neben dem Lab. Jeder startet Python im Container jupyter.
Einen Stapel im Lab benutzen
Der erste Befehl schreibt ein kleines Programm in stapel.py. Es legt drei Seiten auf einen Stapel und nimmt zwei wieder herunter. Danach dreht es das Wort Banane mit einem Stapel um. Der zweite Befehl startet es.
Das Programm in stapel.py schreiben
docker exec jupyter sh -c "printf 'verlauf = []\nverlauf.append(\"start\")\nverlauf.append(\"shop\")\nverlauf.append(\"kasse\")\nprint(verlauf.pop())\nprint(verlauf.pop())\nprint(verlauf)\nstapel = []\nfor buchstabe in \"Banane\":\n stapel.append(buchstabe)\numgekehrt = \"\"\nwhile len(stapel) > 0:\n umgekehrt = umgekehrt + stapel.pop()\nprint(umgekehrt)\n' > stapel.py"Hier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Den Stapel starten
docker exec jupyter python3 stapel.pyHier 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: zuerst hinein, zuerst heraus
In einer Schlange kommt zuerst dran, wer zuerst da war. Das Prinzip heißt FIFO, englisch first in, first out.
In Python hängst du hinten mit append(x) an. Vorn nimmst du mit pop(0) das erste Element heraus. Die 0 sagt: die Stelle ganz vorn.
Beispiel: Druckaufträge in der Schule
| Aktion | Schlange danach (vorn bis hinten) | Ergebnis |
|---|---|---|
| Ana schickt einen Auftrag | Ana | |
| Ben schickt einen Auftrag | Ana, Ben | |
| Der Drucker nimmt den nächsten | Ben | Ana wird gedruckt |
| Cem schickt einen Auftrag | Ben, Cem |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Das Programm in schlange.py schreiben
docker exec jupyter sh -c "printf 'schlange = [\"Ana\", \"Ben\", \"Cem\"]\nprint(schlange.pop(0))\nschlange.append(\"Dilara\")\nprint(schlange)\n' > schlange.py"Hier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Die Warteschlange starten
docker exec jupyter python3 schlange.pyHier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Ein häufiger Fehler
Warnung
Viele verwechseln pop() und pop(0). pop() nimmt das letzte Element, das ist ein Stapel. pop(0) nimmt das erste, das ist eine Schlange. Nimm bei einer leeren Liste nichts heraus, sonst gibt es einen Fehler. Prüfe vorher len(liste) > 0.
Mit einem Stapel Klammern prüfen
Ein Taschenrechner oder ein Editor prüft mit einem Stapel, ob jede öffnende Klammer eine passende schließende hat. Öffnende Klammern kommen auf den Stapel. Bei einer schließenden nimmst du die oberste herunter.
Passen beide nicht zusammen oder ist der Stapel leer, ist es falsch. Am Ende muss der Stapel leer sein.
Beispiel: der Text (a[b]) Schritt für Schritt
| Zeichen | Was passiert | Stapel danach |
|---|---|---|
| ( | Öffnend: Push | ( |
| a | Keine Klammer: nichts | ( |
| [ | Öffnend: Push | ( [ |
| b | Keine Klammer: nichts | ( [ |
| ] | Schließend: Pop gibt [, passt | ( |
| ) | Schließend: Pop gibt (, passt | leer, also richtig |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Weiterführend: der Rückgängig-Knopf
Ein Zeichenprogramm merkt sich jede Aktion auf einem Stapel. Wie funktioniert dann Rückgängig? Was bräuchte der Knopf Wiederholen als zweiten Stapel? Skizziere, was bei fünf Aktionen und zwei Rückgängig auf jedem Stapel liegt.