Stapelspeicher

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 beliebige Menge von Objekten aufnehmen und gibt diese entgegengesetzt zur Reihenfolge der Aufnahme wieder zurück. Dazu stellen Stapel die Operationen

• push (einkellern) zum Hinzufügen eines Objektes und
• pop (auskellern) zum Zurückholen und Entfernen eines Objektes

bereit. Als erweiterte Funktion wird meist peek für das Ansehen ohne Entfernen eines Objektes angeboten.

Dabei wird nach dem Last In - First Out-Prinzip (deutsch zuletzt hinein - zuerst heraus, kurz LIFO) gearbeitet, das heißt es wird von pop immer das Objekt aus dem Stapel zurückgegeben, welches als letztes mit push hineingelegt wurde.

In der theoretischen Informatik werden Kellerspeicher 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 ohne Veränderung der Daten jedes Element betrachtet werden kann (vergleichbar einem Lesezugriff auf einen Array). Diese Unterscheidung spielt jedoch in der Praxis keine Rolle, beinahe jede Implementation ist ein Stapel, daher werden die Begriffe im Allgemeinen synonym verwendet.

Illustration

Man kann sich einen Stapelspeicher wie einen Stapel von Umzugskisten vorstellen. Man kann immer eine neue Kiste oben auf den Stapel packen (push) oder eine Kiste von oben herunternehmen (pop). Die Befehle push und pop erlauben ausschließlich den Zugriff auf das oberste Element des Stapelspeichers. Ein Entfernen eines weiter unten liegenden Elementes im Stapelspeicher ist nicht möglich. Das Lesen und Schreiben auf weiter unten liegende Elemente ist nur durch direktes Lesen und Beschreiben der Speicheradresse dieses Elementes möglich.

Geschichte

Die Verwendung eines Stapelspeichers zur Übersetzung von Programmiersprachen wurde 1957 von Friedrich Ludwig Bauer und Klaus Samelson unter dem Namen "Kellerprinzip" patentiert (Deutsches Patentamt, Auslegeschrift 1094019, B441221X/42m. 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.8.1971, DE-PS 1094019).

Die lange ausgebliebene internationale Anerkennung und Ehrung ihrer Leistung erfolgte erst im Jahre 1988: Friedrich Ludwig Bauer erhielt (als einziger Überlebender) den legendären Computer Pioneer Award (IEEE) for Computer Stacks.

Anwendungen

Mikroprozessoren

In Mikroprozessoren gibt es dazu oft ein spezielles Register, den Stapelzeiger (stack pointer, SP). Dieses Register enthält eine Speicheradresse, die auf den gerade obersten Stapeleintrag zeigt. Wenn mit der Operation push ein weiteres Objekt auf dem Stapel abgelegt wird, dann erhöht sich der Wert des Stapelzeigers und zeigt so auf die nächste Adresse, in die der neue Stapeleintrag geschrieben wird. Bei pop wird der Eintrag der Adresse gelesen und anschließend der Stapelzeiger vermindert, so dass er auf den letzten Stapeleintrag zeigt. Dieses Register kann i.A. auch direkt gesetzt werden. In manchen Prozessoren wird der Stapelzeiger bei push vermindert und bei pop erhöht. Am Prinzip ändert dies aber nichts.

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. Compiler für moderne Programmiersprachen erweitern diesen Mechanismus oft, indem sie mit zusätzlichen push- und pop-Operationen vor dem Aufruf des Unterprogramms an dieses Parameter übergeben. Ähnlich können so auch Ergebnisse des Unterprogramms zurückgegeben werden. Da der Stapel im normalen Arbeitsspeicher des Computers liegt, kann er vom Mikroprozessor auch wie normaler Speicher benutzt werden. Lokale Variablen, z.B. von Unterprogrammen, werden daher ebenfalls auf dem Stapel gespeichert.

In Multitasking-Systemen gibt es für jedes Programm einen eigenen Stapel. Beim Umschalten zwischen Prozessen wird dieser durch direktes Setzen von SP initialisiert.

Rekursive Programmierung

In diesem Zusammenhang ist auch die Realisierung von rekursiven Prozeduraufrufen mittels Stacks interessant. Dabei geht im Prinzip folgendes vor sich:

1. Für jede Prozedurinstanz müssen Rücksprungadresse, Parameter und lokale Variablen gemerkt werden.
2. Dies tut man in sogenannten Aktivierungsrecords, die auf dem Stack abgelegt werden.
3. Wenn die Prozedur beendet wird, so wird ihr Aktivierungsrecord wieder vom Stack entfernt.

Durch die oben beschriebene Stack-Unterstützung von Microprozessoren wird also zugleich eine effiziente Unterstützung für rekursive Programmierung bereitgestellt.

Ein anderer Anwendungsbereich im Zusammenhang mit Rekursion ergibt sich, wenn man eine rekursive Funktion in eine iterative Funktion umwandeln will. Auch hierbei kommt häufig ein Stack zum Einsatz.

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 (z. B. Java, C#, 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 mittels Stacks

Stacks eignen sich hervorragend zur Auswertung von Klammerausdrücken, wie sie etwa in der Mathematik geläufig sind. Die folgenden Schritte geben eine grobe Richtschnur an, wie solche Strukturen mit Hilfe zweier Stacks verarbeitet werden können:

1. Für Operatoren und Operanden wird je ein Stack initialisiert.
2. Der zu verarbeitende Klammerausdruck wird symbolweise eingelesen.
3. Wird eine öffnende Klammer eingelesen, so ist diese zu ignorieren.
4. Wird ein Operand oder Operator eingelesen, so ist dieser auf den jeweiligen Stack zu legen.
5. Wird eine schließende Klammer eingelesen, so sind folgende Schritte auszuführen:
   1. Den Obersten Operator von Operatorstack nehmen.
   2. So viele Operanden wie nötig vom Operandenstack nehmen.
   3. Ergebnis auswerten und auf Operandenstack legen.
6. Schließlich ist der Operatorstack leer und im Operandenstack liegt das Ergebnis.

Umgekehrte Polnische Notation

Zur Berechnung von Termen wird gelegentlich die Umgekehrte Polnische Notation (UPN) verwendet, die mit Hilfe der Operationen eine Klammersetzung und Punkt-vor-Strich-Regeln überflüssig macht. Die Operationen werden auch hier nicht explizit angegeben, sondern ergeben sich aus den Rechenvorschriften der UPN. Zahlwerte werden automatisch auf dem Stapel abgelegt, Operatoren (+, -, *, /) holen die oberen beiden Werte (bei unären Operatoren, zum Beispiel Vorzeichenwechel, natürlich nur einen) vom Stapel und legen anschließend das (Zwischen-)Ergebnis dort wieder ab. Da hier der Operator als letztes angegeben wird (die Werte müssen zur Durchführung der Operation bereits auf dem Stapel vorliegen), spricht man auch von einer Postfix-Notation.

Infix-Notation

Bei der maschinengestützten Auflösung von arithmetischen Ausdrücken in der so genannten Infix-Notation (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 UPN-Term umgewandelt, bevor das Ergebnis durch Abarbeiten des Stapels errechnet wird. Die Umformung erfolgt auch hier wieder durch einen Parser.

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

Siehe auch

• Warteschlange
• Pufferüberlauf