stack-datenstruktur

Stack (Stapel)

Kurz: Ein Stack ist eine Datenstruktur nach dem Prinzip LIFO (Last In, First Out): Das zuletzt abgelegte Element wird als erstes wieder entnommen – wie ein Stapel Teller.

Genauer: Es gibt nur zwei Hauptoperationen: push legt ein Element oben auf den Stapel, pop entfernt das oberste. Mit peek schaut man nach oben, ohne es zu entfernen. Stacks sind überall zu finden: im Aufrufstapel jedes Programms, in der Rückgängig-Funktion von Editoren und beim Auswerten von Klammerausdrücken.

Im Detail

Ein Stack lässt sich mit einem Array oder einer verketteten Liste umsetzen; beide Varianten bieten push und pop in konstanter Zeit O(1) (siehe Big-O-Notation).

stapel = []
stapel.append("A")   # push
stapel.append("B")
stapel.append("C")
print(stapel.pop())  # C  (zuletzt hinein, zuerst heraus)
print(stapel[-1])    # B  (peek)
print(len(stapel))   # 2

Typische Anwendungen

• Aufrufstapel (Call Stack): Jeder Funktionsaufruf legt einen Rahmen mit lokalen Variablen und Rücksprungadresse auf den Stack; bei return wird er entfernt. Zu tiefe Rekursion führt zum Stack Overflow (siehe Stack und Heap).
• Klammerprüfung: Öffnende Klammern auf den Stack legen, bei schließenden das oberste Element vergleichen.
• Rückgängig/Wiederholen (Undo/Redo) mit zwei Stacks.
• Tiefensuche in Bäumen und Graphen (Baum, Graph) und Auswertung der umgekehrten polnischen Notation.

def klammern_ok(text):
    paare = {")": "(", "]": "[", "}": "{"}
    s = []
    for c in text:
        if c in "([{":
            s.append(c)
        elif c in paare:
            if not s or s.pop() != paare[c]:
                return False
    return not s
 
print(klammern_ok("{[()]}"))   # True
print(klammern_ok("([)]"))     # False

Siehe auch: Queue, Datenstrukturen, Stack und Heap, Rekursion