Die Datenstruktur Stapel (stack) in Python
In dieser Lektion implementierst du mit einer Python-Liste die Grundoperationen eines Stapels: ablegen (push), entnehmen (pop) und das oberste Element ansehen (peek).
Einführung
Das Problem
Rückgängig-Knöpfe, der Zurück-Knopf im Browser und das Prüfen passender Klammern müssen sich Elemente merken und das neueste zuerst zurückgeben. Ein Stack ist genau dafür gebaut.
Stell es dir so vor
Ein Stack ist wie ein Tellerstapel in der Kantine. Neue Teller legst du oben drauf, und du nimmst Teller von oben. Der zuletzt hingelegte Teller wird zuerst benutzt, und aus der Mitte kannst du keinen herausziehen.
stack.append("third")🍽️ Einen Teller oben drauflegenstack.pop()⬆️ Den obersten Teller nehmenstack[-1]👀 Den obersten Teller ansehen, ohne ihn zu nehmenstack📚 Die Teller, die noch auf dem Stapel liegenEin Stack ist eine Last-in-first-out-Sammlung (LIFO): Elemente werden nur oben hinzugefügt und entfernt.
Das Wichtigste
stack.append(...)legt ein Element oben drauf, also ans Ende der Liste.stack.pop()entfernt das oberste Element und gibt es zurück, hier"third".stack[-1]liest das oberste Element, ohne es zu entfernen.appendundpoparbeiten beide am Ende der Liste, deshalb sind sie schnell.
Wann verwendet man das?
- Verläufe für Rückgängig und Wiederholen.
- Passende Klammern prüfen und Ausdrücke parsen.
- Tiefensuche und Backtracking ohne Rekursion.
Wann du es nicht brauchst
- Elemente sollen in der Reihenfolge ihres Eintreffens herauskommen: Das ist eine Queue.
- Du brauchst Elemente aus der Mitte oder nach Position: Eine normale Liste oder eine andere Struktur passt besser.
So funktioniert es
Mit push und pop siehst du, dass das zuletzt hineingelegte Element immer zuerst herauskommt.
Beispielcode
stack = []
stack.append("first")
stack.append("second")
stack.append("third")
print("popped:", stack.pop())
print("top:", stack[-1])
print("stack:", stack)
Ergebnis der Ausführung
popped: third
top: second
stack: ['first', 'second']
Erklärung des Codes
Die Methode append() legt ein Element oben auf den Stapel, und pop() entnimmt das oberste Element und entfernt es, deshalb kommt "third" zuerst heraus. Mit stack[-1] siehst du das oberste Element an, ohne es zu entfernen. Die Operationen append() und pop() am Ende der Liste haben im Durchschnitt die Komplexität O(1).
Ändere die Werte und führe das Programm im CodeUtility Python Online-Compiler aus, ohne Python lokal zu installieren.
Übungen zur Vertiefung
Ändere den Code anhand der folgenden Vorschläge. Wenn du selbst etwas änderst und das Ergebnis beobachtest, verstehst du viel mehr, als wenn du den Code nur liest.
- Teste mit einer leeren Liste, einer Liste mit nur einem Element und einer Liste mit doppelten Werten.
- Gib den Zustand nach jedem Schritt aus, um den Algorithmus bei der Arbeit zu beobachten.
- Miss die Laufzeit mit 100, 1.000 und 10.000 Elementen und vergleiche sie mit einer anderen Lösung.
Häufige Fehler
pop auf einem leeren Stack
pop() auf einer leeren Liste löst einen IndexError aus.
item = stack.pop()
if stack:
item = stack.pop()
Den Anfang der Liste als oberes Ende nutzen
insert(0, x) und pop(0) verschieben jedes Element, das ist langsam.
stack.insert(0, item)
stack.pop(0)
stack.append(item)
stack.pop()
Lektion fertig?
Markiere sie als gelernt, um deinen Fortschritt zu verfolgen.
Mit einer Challenge üben
Nutze den Inhalt dieser Lektion, um ein echtes Problem zu lösen. Jede Challenge läuft im Browser, mit sofortigen Tests und einem KI-Review.
- Nearest Smaller Value to the Left For each number, find the closest earlier position containing a strictly smaller number. Mittel
- Mini Stack-Language Interpreter Evaluate a small stack language. Schwierig