In der Informatik bezeichnet ein Stapelspeicher (kurz Stapel, häufig auch mit dem englischen Wort Stack bezeichnet) eine häufig (aber meist unbewusst) eingesetzte, spezielle 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, zum Hinzufügen eines Objektes und
- pop, zum Zurückholen und Entfernen eines Objektes
bereit.
Dabei wird nach dem Last In - First Out-Prinzip (deutsch zuletzt hinein - zuerst heraus, kurz LIFO) gearbeitet, d.h. es wird von pop immer das Objekt aus dem Stapel zurückgegeben, welches als letztes mit push hineingelegt wurde.
Die Theoretische Informatik unterscheidet hierbei 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 Allgmeinen synonym verwendet.
Illustration
Man kann sich einen Stapel 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 ausschliesslich den Zugriff auf das oberste Element des Stapelspeichers. Ein Entfernen eines weiter unten liegenden Elementes im Stabelspeicher ist nicht möglich. Das Lesen und Schreiben auf weiter unten liegende Elemente ist nur durch direktes Lesen und Beschreiben der Speicheraddresse dieses Elementes möglich.
Anwendungen
Funktionale Programmiersprachen
Stapel werden in funktionalen Programmiersprachen meist nur implizit benutzt, ohne dass sich der Programmierer Gedanken darum machen muss, beispielsweise bei rekursiven Funktionen. Will man eine rekursive Funktion in eine iterative Funktion umwandeln, so muss man oft doch explizit einen Stapel programmieren.
Mikroprozessoren
In Mikroprozessoren gibt es dazu oft ein spezielles Register, den Stapelzeiger. 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. 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. Compiler für moderne funktionale 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.
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 Prozedurinkarnation 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.
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 entsprechend 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:
Für Operatoren und Operanden wird je ein Stack initialisiert. Der zu verarbeitende Klammerausdruck wird symbolweise eingelesen. Wird eine öffnende Klammer eingelesen, so ist diese zu ignorieren. Wir dine Operand oder Operator eingelesen, so ist dieser auf den jeweiligen Stack legen. Wird eine schließende Klammer eingelesen, so sind folgende Schritte auszuführen: - Den Obersten Operator von Operatorstack nehmen. - So viele Operanden wie nötig vom Operandenstack nehmen. - Ergebnis auswerten und auf Operandenstack legen. 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 Unterprogreammen geschieht über den ersten Stapel, der zweite nimmt die Rücksprungadresse auf.
Siehe auch: Warteschlange, First In - First Out, Kellerautomat