Stacks und Queues in Python: Zwei fundamentale Datenstrukturen

Fast jedes Programm muss irgendwann eine Sammlung von Elementen in einer bestimmten Reihenfolge verwalten: rückgängig gemachte Aktionen, wartende Aufgaben, aufgerufene Funktionen. Zwei Datenstrukturen tauchen dabei immer wieder auf – der Stack und die Queue. Beide sind einfach zu verstehen, aber der Unterschied in der Reihenfolge, in der du Elemente wieder herausbekommst, entscheidet über den passenden Einsatz. In diesem Beitrag lernst du beide Strukturen kennen, setzt sie sauber in Python um und verstehst, wann du welche brauchst.

Was ist ein Stack?

Ein Stack (Stapel) folgt dem Prinzip LIFO – Last In, First Out. Das zuletzt hinzugefügte Element wird als Erstes wieder entfernt. Stell dir einen Stapel Teller vor: Du legst neue Teller oben drauf und nimmst sie auch von oben wieder weg. An den untersten Teller kommst du erst, wenn alle darüber weg sind.

Ein Stack kennt im Kern zwei Operationen: push legt ein Element oben ab, pop nimmt das oberste Element weg. In Python kannst du dafür direkt eine Liste verwenden, denn append() und pop() arbeiten beide am Ende der Liste und sind sehr effizient.

stack = []

# push: Elemente oben drauflegen
stack.append("a")
stack.append("b")
stack.append("c")

print(stack)        # ['a', 'b', 'c']

# pop: oberstes Element entfernen
oben = stack.pop()
print(oben)         # 'c'
print(stack)        # ['a', 'b']

Wichtig ist, dass du bei pop() keinen Index angibst – dann wird immer das letzte Element genommen. Genau das brauchst du für LIFO.

Einen Stack als eigene Klasse

Eine nackte Liste funktioniert, aber sie erlaubt auch Dinge, die ein echter Stack nicht können sollte – etwa den wahllosen Zugriff per Index. Mit einer kleinen Klasse machst du die Absicht klar und schützt dich vor Fehlern wie dem pop() auf einem leeren Stack.

class Stack:
    def __init__(self):
        self._items = []

    def push(self, item):
        self._items.append(item)

    def pop(self):
        if self.is_empty():
            raise IndexError("pop aus leerem Stack")
        return self._items.pop()

    def peek(self):
        # oberstes Element ansehen, ohne es zu entfernen
        return self._items[-1]

    def is_empty(self):
        return len(self._items) == 0

    def __len__(self):
        return len(self._items)


s = Stack()
s.push(1)
s.push(2)
print(s.peek())     # 2
print(s.pop())      # 2
print(len(s))       # 1

Die Methode peek ist praktisch, wenn du nur wissen willst, was oben liegt, ohne es wegzunehmen. Beachte auch, dass alle Operationen konstante Laufzeit O(1) haben – unabhängig davon, wie groß der Stack ist.

Ein klassisches Stack-Problem: Klammern prüfen

Stacks glänzen überall dort, wo etwas zuletzt Geöffnetes zuerst wieder geschlossen werden muss. Ein Paradebeispiel ist die Prüfung, ob Klammern in einem Ausdruck korrekt verschachtelt sind. Jede öffnende Klammer legst du auf den Stack, bei jeder schließenden prüfst du, ob oben die passende öffnende liegt.

def klammern_gueltig(text):
    paare = {")": "(", "]": "[", "}": "{"}
    stack = []
    for zeichen in text:
        if zeichen in "([{":
            stack.append(zeichen)
        elif zeichen in ")]}":
            if not stack or stack.pop() != paare[zeichen]:
                return False
    return len(stack) == 0


print(klammern_gueltig("(a[b]{c})"))   # True
print(klammern_gueltig("(a[b)]"))      # False
print(klammern_gueltig("((("))         # False

Am Ende muss der Stack leer sein – sonst gibt es noch offene Klammern ohne Gegenstück. Dieses Muster steckt in echten Werkzeugen wie Compilern und Code-Editoren.

Was ist eine Queue?

Eine Queue (Warteschlange) folgt dem umgekehrten Prinzip FIFO – First In, First Out. Das zuerst hinzugefügte Element wird als Erstes wieder entfernt, genau wie bei einer Schlange an der Kasse: Wer zuerst kommt, wird zuerst bedient.

Hier lauert eine Falle: Du könntest eine Liste nehmen und mit append() hinten anfügen und mit pop(0) vorne entfernen. Das funktioniert, ist aber langsam – pop(0) muss alle übrigen Elemente um eine Position nach vorn schieben und hat damit Laufzeit O(n). Für Queues nutzt du deshalb collections.deque, das an beiden Enden in O(1) arbeitet.

from collections import deque

queue = deque()

# enqueue: hinten anstellen
queue.append("Anna")
queue.append("Ben")
queue.append("Carla")

# dequeue: vorne bedienen
print(queue.popleft())   # 'Anna'
print(queue.popleft())   # 'Ben'
print(queue)             # deque(['Carla'])

Der Schlüssel ist popleft(): Es entfernt das linke (älteste) Element effizient. Mit append() und popleft() hast du eine vollwertige, schnelle Queue.

Wann nutzt du was?

Die Wahl hängt allein davon ab, in welcher Reihenfolge du die Elemente wieder brauchst:

• Stack (LIFO): Undo-/Redo-Funktionen, der Aufrufstapel bei Funktionsaufrufen, das Auswerten von Ausdrücken, Backtracking-Algorithmen und die Tiefensuche (DFS) in Graphen.
• Queue (FIFO): Aufgaben-Warteschlangen, Druckaufträge, das Puffern von Daten, Nachrichtensysteme und die Breitensuche (BFS) in Graphen.

Eine kleine Merkhilfe: Wenn die jüngste Aufgabe Vorrang hat, nimmst du einen Stack. Wenn Fairness nach Ankunftszeit zählt, nimmst du eine Queue. Übrigens verwendet Python intern selbst einen Stack, um sich zu merken, welche Funktion welche aufgerufen hat – deshalb heißt die Fehlermeldung bei zu tiefer Rekursion auch RecursionError: maximum recursion depth exceeded.

Fazit

Stacks und Queues sind zwei der grundlegendsten Datenstrukturen überhaupt, und der einzige echte Unterschied liegt in der Reihenfolge: LIFO beim Stack, FIFO bei der Queue. In Python bekommst du einen Stack fast geschenkt mit einer einfachen Liste und ihren append()/pop()-Methoden, während du für Queues am besten collections.deque mit append() und popleft() greifst. Wenn du das nächste Mal wartende Aufgaben, verschachtelte Strukturen oder eine Undo-Funktion umsetzt, weißt du jetzt, welches Werkzeug passt – und warum.