Stack: LIFO und typische Fehler

Ein Stack speichert Elemente nach dem LIFO-Prinzip: das zuletzt eingefügte Element wird zuerst entfernt. Typische Operationen sind push (oben ablegen), pop (oben entfernen und liefern) und peek oder top (oben lesen ohne Entfernen).

Anwendungsfälle: Klammerprüfung, Undo-Puffer, Auswertung von Postfix-Ausdrücken, Laufzeitstapel bei Methodenaufrufen.

Beispielspur: push(A), push(B), pop liefert B, peek liefert A.

Randfall: pop oder peek auf einem leeren Stack ist ein Underflow. Die Spezifikation muss festlegen, ob eine Exception geworfen oder ein Sonderwert geliefert wird.

$$\operatorname{pop}(\operatorname{push}(S,x))=x$$

Wo gebraucht

Call Stack der JVM, Undo-Puffer in Editoren, Auswertung von Ausdrücken und DFS mit explizitem Stack. In Compilern und Interpretern ist LIFO der Standard für geschachtelte Kontextwechsel. Leeres Pop ohne Prüfung ist ein klassischer Produktionsfehler in Parsern.

Vertiefung

Bei einem LIFO-Speicher ist nur das zuletzt eingefügte Element direkt zugänglich. Diese Einschränkung ist nützlich: Verschachtelte Strukturen, Rücksprungpunkte und noch offene Teilprobleme werden genau in umgekehrter Entstehungsreihenfolge abgearbeitet.

Eine zentrale Invariante lautet, dass top stets das nächste zu entfernende Element bezeichnet oder eindeutig den leeren Zustand codiert. Ob top auf das oberste belegte Feld oder auf das erste freie Feld zeigt, ist eine Implementierungsentscheidung, die in allen Operationen konsistent sein muss.

Ein Überlauf betrifft eine feste Kapazität, ein Unterlauf den Zugriff auf einen leeren Speicher. Bibliotheksimplementierungen wachsen meist dynamisch, können aber weiterhin durch Speichergrenzen scheitern. Anwendungen sollten leere Zustände nicht mit einem regulären Rückgabewert verwechseln.

Schwierigkeitsstufen

1. Eine Folge von Einfüge- und Entnahmeoperationen simulieren.
2. Die top-Invariante für zwei Indexkonventionen angeben.
3. Einen Parser oder eine iterative Tiefensuche mit diesem Prinzip begründen.

Fallstricke

Häufig werden Prüfung und Entnahme getrennt, obwohl sich der Zustand dazwischen ändern kann. Ebenso führt ein uneinheitlich interpretierter top-Index zu Off-by-one-Fehlern.