Stapel (Stack): LIFO, Operationen und Anwendungen

Ein Stack arbeitet nach dem LIFO-Prinzip. LIFO steht für „Last In, First Out“, auf Deutsch „zuletzt hinein, zuerst heraus“. Von den noch vorhandenen Werten wird der zuletzt abgelegte zuerst entnommen. Nach seiner Entnahme ist der unmittelbar darunterliegende Wert oben.

Eine Warteschlange arbeitet nach dem FIFO-Prinzip. FIFO steht für „First In, First Out“, also „zuerst hinein, zuerst heraus“. Von den noch vorhandenen Werten wird der zuerst eingefügte zuerst entnommen. Stack und Warteschlange unterscheiden sich damit durch ihre Entnahmereihenfolge. Beide Regeln richten sich nach dem Einfügen, nicht nach der Größe eines Zahlenwerts.

Die Operationen eines Stacks sind festgelegte Aktionen. push legt einen Wert oben ab. Bei einem nicht leeren Stack liefert pop den obersten Wert zurück und entfernt ihn. peek liefert bei einem nicht leeren Stack den obersten Wert zurück, ohne ihn zu entfernen. Ein Rückgabewert ist das Ergebnis, das eine Operation an den aufrufenden Ablauf liefert. pop und peek unterscheiden sich somit darin, ob sie den gespeicherten Inhalt verändern.

Wir schreiben Stack-Zustände in eckigen Klammern: Bei [18, 35] liegt 18 unten und 35 oben. Die Oberseite steht rechts. [] bezeichnet den leeren Stack. push(x) bedeutet: Lege den Wert x oben ab. Bei pop() und peek() stehen keine Angaben in den runden Klammern, weil kein einzufügender Wert benötigt wird. Diese Schreibweisen beschreiben Operationen; sie sind kein vollständiges ausführbares Programm.

Die folgenden Abläufe verwenden pop() und peek() bei einem nicht leeren Stack. Den Leerfall legen wir im Abschnitt zur Implementierung ausdrücklich fest. Auch der Rückgabewert von push ist hier nicht festgelegt.

Eine Anwendung ist das Speichern von Rücksprungadressen. Eine Rücksprungadresse gibt an, an welcher Stelle ein Programm nach einem Aufruf weitergehen soll. Ein Unterprogramm ist ein benannter Programmteil, der eine Aufgabe erledigt. Wir betrachten einen Ablauf, bei dem Aufrufe ihre Rücksprungadressen auf einem Stack ablegen. Ruft ein Unterprogramm ein weiteres auf, liegt dessen Rücksprungadresse oben. Beim Zurückkehren wird sie zuerst entnommen. Der aufrufende Programmteil läuft an der Stelle nach dem Aufruf weiter, nicht wieder an seinem Anfang.

Ein Stack kann auch Rechenausdrücke in Postfixnotation auswerten. Dabei stehen Zahlen vor dem zugehörigen Rechenzeichen. Die Folge „8 3 −“ bedeutet zum Beispiel 8-3=5. Lies die Folge von links nach rechts. Lege jede Zahl auf den Stack. Ein Rechenzeichen für zwei Zahlen nimmt zuerst den rechten, dann den linken Rechenwert herunter. Berechne linker Wert minus rechter Wert bei einer Subtraktion; ein Pluszeichen verlangt entsprechend eine Addition. Lege das Ergebnis wieder oben ab.

Wir betrachten gültige Folgen mit Plus- und Minuszeichen: Bei jedem Rechenzeichen müssen mindestens zwei Werte bereitliegen. Nach der vollständigen Auswertung bleibt genau ein Ergebnis auf dem Stack. Die Reihenfolge der Zahlen und Zeichen legt die Rechnung fest. Zusätzliche Klammern und Vorrangregeln wie „Punkt vor Strich“ werden für diese Schreibweise nicht benötigt.

Eine Implementierung ist die konkrete Umsetzung der beschriebenen Regeln in einem Programm. Wir beschreiben ein Beispiel in Python, einer Programmiersprache. Es speichert die Stack-Werte in einer dynamisch erweiterbaren Liste. Das bedeutet: Die Liste kann beim Einfügen wachsen, soweit Speicher verfügbar ist. Ihr Ende dient als Oberseite. push hängt dort einen Wert an. Bei einem nicht leeren Stack entfernt pop den letzten Listeneintrag und liefert ihn zurück; peek liest ihn ohne Entfernen.

Vor dem Entfernen oder Lesen prüft dieses Beispiel, ob die Liste leer ist. Dann liefern pop und peek den besonderen Python-Wert None zurück und lassen den Stack leer. None bedeutet hier „kein Wert vorhanden“. Für unsere Abläufe speichern wir Zahlen. 0 ist dabei eine gültige Zahl und kein Zeichen für einen leeren Stack. [] beschreibt den leeren Listeninhalt; es ist hier nicht der Rückgabewert von pop oder peek. Würde man auch None als Eintrag zulassen, könnte man am Rückgabewert allein einen solchen Eintrag nicht vom Leerfall unterscheiden.

Diese Behandlung des Leerfalls ist eine Festlegung dieses Beispiels. Andere Implementierungen können einen Fehler melden. Auch eine erweiterbare Liste hat keinen unbegrenzten Speicher. Für eine zusätzliche Variante mit fester Platzanzahl legen wir fest: push prüft vor dem Einfügen, ob noch ein Platz frei ist. Ist der Stack voll, meldet die Operation „voll“ und lässt den Inhalt unverändert. Ein voller Stack ist dabei nicht dasselbe wie ein leerer Stack.