Wikipedia · einfach zusammengefasst · Stand
Stapelspeicher
Abstrakter Datentyp. Bearbeiten. Bei der Implementierung eines Stapelspeichers als abstrakter Datentyp in einer einfach verketteten Liste wird der Zeiger auf …
Inhalt6 Abschnitte
Grundprinzip und Grundoperationen
Ein Stapelspeicher, auch Kellerspeicher, Stapel oder Stack, ist eine dynamische Datenstruktur der Informatik. Er kann theoretisch beliebig viele, praktisch aber nur begrenzt viele Objekte aufnehmen. Sein entscheidendes Prinzip heißt Last-In-First-Out (LIFO): Das zuletzt abgelegte Element wird als erstes wieder entnommen.
Zugriff besteht grundsätzlich nur auf die Oberseite des Stapels. push („einkellern“) legt ein Objekt oben ab. pop („auskellern“) liefert das oberste Objekt und entfernt es. peek, manchmal top genannt, liefert das oberste Objekt, ohne es zu entfernen. Beim MOS Technology 6502 heißt die entsprechende Entnahmeaktion pull. In manchen Implementierungen gibt es außerdem duplicate zum Duplizieren des obersten Elements, swap oder exchange zum Vertauschen der obersten zwei Elemente sowie rotate oder roll zum rotierenden Verschieben der n obersten Elemente.
In der Automatentheorie wird zwischen einem echten Kellerspeicher, bei dem nur das oberste Element lesbar ist, und einem Stapelspeicher unterschieden, bei dem alle Elemente betrachtet, aber nicht verändert werden können. In der Praxis ist diese Unterscheidung kaum wichtig; die Begriffe werden meist gleichbedeutend verwendet.
Speicheraufbau, Stapelzeiger und Fehler
Ein Stack liegt gewöhnlich in einem Block von Speicherzellen. Sein Boden beziehungsweise Ursprung befindet sich an einer festen Speicheradresse. Ein Stapelzeiger (Stackpointer) enthält die Adresse des aktuellen obersten Elements oder, je nach Implementierung, die Adresse der nächsten freien Position.
Beim push wird der Stapelzeiger abhängig von der Wachstumsrichtung um die Größe des Elements erhöht oder verringert und das neue Element in den Stapelbereich kopiert. Beim pop werden Daten vom Stapel kopiert und der Zeiger entsprechend zurückbewegt. Ein Stack kann zu höheren oder zu niedrigeren Speicheradressen wachsen. Häufig beginnt er bei einer hohen Adresse und wächst in Richtung Adresse 0: push vermindert dann den Stapelzeiger, pop erhöht ihn.
Der Stapelzeiger darf den Ursprung nicht überschreiten. Liegt der Ursprung beispielsweise bei Adresse 1000 und der Stapel wächst nach unten über 999, 998 usw., darf der Zeiger nicht auf 1001 oder höher gelangen. Geschieht das durch pop, entsteht ein Stapelunterlauf. Überschreitet push die maximal verfügbare Ausdehnung, entsteht ein Stapelüberlauf. Die Darstellung als von unten nach oben, links nach rechts oder oben nach unten wachsender Stapel ist nur eine Visualisierung; wichtig ist die feste Position seines Bodens.
Bedeutung in Mikroprozessoren und Programmen
Die meisten Mikroprozessoren unterstützen Stapelspeicher direkt durch Maschinenbefehle. Sie besitzen oft ein spezielles Register, den Stackpointer, der auf den aktuellen Stapeleintrag des aktuellen Prozesses zeigt. Befehle wie push und pop schreiben auf den Stack beziehungsweise lesen von ihm und passen den Stapelzeiger automatisch an.
Jump To Subroutine legt die Rücksprungadresse auf dem Stack ab; Return From Subroutine verwendet sie später. Funktionen und Unterprogramme können Parameter über den Stack erhalten, Rückgabewerte dort ablegen und Speicher für lokale Variablen reservieren. Dadurch ist Rekursion möglich, also der Aufruf einer Funktion aus sich selbst heraus. Liest eine Funktion bei der Rückkehr einen Eintrag zu viel oder zu wenig, kann der Prozessor Code an zufälligen Speicherpositionen auszuführen versuchen. Angreifer können durch eine nicht korrekt behandelte Größenangabe einen Pufferüberlauf ausnutzen und den Rücksprung so verändern, dass bösartiger Code ausgeführt wird.
In Multitasking-Systemen besitzt jeder Prozess und jeder Thread einen eigenen Stack. Beim Wechsel werden neben anderen Registern auch die jeweiligen Stapelzeiger gespeichert und geladen. Manche Betriebssysteme legen am unteren Stackende die Adresse einer Abbruch- oder Fehlerbehandlungsroutine ab, um auf einen Unterlauf reagieren zu können. Manche vergrößern den Stack während der Laufzeit, andere verlangen eine vorher festgelegte Größe. Die Wasserstands-Methode misst die Stacknutzung: Der reservierte Bereich wird mit einem festen Datenmuster gefüllt; nach der Laufzeit zeigen unveränderte Bereiche den ungenutzten Platz.
Abstrakter Datentyp und Implementierungen
Als abstrakter Datentyp kapselt ein Stack seine Datenknoten, den Zeiger top auf die Oberseite und einen Zähler count für die Elementzahl. In einer einfach verketteten Liste enthält jeder Knoten beispielsweise einen Datenzeiger dataPointer und einen Verweis link auf den nächsten Knoten. Das Programm verwaltet den Speicher für die Daten und übergibt deren Adresse an den Stack.
Stacks lassen sich unterschiedlich implementieren. Eine C-Implementierung kann ein Array fester Länge verwenden; im Artikel ist LEN auf 100 gesetzt. count bezeichnet dort die Zahl gespeicherter Elemente, push fügt an data[count] an, pop verringert count und liefert das bisher oberste Arrayelement. C++, Java und Python zeigen Varianten mit verketteten Listen beziehungsweise, in Python, einer dynamisch erweiterbaren Liste. Python verwendet append für push, pop der Liste für die Entnahme und den Index -1 für peek.
Viele Sprachen stellen Stacks bereits über ihre Standardbibliothek bereit: Java über java.util.LinkedList und die C++ Standard Template Library über das Template stack<T>. Die dortige C++-Bibliotheksimplementierung verwendet normalerweise nicht die im Artikel gezeigte einfach verkettete Liste.
Compiler, Klammern und Terme
Compiler und Interpreter verwenden vor einem Unterprogrammaufruf gewöhnlich push-Operationen, um Parameter zu übergeben. Da der Compiler die Parametertypen kennt, dürfen die Parameter unterschiedliche Größen haben. Auch Ergebnisse und lokale Variablen können über den Stack verwaltet werden. Bei der Umwandlung eines rekursiven Unterprogramms in ein iteratives muss dieser Mechanismus häufig ausdrücklich nachgebildet werden. Virtuelle Maschinen wie Java oder P-Code-Pascal optimieren ihren kompilierten Zwischencode für die Stackverwendung, damit dessen Interpretation zur Laufzeit schneller erfolgt.
Beim Übersetzen formaler Sprachen verwendet ein Parser einen Stack und kann beispielsweise wie ein Kellerautomat arbeiten. Stacks prüfen außerdem Verschachtelungen in Termen und Syntaxen, etwa bei BB-Codes und XML-Dokumenten.
Zur Auswertung eines Klammerausdrucks werden ein Operatoren- und ein Operandenstack angelegt. Öffnende Klammern werden ignoriert; Operatoren und Operanden werden jeweils abgelegt. Bei einer schließenden Klammer wird der oberste Operator entnommen, die dafür benötigte Anzahl oberster Operanden entnommen und das Ergebnis wieder auf den Operandenstack gelegt. Sobald der Operatorenstack leer ist, liegt das Ergebnis auf dem Operandenstack.
In der Postfixnotation sind Klammern und Prioritätsregeln nicht nötig. Zahlen werden auf den Stack gelegt; binäre Operatoren wie +, −, * und / entnehmen zwei Werte, unäre Operatoren wie der Vorzeichenwechsel einen Wert, und legen das Zwischenergebnis wieder ab. Bei der maschinellen Verarbeitung von Infixnotation, bei der der Operator zwischen Zahlwerten steht, werden vorrangige Teilterme zwischengespeichert und der Infix-Term schrittweise in einen Postfix-Term umgewandelt.
Typische Anwendungen und verwandte Konzepte
Ein anschauliches Beispiel ist ein Stapel von Umzugskisten oder Spielkarten: Es kann nur oben eine Kiste oder Karte abgelegt oder entnommen werden. Im C++-Kartenbeispiel werden nacheinander „Kreuz Bube“, „Herz Dame“ und „Karo König“ abgelegt. Nach pop ist „Herz Dame“ oben; nach push von „Karo Ass“ ist dieses oberste Element. Kartenspiele wie Texas Hold’em, Omaha Hold’em, Canasta und Die Siedler von Catan können sinnvoll mit Stacks programmiert werden.
Stapelorientierte Sprachen wie Forth und PostScript führen fast alle Variablenoperationen über einen oder mehrere Stacks aus und schreiben arithmetische Operationen in Postfixnotation. Forth verwendet zusätzlich einen Return-Stapel für Rücksprungadressen und während der Übersetzung für Sprungziele von Kontrollstrukturen; in den meisten Implementierungen gibt es außerdem einen Stack für Gleitkommaoperationen. Bei einer Stack-Architektur beziehen sich Datenoperationen implizit auf einen Stack, also ohne getrennte push- und pop-Befehle. Beispiele sind Intel-Gleitkommaprozessoren und technisch-wissenschaftliche Taschenrechner der HP-41-, Voyager- und HP-48-Serie.
Eine Warteschlange (Queue) arbeitet dagegen nach First-In-First-Out: Das zuerst eingefügte Element wird zuerst entnommen. Stack und Queue haben dieselbe Methodensignatur, aber unterschiedliches Verhalten. Der Heap ist ein anderer Speicherbereich für zur Laufzeit entstehende Speicheranforderungen, wenn die Lebensdauer von Objekten nicht dem eingeschränkten Prinzip von Stack oder Warteschlange entspricht.
