Stapel (Stack): LIFO, Operationen und Anwendungen

Stell dir einen Stapel aus Umzugskisten vor. Eine neue Kiste stellst du oben ab. Willst du eine Kiste entnehmen, erreichst du ebenfalls zuerst die oberste. Eine weiter unten liegende Kiste wird erst zugänglich, nachdem du alle Kisten über ihr entfernt hast.

Die Wörter „oben“ und „unten“ beschreiben die logische Ordnung. Ein gezeichneter Stack kann nach oben, nach unten oder zur Seite wachsen, ohne dass sich sein Verhalten ändert.

Ein Stack ist ein abstrakter Datentyp: Seine erlaubten Operationen und deren Wirkung werden festgelegt, ohne eine bestimmte technische Implementierung vorzuschreiben. Er kann beispielsweise mit einem Array oder einer verketteten Liste umgesetzt werden.

Drei Operationen bilden den Kern eines Stacks:

• push(x) legt das Element x oben auf den Stack.
• pop() liefert das oberste Element und entfernt es.
• peek() oder top() liefert das oberste Element, entfernt es aber nicht.

Häufig gibt es zusätzlich eine Prüfung wie is_empty(), die feststellt, ob der Stack leer ist.

Bei längeren Folgen hilft eine Zustandsliste. Notiere die Elemente stets in derselben Richtung, zum Beispiel von unten nach oben. Ändere nur das obere Ende.

So vermeidest du typische Fehler

1. Markiere eindeutig, welches Ende oben ist.
2. Führe die Operationen in der angegebenen Reihenfolge aus.
3. Schreibe bei pop zuerst den Rückgabewert auf und entferne ihn dann aus deinem Zustandsbild.
4. Verändere den Stack bei peek nicht.

Ein Stack passt zu Aufgaben, bei denen der jüngste gespeicherte Zustand zuerst wieder gebraucht wird.

Browser und Rücksprünge

Bei einer vereinfachten Zurück-Funktion wird die zuvor besuchte Seite auf einem Stack gespeichert. Beim Zurückgehen wird die zuletzt gespeicherte Seite zuerst wieder aufgerufen.

Auch verschachtelte Unterprogramm- oder Methodenaufrufe folgen diesem Muster. Zu einem Aufruf wird eine Rücksprungadresse gespeichert. Ruft das Unterprogramm ein weiteres Unterprogramm auf, kommt dessen Rücksprungadresse obenauf. Der zuletzt begonnene Aufruf muss zuerst enden, damit die Rückkehrreihenfolge stimmt.

Ausdrücke und verschachtelte Strukturen

Stacks können Operanden und Operatoren bei der Auswertung mathematischer Ausdrücke zwischenspeichern. Ebenso helfen sie dabei, korrekt verschachtelte Strukturen zu prüfen: Eine zuletzt geöffnete Struktur muss zuerst wieder geschlossen werden.

Stack oder Warteschlange?

Eine Warteschlange entnimmt das älteste Element zuerst. Dieses Prinzip heißt FIFO: First In, First Out. Beim Stack wird dagegen das jüngste Element zuerst entnommen.

Die abstrakten Operationen bleiben gleich, auch wenn die interne Darstellung wechselt.

Umsetzung mit einem Array

Ein Array kann die Elemente zusammenhängend speichern. Eine Zählvariable gibt an, wie viele Plätze belegt sind. push schreibt an die nächste freie Stelle und erhöht die Zahl der Elemente. pop verringert sie und liefert das zuvor oberste Element.

Ist das Array voll, muss die Implementierung den Stack vergrößern oder den Einfügeversuch eindeutig ablehnen. Bei dynamischer Vergrößerung können einzelne Operationen wegen des Kopierens länger dauern. Bei üblichen Implementierungen besitzen push und pop im Normalfall konstanten Aufwand, also $O(1)$.

Umsetzung mit einer verketteten Liste

Bei einer einfach verketteten Liste verweist top auf den obersten Knoten. Jeder Knoten enthält einen Wert und einen Verweis auf den darunterliegenden Knoten.

Für push(x):

1. Erzeuge einen neuen Knoten mit dem Wert x.
2. Lass ihn auf den bisherigen obersten Knoten verweisen.
3. Setze top auf den neuen Knoten.

Für pop():

1. Prüfe zuerst, ob top leer ist.
2. Merke den Wert des obersten Knotens.
3. Setze top auf dessen Nachfolger.
4. Liefere den gemerkten Wert.

Diese Reihenfolge behandelt auch einen Stack mit genau einem Element: Dessen Nachfolger ist leer, also wird der Stack nach pop() korrekt leer.

Unterlauf und Überlauf

Ein pop() oder peek() auf einem leeren Stack verursacht einen Stack-Unterlauf, wenn dieser Fall nicht abgefangen wird. Eine Implementierung muss dafür ein eindeutiges Verhalten festlegen, etwa einen Fehler auszulösen oder ausdrücklich einen besonderen Rückgabewert zu verwenden. Ein regulär speicherbarer Wert wie 0 eignet sich nicht ohne zusätzliche Kennzeichnung als Fehlersignal.

Ein Stack-Überlauf entsteht, wenn mehr Speicher benötigt wird, als für den Stack verfügbar ist. Das kann beispielsweise bei sehr tiefer Verschachtelung oder Rekursion geschehen.

Du beherrschst den Kern des Stacks, wenn du bei jeder Operationsfolge zuerst das obere Element bestimmst, peek und pop auseinanderhältst und den Leerfall ausdrücklich prüfst.