Stapelüberlauf

Vereinfachte Darstellung eines Stacks mit den Funktionen Push (drauflegen) und Pop (runternehmen)

In der Informatik bezeichnet ein Stapelspeicher oder Kellerspeicher (kurz Stapel oder Keller, häufig auch mit dem englischen Wort Stack bezeichnet) eine häufig eingesetzte Datenstruktur. Sie wird von den meisten Mikroprozessoren in der Hardware direkt unterstützt.

Funktionsprinzip

Ein Stapel kann eine theoretisch beliebige, in der Praxis jedoch immer begrenzte Menge von gleich großen Informationsstrukturen (Objekte) aufnehmen und gibt diese, in entgegengesetzter Reihenfolge zur Aufnahme, wieder zurück.

Dazu werden folgende Operationen zur Verfügung gestellt: push (auch einkellern) ist das Hinzufügen eines Objektes auf den Stapel. pop (auskellern) holt und entfernt ein Objekt vom Stapel. Bei manchen Prozessoren wie dem MOS Technology 6502 wird diese Aktion dagegen pull (herunterziehen) genannt. peek (nachsehen) holt ein Objekt, ohne es zu entfernen. Letzteres ist in vielen Implementationen vorhanden.

Es wird nach dem Last In – First Out-Prinzip (deutsch zuletzt hinein – zuerst heraus, kurz LIFO) gearbeitet: Bei pop wird immer das Objekt aus dem Stapel zurückgegeben, welches als letztes mit push hineingelegt wurde, ähnlich wie bei einem Bücherstapel.

In der theoretischen Informatik werden Stapel benutzt, um bestimmte Problemklassen theoretisch betrachten zu können (vgl. Kellerautomat). Sie unterscheidet deshalb genauer zwischen einem echten Kellerspeicher (kurz Keller), bei dem kein Element außer dem obersten gelesen werden kann, und einem Stapelspeicher, bei dem jedes Element betrachtet, aber nicht verändert werden kann. In der Praxis spielt diese Unterscheidung jedoch kaum eine Rolle, beinahe jede Implementation ist ein Stapel. Daher werden die Begriffe im Allgemeinen synonym verwendet.

Illustration

Skizze eines Stapels

Ein Stapelspeicher ist mit einem Stapel von Umzugskisten vergleichbar. Es kann immer eine neue Kiste oben auf den Stapel gepackt werden (entspricht push) oder eine Kiste von oben heruntergenommen werden (entspricht pop). Der Zugriff ist im Regelfall nur auf das oberste Element des Stapels möglich. Ein Hinzufügen oder Entfernen einer Kiste weiter unten im Stapel ist nicht möglich. Es gibt aber Befehle, die beiden obersten Elemente zu vertauschen (SWAP, ROT).

Geschichte

Die Verwendung eines Stapelspeichers zur Übersetzung von Programmiersprachen wurde 1957 von Friedrich Ludwig Bauer und Klaus Samelson unter dem Namen „Kellerprinzip“ patentiert ^[1] und etwa zur selben Zeit unabhängig vom australischen Philosophen Charles Hamblin entdeckt. Die lange ausgebliebene internationale Anerkennung und Ehrung ihrer Leistung erfolgte erst im Jahre 1988. Friedrich Ludwig Bauer erhielt den legendären Computer Pioneer Award (IEEE) für Computer Stacks. Samelson war inzwischen verstorben.

Anwendungen

Mithilfe des Stapelspeichers lassen sich einfach Terme oder Syntaxen auf richtige Verschachtelung prüfen, so wie es oft im Internet bei BB-Codes oder XML-Dokumenten der Fall ist.

Mikroprozessoren

In Mikroprozessoren gibt es dazu oft ein spezielles Register, den Stackpointer (Stapelzeiger). Dieses Register enthält eine Speicheradresse, die auf den gerade obersten Stapeleintrag zeigt. Wird die Operation push aufgerufen, die ein weiteres Objekt auf dem Stapel ablegt, so wird der Stackpointer auf die benachbarte freie Zelle versetzt und der neue Wert dorthin geschrieben. Bei pop wird der Eintrag der Adresse gelesen und anschließend der Stapelzeiger versetzt, so dass er auf den benachbarten, nun letzten Stapeleintrag zeigt. Dieses Register kann im Allgemeinen auch direkt gesetzt werden.

Die Implementierung eines Stapels entspricht nicht der intuitiven Annahme, dass auf einen Stapel gelegte Daten eine höhere Adresse erhalten. In den meisten Prozessoren beginnt der Stapel bei einer betragsmäßig hohen Adresse und wird in Richtung der Adresse 0 gestapelt. Das bedeutet, dass bei push der Stapelzeiger vermindert und bei pop erhöht wird. Der Stapel wächst „nach unten“, in Richtung niedrigerer Speicheradressen. Dies ist historisch begründet: Legt man bei begrenztem Speicher den Stack an die höchstmögliche Adresse, minimiert man die Wahrscheinlichkeit, dass andere Programmdaten (die z. B. hinter dem Programm abgelegt werden) mit dem Stapel kollidieren.

Der Stapel des Mikroprozessors wird oft von diesem selbst bei Aufruf und Rücksprung von Unterprogrammen zur Speicherung der Rücksprungadresse genutzt, ohne dass ein zusätzliches push oder pop zum Ablegen oder Holen dieser Rücksprungadresse nötig ist, da die entsprechenden Anweisungen das Register selbst richtig setzen. Die Programmiersprache Forth basiert auf einem zusätzlichen Stapel, auf dem die Operanden und Ergebnisse der mathematischen Operationen abgelegt werden.

In Multitasking-Systemen gibt es für jedes Programm einen eigenen Stapelspeicher. Beim Umschalten zwischen Prozessen wird neben anderen Registern auch der Stapelzeiger des fraglichen Prozesses geladen.

Um Fehler in der Benutzung des Stacks durch einen „Unterlauf“ des Stapelzeigers aufzudecken, legen manche Betriebssysteme wie z. B. OSEK-OS als untersten Wert im Stapel die Sprungadresse einer Fehlerbehandlungsroutine ab. Holt der Prozessor durch einen Fehler in der Aufrufverschachtelung diese Adresse vom Stapel, kann ggfs. noch auf den Ablauffehler reagiert werden.

Um den Nutzungsgrad des meist begrenzten Stapelspeichers zu ermitteln, bedient man sich der sogenannten Wasserstands-Methode: Der gesamte für den Stapelspeicher reservierte Speicher wird mit einem fixen Datenmuster initialisiert und dann das Programm gestartet. Anhand der Bereiche, die nach einer gewissen Laufzeit noch das Initialisierungsmuster enthalten, kann festgestellt werden, wie viel Platz auf dem Stapel wirklich genutzt wurde.

Moderne Programmiersprachen

Compiler für moderne Programmiersprachen nutzen gewöhnlich push- und pop-Operationen vor dem Aufruf eines Unterprogramms, um an dieses Parameter zu übergeben. Ähnlich können so auch Ergebnisse des Unterprogramms zurückgegeben werden. Lokale Variablen, zum Beispiel von Unterprogrammen, werden ebenfalls auf dem Stapel gespeichert. Für rekursive Programmierung wird dieser Mechanismus nochmal erweitert, indem auch für die lokalen Variablen des Unterprogramms auf dem Stapelspeicher Platz reserviert wird. Bei der Umwandlung einer rekursiven Funktion in eine iterative Funktion muss dieser Mechanismus häufig explizit implementiert werden.

Implementierbeispiel eines Stacks in Java

public class Stack {
    private class StackElement {
        private int value;
        private StackElement next;
 
        public StackElement(int value) {
            this.value = value;
            this.next = null;
        }
 
        public void setNext(StackElement next) {
            this.next = next;
        }
 
        public int getValue() {
            return value;
        }
 
        public StackElement getNext() {
            return this.next;
        }
    }
 
    private StackElement top;
 
    public Stack() {
        this.top = null;
    }
 
    public boolean isEmpty() {
        return (top == null);
    }
 
    public void push(int value) {
        StackElement tmp = new StackElement(value);
        tmp.setNext(top);
        this.top = tmp;
    }
 
    public void pop() {
        if (this.top == null)
            return;
 
        this.top = top.getNext();
    }
 
    public int top() {
        return top.getValue();
    }
}

Compiler

Zur Übersetzung des Quellcodes einer Formalen Sprache nutzen Compiler und Interpreter einen Parser, der bei der Textanalyse Syntax-Regeln auf einem Stapel ablegt und so vergleichend dem nachfolgenden Textelement eine angenommene Bedeutung (das oberste Stapelelement) zuordnen kann. Programmiersprachen, die auf eine virtuelle Maschine aufsetzen (zum Beispiel Java, P-Code-Pascal), optimieren den kompilierten Zwischencode für die Verwendung eines Stapels, um zur Laufzeit die Interpretation dieses Zwischencodes zu beschleunigen.

Verarbeitung von Klammerstrukturen

Stapelspeicher eignen sich auch zur Auswertung von Klammerausdrücken, wie sie etwa in der Mathematik geläufig sind. Dabei wird zunächst für Operatoren und Operanden je ein Stapelspeicher initialisiert. Der zu verarbeitende Klammerausdruck wird nun symbolweise eingelesen. Wird eine öffnende Klammer eingelesen, so ist diese zu ignorieren. Wird ein Operand oder Operator eingelesen, so ist dieser auf den jeweiligen Stapelspeicher zu legen. Wird eine schließende Klammer eingelesen, so wird der oberste Operator vom Stapelspeicher für die Operatoren genommen und entsprechend diesem Operator eine geeignete Anzahl von Operanden, die zur Durchführung der Operation benötigt werden. Das Ergebnis wird dann wieder auf dem Stapelspeicher für Operanden abgelegt. Sobald der Stapelspeicher für die Operatoren leer ist, befindet sich im Stapelspeicher für die Operanden das Ergebnis.

Postfixnotation

Zur Berechnung von Termen wird gelegentlich die Postfixnotation verwendet, die mit Hilfe der Operationen eine Klammersetzung und Prioritätsregeln für die Operationen überflüssig macht. Zahlwerte werden automatisch auf dem Stapel abgelegt. Binäre Operatoren (zum Beispiel +, −, *, /) holen die oberen beiden Werte, unäre Operatoren (zum Beispiel Vorzeichenwechsel) einen Wert vom Stapel und legen anschließend das (Zwischen-)Ergebnis dort wieder ab.

Infixnotation

Bei der maschinengestützten Auflösung von arithmetischen Ausdrücken in der so genannten Infixnotation (der Operator steht zwischen den beteiligten Zahlwerten) werden zunächst vorrangige Teilterme in einem Stapel zwischengelagert und so faktisch der Infix-Term schrittweise in einen Postfix-Term umgewandelt, bevor das Ergebnis durch Abarbeiten des Stapels errechnet wird.

Stapelorientierte Sprachen

Stapelorientierte Sprachen (z. B. Forth oder Postscript) wickeln fast alle Variablen-Operationen über einen Stapel ab und stellen neben den oben genannten Operatoren noch weitere zur Verfügung. Beispielsweise tauscht der Forth-Operator swap die obersten beiden Elemente des Stapels. Arithmetische Operationen werden in der Postfix-Notation aufgeschrieben und beeinflussen damit ebenfalls den Stapel.

Forth benutzte einen zweiten Stapel (Return-Stapel) zur Zwischenspeicherung der Rücksprungadressen von Unterprogrammen während der Ausführungsphase. Dieser Stapel wird auch während der Übersetzungsphase für die Adressen der Sprungziele für die Kontrollstrukturen verwendet. Die Übergabe und Rückgabe von Werten an Unterprogrammen geschieht über den ersten Stapel, der zweite nimmt die Rücksprungadresse auf.

Verwandte Themen

Eine First In – First Out-Datenstruktur nennt sich Warteschlange. Beide Strukturen haben dieselbe Signatur (d. h. Methoden-Struktur), aber unterschiedliches Verhalten, weswegen sie oft zusammen unterrichtet werden.

Eine andere Art Speicher zu verwalten ist die dynamische Speicherverwaltung, die zur Laufzeit entstehende Speicheranforderungen bedienen kann. Dieser Speicher wird oft als Heap oder Halde bezeichnet und wird eingesetzt wenn sehr große Mengen an Speicher benötigt werden.

Siehe auch

• Floodfill
• Deque
• Stacktrace

Literatur

Deutsches Patentamt, Auslegeschrift DE1094019. Verfahren zur automatischen Verarbeitung von kodierten Daten und Rechenmaschine zur Ausübung des Verfahrens. (Anmeldetag: 30. März 1957. Bekanntmachung der Anmeldung und Ausgabe der Auslegeschrift: 1. Dezember 1960. Dr. Friedrich Ludwig Bauer und Dr. Klaus Samelson, München, sind als Erfinder genannt worden. Erteilt 12. August 1971, DE-PS 1094019.)

1. ↑ Bauer/Goos: Informatik, Eine einführende Übersicht, Erster Teil. Springer-Verlag, Berlin 1982, S. 222. „Die Bezeichnung ‚Keller‘ hierfür wurde von Bauer und Samuelson in einer deutschen Patentanmeldung vom 30. März 1957 eingeführt.“

Weblinks

• Ehrung von Friedrich Ludwig Bauer