Python-Algorithmen

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).

  • Fortgeschritten
  • 2 Min. Lesezeit
  • 1 ausführbares Beispiel

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.

Vom Tellerstapel zum Code
stack.append("third")🍽️ Einen Teller oben drauflegen
stack.pop()⬆️ Den obersten Teller nehmen
stack[-1]👀 Den obersten Teller ansehen, ohne ihn zu nehmen
stack📚 Die Teller, die noch auf dem Stapel liegen
Last in, first out: Nur das oberste Element ist erreichbar.
In einem Satz

Ein Stack ist eine Last-in-first-out-Sammlung (LIFO): Elemente werden nur oben hinzugefügt und entfernt.

Das Wichtigste

  1. stack.append(...) legt ein Element oben drauf, also ans Ende der Liste.
  2. stack.pop() entfernt das oberste Element und gibt es zurück, hier "third".
  3. stack[-1] liest das oberste Element, ohne es zu entfernen.
  4. append und pop arbeiten 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

Code ausführen →
main.py
stack = []
stack.append("first")
stack.append("second")
stack.append("third")

print("popped:", stack.pop())
print("top:", stack[-1])
print("stack:", stack)
Run-Button für dieses Beispiel erstellen

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.

  1. Teste mit einer leeren Liste, einer Liste mit nur einem Element und einer Liste mit doppelten Werten.
  2. Gib den Zustand nach jedem Schritt aus, um den Algorithmus bei der Arbeit zu beobachten.
  3. Miss die Laufzeit mit 100, 1.000 und 10.000 Elementen und vergleiche sie mit einer anderen Lösung.
Im Python-Compiler ausführen →

Häufige Fehler

pop auf einem leeren Stack

pop() auf einer leeren Liste löst einen IndexError aus.

Problem
item = stack.pop()
Lösung
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.

Problem
stack.insert(0, item)
stack.pop(0)
Lösung
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.

Alle Challenges