Stack, Queue und verkettete Liste

Kurz gesagt: Ein Stack gibt das zuletzt hinzugefügte Element zuerst zurück (LIFO), eine Queue das zuerst hinzugefügte (FIFO), und eine verkettete Liste hält jedes Element in einem Knoten, der auf den nächsten zeigt.

Problem

„Rückgängig“ macht das Falsche rückgängig

Ein Texteditor hält die Aktionen in einer Liste. Strg+Z soll die letzte rückgängig machen, macht aber die erste rückgängig:

actions = []
actions.append("Text getippt")
actions.append("Titel fett gemacht")
actions.append("Foto eingefügt")

# Strg+Z: die letzte Aktion rückgängig machen.
undone = actions.pop(0)
print("Rückgängig:", undone)
print("Übrig:", actions)

Ausgabe

Rückgängig: Text getippt
Übrig: ['Titel fett gemacht', 'Foto eingefügt']

Die Korrektur ist actions.pop(). Aber jeder, der diesen Code anfasst, muss sich merken, an welchem Ende er entfernt. Und an der Kasse im Laden ist es umgekehrt: Wer zuerst kam, wird zuerst bedient. Gibt es eine Collection, die das Ende selbst kennt?

Die Idee

Stack: der Letzte liegt oben

Ein Stack ist wie ein Stapel Teller. Du legst oben drauf und nimmst von oben. Was zuletzt hineinkam, kommt zuerst heraus. Das heißt LIFO: last in, first out.

Der Button „Zurück“ im Browser ist ein Stack:

history = []
history.append("Startseite")
history.append("Laptops")
history.append("Laptop 14 Zoll")
print("Jetzt:", history[-1])

history.pop()
print("Zurück:", history[-1])
print(history)

Ausgabe

Jetzt: Laptop 14 Zoll
Zurück: Laptops
['Startseite', 'Laptops']

Python hat keine eigene Klasse für einen Stack: Eine Liste ist ein Stack, wenn du nur am Ende hineinlegst und herausnimmst.

• append legt oben drauf, pop() ohne Index entfernt das oberste und gibt es zurück, und history[-1] schaut das oberste nur an.
• Oben ist das Ende der Liste. Beide Operationen sind schnell, weil sich am Ende nichts verschiebt.
• print gibt den Stack von unten nach oben aus: Das oberste steht zuletzt.

Genauer, für Neugierige

• pop() und [-1] auf einer leeren Liste brechen das Programm mit IndexError ab. Prüf also zuerst. if history: bedeutet „wenn die Liste nicht leer ist“: Eine leere Liste verhält sich in if und while wie False.

history = []
if history:
    print("Jetzt:", history[-1])
else:
    print("Es gibt keine vorige Seite.")
try:
    history.pop()
except IndexError as e:
    print(f"IndexError: {e}")

Ausgabe

Es gibt keine vorige Seite.
IndexError: pop from empty list

Probier es aus

Was bleibt rückgängig zu machen?

Was gibt das Programm aus?

undo = []
undo.append("Schriftart")
undo.append("Farbe")
undo.append("Größe")
undo.pop()
undo.append("Unterstreichung")
while len(undo) > 0:
    print(undo.pop())

Antwort

Unterstreichung
Farbe
Schriftart

Schriftart
Farbe
Größe

Schriftart
Farbe
Unterstreichung

Unterstreichung
Größe
Farbe
Schriftart

Prüfen

Die Idee

Queue: Wer zuerst kommt, wird zuerst bedient

Eine Queue (Warteschlange) ist wie die Schlange an der Kasse. Du stellst dich hinten an, und der Erste wird bedient. Das heißt FIFO: first in, first out.

Druckaufträge warten in einer Queue:

from collections import deque

printer = deque()
printer.append("rechnung.pdf")
printer.append("vertrag.docx")
printer.append("foto.jpg")
print("Nächster:", printer[0])

while len(printer) > 0:
    print("Drucke", printer.popleft())
print("Warteschlange:", printer)

Ausgabe

Nächster: rechnung.pdf
Drucke rechnung.pdf
Drucke vertrag.docx
Drucke foto.jpg
Warteschlange: deque([])

• deque liegt im Modul collections, darum beginnt die Datei mit from collections import deque. Der Name kommt von double-ended queue, einer Queue mit zwei Enden.
• append stellt hinten an, popleft entfernt den ersten und gibt ihn zurück, und printer[0] schaut den ersten an.
• Warum keine Liste mit pop(0)? pop(0) rückt alle anderen einen Platz nach vorne, wie das Einfügen vorne in der Lektion über Listen. deque entfernt vorne, ohne etwas zu verschieben.

Genauer, für Neugierige

• popleft auf einer leeren Queue bricht das Programm mit IndexError ab. Eine deque kann auch ein Stack sein: append und pop arbeiten am rechten Ende.

from collections import deque

clients = deque()
clients.append("Kunde 1")
clients.append("Kunde 2")
print("Letzter:", clients.pop())
print("Bedient:", clients.popleft())
try:
    clients.popleft()
except IndexError as e:
    print(f"IndexError: {e}")

Ausgabe

Letzter: Kunde 2
Bedient: Kunde 1
IndexError: pop from an empty deque

• Es gibt auch queue.Queue, aber das ist für Programme mit mehreren Threads, die einander Aufgaben weitergeben. Für eine gewöhnliche Queue nimmst du deque.

Probier es aus

Der Nächste an der Kasse

Die Kassiererin ruft den nächsten Kunden. Welche Methode nimmt ihn aus der Queue?

from collections import deque

checkout = deque()
checkout.append("Jonas")
checkout.append("Maria")
client = checkout.()
print(f"Du bist dran, {client}")

Prüfen

Sieh es dir an

Eine verkettete Liste von innen

Eine Liste hält die Elemente nebeneinander in einem Array. Darum verschiebt das Einfügen vorne alle anderen. Es geht auch anders: Jedes Element steckt in einem eigenen Objekt, das den Wert und einen Pfeil zum nächsten hält. So ein Objekt heißt Knoten:

class Node:
    def __init__(self, value, next):
        self.value = value
        self.next = next

Eine Liste aus Knoten heißt verkettete Liste. Es reicht, den ersten Knoten zu halten, head. Jeden nächsten findest du, indem du dem Pfeil next folgst. Der letzte zeigt auf None.

head = None
head = Node("Kaffee", head)
head = Node("Milch", head)
head = Node("Brot", head)

n = head
while n is not None:
    print(n.value)
    n = n.next

Schritt für Schritt, in Worten

1. Die Liste ist leer: head ist None.
2. Ein neuer Knoten: next ist der alte head (None), und head rückt auf den Knoten.
3. Der zweite Knoten zeigt auf den ersten. Im Speicher bewegt sich nichts: Nur die Pfeile ändern sich.
4. Auch der dritte Knoten kommt nach vorne: Der zuletzt hinzugefügte ist der erste.
5. n beginnt bei head und gibt jeden Knoten aus.
6. n erreicht None: Die Schleife endet.

• Einfügen vorne: ein neuer Knoten, dessen next auf den alten ersten zeigt, und head zeigt auf den neuen. Zwei Pfeile, und du verschiebst nichts.
• Durchlaufen: Du beginnst bei head und folgst next, bis du bei None ankommst.
• Der Preis: Knoten haben keine Indizes. Zum fünften Element kommst du, indem du durch die ersten vier gehst.

Die Idee

deque, und was wann

Python hat keine fertige verkettete Liste wie die Klasse Node. Es hat deque: Innen ist sie eine verkettete Liste, aber jeder Knoten hält nicht ein Element, sondern einen ganzen Block davon. Darum ist sie an beiden Enden schnell: append und appendleft, pop und popleft, [0] und [-1]:

from collections import deque

route = deque()
route.append("Nürnberg")
route.append("Leipzig")
route.appendleft("München")
route.append("Berlin")
print(list(route))

route.remove("Leipzig")
print("Nach der Änderung:", list(route))
print("Von", route[0], "nach", route[-1])

Ausgabe

['München', 'Nürnberg', 'Leipzig', 'Berlin']
Nach der Änderung: ['München', 'Nürnberg', 'Berlin']
Von München nach Berlin

Was wann:

• Eine Liste nach Nummer: list. Das ist die übliche Wahl.
• Ein Stack: list mit append und pop.
• Eine Queue: deque mit append und popleft.

Genauer, für Neugierige

• list(route) macht aus der Queue eine gewöhnliche Liste, damit sie als Liste ausgegeben wird. Ein einfaches print(route) gibt deque([...]).
• In CPython hält jeder Block einer deque 64 Elemente, und die Blöcke sind in beide Richtungen verkettet, zum nächsten und zum vorigen. Darum sind route[0] und route[-1] schnell, ein Element in der Mitte einer großen Queue aber langsam: Du erreichst es über die Blöcke.
• Der Knoten aus dieser Karte hat nur next. So eine Liste heißt einfach verkettet.

Probier es aus

Finde den Fehler

Die Funktion soll die Knoten zählen. Für die Liste Brot → Milch → Kaffee gibt sie 2 statt 3 zurück. Und bei einer leeren Liste bricht sie mit AttributeError ab. In welcher Zeile steckt der Fehler?

Wähle die Zeile mit dem Fehler.

1def count(head):2 count = 03 n = head4 while n.next is not None:5 count += 16 n = n.next7 return count

Prüfen

Übung

Stacks und Queues im Einsatz

Löse die Aufgaben in deinem Editor. Die Collection ist ein Feld der Klasse mit einem _ vorne.

1. Ein Spielzeugzug. Eine Klasse Train mit den Methoden add_wagon(wagon) und remove_wagon(). Der Zug ist ein Stack: Der zuletzt angekoppelte Wagen wird zuerst abgekoppelt. remove_wagon() gibt den abgekoppelten Wagen zurück, oder None, wenn keiner da ist. Füge count() hinzu. Kopple drei Wagen an und zwei ab.

Ausgabe

Abgekoppelt: Wagen 3
Abgekoppelt: Wagen 2
Wagen: 1

2. Eine Buslinie. Eine Klasse BusRoute mit einer Queue von Haltestellen und den Methoden add_stop(stop) und get_next_stop(), die die nächste Haltestelle zurückgibt, oder None, wenn die Strecke zu Ende ist. Füge „Hauptbahnhof“, „Rathaus“ und „Universität“ hinzu und fahr die Strecke ab.

Ausgabe

Nächster Halt: Hauptbahnhof
Nächster Halt: Rathaus
Nächster Halt: Universität
Ende der Strecke.

3. Ein Börsenticker. Eine Klasse StockTicker hält die letzten N Preise einer Aktie. Der Konstruktor bekommt das Symbol und N. update_price(price) fügt einen Preis hinzu, und wenn es mehr als N Preise sind, entfernt es den ältesten. Füge get_last_price() und average() für die gespeicherten Preise hinzu. Für SAP mit N = 3 übergib die Preise 150, 152, 149 und 155. Tipp: deque(maxlen=3) entfernt den ältesten von selbst, wenn es mehr als 3 sind. Gib die Preise mit zwei Nachkommastellen aus.

Ausgabe

SAP: letzter Preis 155.00 €
Durchschnitt der letzten 3: 152.00 €

4. Ausgeglichene Klammern. Ein Code-Editor prüft, ob die Klammern (), [] und {} in der richtigen Reihenfolge geschlossen sind. Schreib is_balanced(text) mit einem Stack: Eine öffnende Klammer legst du auf den Stack, bei einer schließenden nimmst du die oberste herunter und prüfst, dass sie von derselben Art ist. Am Ende muss der Stack leer sein. Lies drei Zeilen ein.

Eingabe

(1 + [2 * 3])
(1 + 2]
((5)

Ausgabe

(1 + [2 * 3]) -> ja
(1 + 2] -> nein
((5) -> nein

5. Deine eigene verkettete Liste. Eine Klasse MyLinkedList mit den Knoten aus der Lektion und den Methoden add(value) (am Ende), remove(value), contains(value), size() und __str__(). In remove findest du den Knoten vor dem gesuchten und lenkst sein next um. Prüf den Fall, dass der erste entfernt wird, gesondert.

Ausgabe

[Rechnung, Bericht, Besprechung]
Enthält Bericht: True
Nach dem Entfernen: [Rechnung, Besprechung]
Größe: 2

Weitere Aufgaben

• Rückgängig und Wiederholen. Halte zwei Stacks: undo und redo. Eine neue Aktion kommt in undo und leert redo. „Rückgängig“ verschiebt die oberste von undo nach redo, und „Wiederholen“ verschiebt sie zurück.
• Wörter rückwärts. Lies einen Satz ein und gib ihn mit den Wörtern in umgekehrter Reihenfolge aus, über einen Stack: „Heute ist Freitag“ wird zu „Freitag ist Heute“.
• Zwei Kassen. Kunden kommen nacheinander und gehen zu der Kasse mit der kürzeren Schlange. Gib aus, wer an welcher Kasse bedient wurde.
• Die verkettete Liste umdrehen. Füge MyLinkedList eine Methode reverse() hinzu, die die Pfeile umdreht, ohne neue Knoten anzulegen.

Test

Teste dich

1. Du legst A auf einen Stack, dann B, dann C. Was kommt bei pop zuerst heraus?

ACB

2. Welche Aufgabe passt zu einer Queue?

Die letzte Aktion rückgängig machenDruckaufträge, die in der Reihenfolge ihres Eingangs gedruckt werdenDer Button „Zurück“ im Browser

3. Was passiert bei popleft() auf einer leeren deque?

Es gibt 0 zurückDas Programm bricht mit IndexError abEs gibt None zurück

4. Warum ist das Einfügen am Anfang einer verketteten Liste schnell?

Weil die Liste sich selbst sortiertWeil du einen neuen Knoten anlegst und zwei Pfeile umsetzt, ohne die anderen Elemente anzufassenWeil die Elemente im Speicher nebeneinander liegen

5. Was ist in einer verketteten Liste langsam?

Ein Element über seine Nummer holen, zum Beispiel das fünfhundertsteDas erste Element entfernenAm Anfang hinzufügen

Prüfen

Lektion von vorn beginnen

Verwandte Lektionen

• Baut auf: Polymorphie · Interfaces als abstrakte Klassen · Exceptions · Listen: append, remove und sort
• Geht weiter in: Hashcodes und Hashfunktionen · Klassen und Daten in Klassen · Command · Speicherkomplexität
• Aufgaben zum Thema: Collections