Ein Kellerspeicher, oft auch Stack, Stapel oder Stapelspeicher genannt, ist eine häufig (aber meist unbewusst) benutzte Datenstruktur in Computerprogrammen. Sie wird von den meisten Mikroprozessoren in der Hardware direkt unterstützt.
Funktionsprinzip
Ein Kellerspeicher 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 Kellerspeicher, pop holt ein Element vom Kellerspeicher (und entfernt dieses).
Dabei wird nach dem LIFO-Prinzip (last in first out) gearbeitet, d.h. es wird immer das Element zurückgegben, welches als letztes auf dem Kellerspeicher mit push abgelegt wurde.
Illustration
Man kann sich einen Kellerspeicher 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).
Anwendungen
Kellerspeicher werden in 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 Kellerspeicher programmieren.
Zur Übersetzung des Quellcodes einer Formalen Sprache nutzen Compiler und Interpreter einen Parser, der bei der Textanalyse Syntax-Regeln auf einem Kellerspeicher 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 Kellerspeichers, um zur Laufzeit die Interpretation dieses Zwischencodes zu beschleunigen.
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 Kellerspeicher 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 Kellerspeicher vorliegen), spricht man auch von einer Postfix-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 Kellerspeicher zwischengelagert und so faktisch der Infix-Term schrittweise in einen UPN-Term umgewandelt, bevor das Ergebnis durch Abarbeiten des Kellerspeichers errechnet wird. Die Umformung erfolgt auch hier wieder durch einen Parser.
Stapelorientierte Programmiersprachen (z.B. Forth) 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 Elelemente des Kellerspeichers. Arithmetische Operationen werden in der UPN notiert und beeinflussen damit ebenfalls den Kellerspeicher.
In der IA32-Architektur gibt es ein Register ESP, den Stackpointer. Dieses Register einthält eine Speicheradresse, die auf den gerade aktuellen Kellerspeichereintrag zeigt. Wenn mit der Operation Push ein weiterer Registerwert auf dem Kellerspeicher abgelegt wird, dann erniedright sich der Wert des Registers ESP. Der Kellerspeicher wächst also von grössern Hauptspeicheradressen in Richtung kleinere Hauptspeicheradressen. Indem man eine bestimmte Adressierungsart wählt kann man auch auf andere statt nur das aktuelle Kellerspeicherelement zugreifen.