Stack
Table of contents |
2 Funktionsprinzip 3 Illustration 4 Anwendungen |
Einleitung
Ein Stack, zu deutsch Stapel, manchmal auch Stapelspeicher oder Kellerspeicher genannt, ist eine häufig (aber meist unbewusst) benutzte Datenstruktur in Computerprogrammen. Sie wird von den meisten Mikroprozessoren in der Hardware direkt unterstützt.
Dabei wird nach dem LIFO-Prinzip (last in first out) gearbeitet, d.h. es wird immer das Element zurückgegeben, welches als letztes auf dem Stack mit push abgelegt wurde.
Die Theoretische Informatik unterscheidet hierbei zwischen einem echten Kellerspeicher, bei dem kein Element außer dem Obersten gelesen werden kann, und einem Stapel, 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 i. A. synonym verwendet.
Man kann sich einen Stack 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).
Siehe auch: Kellerautomat
Forth benutzt einen zweiten Stack (Return-Stapel) zur Zwischenspeicherung der Rücksprungadressen von Routinen 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 Routinen geschieht über den ersten Stapel, der zweite nimmt die Rücksprungadresse auf.
Funktionsprinzip
Ein Stack kann eine beliebige Menge von Elementen aufnehmen. Es gibt im Wesentlichen zwei Operationen, meist mit push und pop bezeichnet. Push legt ein Element auf den Stack, pop holt ein Element vom Stack (und entfernt dieses).Illustration
Anwendungen
Funktionale Programmiersprachen
Stacks 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 umwandeln, so muss man oft doch explizit einen Stack programmieren.Mikroprozessoren
In Mikroprozessoren gibt es dazu oft ein spezielles Register, den Stackpointer. Dieses Register enthält eine Speicheradresse, die auf den gerade obersten Stackeintrag zeigt. Wenn mit der Operation push ein weiterer Wert auf dem Stack abgelegt wird, dann erhöht oder vermindert sich der Wert des Stackpointers (je nach Prozesor) und zeigt so auf die nächste Adresse in die der neue Stackeintrag geschrieben wird. Bei pop wird der Eintrag der Adresse gelesen und anschließend der Stackpointer vermindert oder erhöht (wieder je nach Prozessor, aber diesmal genau umgekehrt), und zeigt so wieder auf den letzten Stackeintrag. Der Stack des Mikroprozessors wird oft von diesem selbst bei Aufruf und Rücksprung von Subroutinen 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 bzw. Rücksprung von der Subroutine Parameter an diese übergeben oder Funktionswerte von dieser zurückgeben.Compiler
Zur Übersetzung des Quellcodes einer Formalen Sprache nutzen Compiler und Interpreter einen Parser, der bei der Textanalyse Syntax-Regeln auf einem Stack 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, P-Code-Pascal) optimieren entsprechend den kompilierten Zwischencode für die Verwendung eines Stack, um zur Laufzeit die Interpretation dieses Zwischencodes zu beschleunigen.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 unitären Operatoren, z.B. Vorzeichenwechel, natürlich nur einen) vom Stack 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 Stack 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 Stack zwischengelagert und so faktisch der Infix-Term schrittweise in einen UPN-Term umgewandelt, bevor das Ergebnis durch Abarbeiten des Stack 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 eine Stapel-Struktur ab und stellen neben den oben genannten Operatoren noch weitere zur Verfügung. Beispielsweise tauscht der Forth-Operator swap die obersten beiden Elemente des Stack. Arithmetische Operationen werden in der UPN notiert und beeinflussen damit ebenfalls den Stack.Programmiersprachen mit rekursiv aufrufbaren Unterprogrammen
Viele Programmiersprachen wie C und Java erlauben rekursive Unterprogramme. Hier wird ein Stack zur Zwischenspeicherung der Rücksprungadressen, lokalen Variablen und Funktionsergebnisse verwendet. Dieser Stack wird in den meisten dieser Sprachen stets benutzt, auch für nicht rekursive Unterprogramme.