Stapelspeicher

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 begrenzte Menge von Objekten aufnehmen. Elemente können nur oben auf den Stapel gelegt und auch nur von dort wieder gelesen werden. Elemente werden übereinander gestapelt und in umgekehrter Reihenfolge vom Stapel genommen. Dies wird auch Last-In-First-Out-Prinzip (LIFO) genannt.

Dazu werden folgende Operationen zur Verfügung gestellt:

• push (auch einkellern) legt das Objekt oben auf den Stapel.
• pop (auskellern) liefert das oberste Objekt und entfernt es vom Stapel. Bei manchen Prozessoren wie dem MOS Technology 6502 wird diese Aktion dagegen pull (herunterziehen) genannt.
• peek (nachsehen) liefert das oberste Objekt, ohne es zu entfernen.

In der Automatentheorie 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 Implementierung 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 in manchen Implementierungen Befehle, um die 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 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. Bauer erhielt den renommierten Computer Pioneer Award (IEEE) für Computer Stacks. Samelson war bereits 1980 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 oft ein spezielles Register, den Stackpointer (Stapelzeiger). Dieses Register enthält eine Speicheradresse, die auf den aktuellen Stapeleintrag (des aktuellen Prozesses) zeigt. Viele Befehle/Operationen des Mikroprozessors nutzen diesen Stapeleintrag. Unter anderem gibt es Befehle, mit denen man in den Stack schreiben (z. B. push beim x86-Prozessor) oder von ihm lesen kann (z. B. pop). Dabei wird automatisch der Stapelzeiger verringert oder erhöht.

Die Operation Jump To Subroutine (Sprung in ein Unterprogramm) legt auf dem Stack die Rücksprungadresse ab, die später von der Operation Return From Subroutine verwendet wird. Unterprogrammen bzw. Funktionen, wie man sie aus Programmiersprachen wie C kennt, werden die Parameter über den Stack übergeben, der auch die Rückgabewerte aufnimmt. Außerdem werden lokale Variablen auf dem Stack gespeichert. Dies erlaubt unter anderem Rekursion, das Aufrufen einer Funktion aus ebendieser Funktion heraus. – Wird bei der Rückkehr aus einer Funktion nur ein Eintrag zu viel oder zu wenig ausgelesen, führt dies zu besonders gravierenden Programmfehlern, da der Prozessor dann versuchen wird, Code an völlig zufälliger Speicherposition auszuführen. Durch das Ausnutzen einer nicht korrekt behandelten Größenangabe der Daten können Angreifer versuchen, einen Pufferüberlauf zu produzieren, der den Stack so verändert, dass durch Umleiten des Rücksprungs bösartiger Code ausgeführt wird.

Bei den meisten Prozessoren beginnt der Stapel bei einer hohen Adresse und wird in Richtung der Adresse 0 gestapelt. Das bedeutet, dass bei push der Stapelzeiger vermindert und etwas in den Stack geschrieben wird und bei pop vom Stack gelesen und der Stapelzeiger 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 unterhalb des Speicherplatzes, der von den Programmen benutzt wird, können so andere Programmdaten (die normal hinter dem Programm abgelegt werden) den Stapel nicht so leicht überschreiben und der Stapel nicht das Maschinenprogramm.

In Multitasking-Systemen gibt es für jeden Prozess und innerhalb der Prozesse für jeden Thread einen eigenen Stapelspeicher. Beim Umschalten zwischen Prozessen bzw. Threads wird neben anderen Registern auch der jeweilige Stapelzeiger gespeichert und geladen.

Um Fehler in der Benutzung des Stacks durch einen „Unterlauf“ des Stapelzeigers aufzudecken, legen manche Betriebssysteme wie beispielsweise DOS oder CP/M (Bei COM-Programmen) oder OSEK-OS als untersten Wert im Stapel die Sprungadresse einer Abbruch- oder Fehlerbehandlungsroutine ab. Holt der Prozessor durch einen Fehler in der Aufrufverschachtelung diese Adresse vom Stapel, kann ggf. noch auf den Ablauffehler reagiert werden. Manche Betriebssysteme können auch den Stapelspeicher während der Laufzeit vergrößern, was bei einem bereits sehr großen Stapel relativ viel Zeit in Anspruch nehmen kann. Bei anderen Betriebssystemen hat der Programmierer selbst anzugeben, wie groß der Stack sein soll.

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. 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.

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.

Stack-Implementierung

In C++:

#include <stdexcept>


template <typename T>
class stack
{
   public:
      // erzeugt einen leeren Stack
      stack(): size_(0) {}

      // erzeugt einen Stack mit n Elementen von T
      stack(size_t n, T value_): size_(0)
      {
         for (int i = 0; i < n; ++i)
            push(value_);
      }

      // Kopierkonstruktor
      stack(const stack &rhs): size_(0)
      {
         // Wenn der "rechte" Stack keine Elemente aufweist, muss nichts weiter getan werden.
         if (rhs.size_ != 0) {
            node *traverser = rhs.top;
            size_t size_ = rhs.size();
            //Absteigen zum ersten Element, dann zum zweiten Element, usw.
            for (; size_ > 0; --size_ ) {
               for (unsigned i=1; i < size_; ++i)
                  traverser = traverser->previous;
               push(traverser->value);
               traverser = rhs.top;
            }
         }
      }

      ~stack()
      {
         for (; size_ != 0; pop());
      }


      // Zuweisungsoperator
      stack& operator=(const stack &rhs)
      {
         // überprüfe ob ein Stack sich selbst zugewiesen wird.
         if (&rhs != &*this)
         {
            for (; size_ != 0; pop());

            // vgl. Kopierkonstruktor
            if (rhs.size_ != 0) {
               node *traverser = rhs.top;
               size_t size_ = rhs.size();
               for (; size_ > 0; --size_ ) {
                  for (unsigned i=1; i < size_; ++i)
                     traverser = traverser->previous;
                  push(traverser->value);
                  traverser = rhs.top;
               }
            }

         }
         return *this;
      }


      void push(T value_)
      {
         node *newNode;
         // .previous des untersten Stackelementes muss 0 sein, damit das Ende des Stacks
         // ermittelt werden kann.
         if (size_ == 0)
            newNode = new node(value_, 0);
         else
            newNode = new node(value_, top);
         top = newNode;
         ++size_;
      }

      T pop()
      {
         if (size_ == 0)
            throw std::underflow_error("Nothing to pop.");
         // Rückgabewert sichern
         T returnValue = top->value;
         node *newTop = top->previous;
         delete top;
         top = newTop;
         --size_;
         return returnValue;
      }

      T peek() const { return top->value; }
      size_t size() const { return size_; }


   private:
      struct node
      {
            T value;
            node *previous;

            node(T value_, node *previous_): value(value_), previous(previous_) {}
      };
      node *top;

      std::size_t size_;   //ab C++11 nicht mehr im std-Namensraum
};

In Java:

// Ein Stapel dynamischer Größe, der alle
// Elemente der Klasse Object sowie deren
// Unterklassen verwalten kann.
public class Stack {
	private Item start = null;
	public void push(Object object) { // Speichert ein neues Objekt
		start = new Item(object,start);
	}
	public Object top() { // Gibt das oberste Objekt wieder
		return !(empty()) ? start.getObject() : null;
	}
	public boolean empty() { // Prüft, ob der Stapel leer ist
		return start == null;
	}
	public void pop() { // Entfernt das oberste Objekt aus dem Stapel
		if(!empty()) start = start.getNext();
	}
}

public class Item {
	private Object object; // Das zu verwaltende Objekt
	private Item next; // Referenz auf den nächsten Knoten
	public Item(Object object, Item next) {
		this.object = object;
		this.next = next;
	}
	public Object getObject() { // Gibt das gespeicherte Objekt aus
		return object;
	}
	public Item getNext() { // Gibt den nächsten Knoten aus
		return next;
	}
}

In vielen Programmiersprachen sind Stacks bereits in der Standardbibliothek implementiert. So stellt Java diese Funktionalität in der Klasse java.util.LinkedList zur Verfügung. In der C++ Standard Template Library bietet das Template stack<T> entsprechende Funktionalität, welche normalerweise jedoch anders als hier nicht mit einer verketteten Listen implementiert ist.

Compiler

Zur Übersetzung des Quellcodes einer formalen Sprache nutzen Compiler und Interpreter einen Parser, der einen Stapel verwendet. Der Parser kann z. B. wie ein Kellerautomat arbeiten.

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 benutzt 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 (engl. Queue). 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 bezeichnet und wird eingesetzt, wenn die Lebensdauer der zu speichernden Objekte unterschiedlich ist und nicht dem eingeschränkten Prinzip des Stapelspeichers oder der Warteschlange entspricht.

Siehe auch

• Floodfill
• Deque
• Stacktrace

Literatur

• Patent DE1094019: Verfahren zur automatischen Verarbeitung von kodierten Daten und Rechenmaschine zur Ausübung des Verfahrens. Angemeldet am 30. März 1957, veröffentlicht am 1. Dezember 1960, Erfinder: Friedrich Ludwig Bauer, Klaus Samelson (Erteilt 12. August 1971).‌

Weblinks

Commons: Stack-Datenstruktur – Sammlung von Bildern, Videos und Audiodateien