Kellerspeicher

Ein Kellerspeicher, oft auch Stack oder Stapel genannt, ist eine häufig (aber meist unbewußt) benutzte Datenstruktur in Computerprogrammen. Sie wird von den meisten Mikroprozessoren in der Hardware direkt unterstützt.

Ein Kellerspeicher kann eine beliebige Menge von Objekten aufnehmen. Es gibt im wesentlichen zwei Operationen, meist mit push und pop bezeichnet. Push legt ein Objekt auf den Kellerspeicher, pop holt ein Objekt vom Kellerspeicher. Dabei wird nach dem LIFO-Prinzip (last in first out) gearbeitet, d.h. es wird immer das Objekt zurückgegben, welches als letztes auf dem Kellerspeicher mit push abgelegt wurde.

Man kann sich einen Kellerspeicher wie einen Stapel Bierkisten vorstellen. Man kann immer eine Kiste oben auf den Stapel packen (push), oder eine Kiste von oben herunternehmen (pop).

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.

Die Programmiersprache Forth wickelt fast alle Variablen-Operationen über eine Stapel-Struktur ab und stellt neben den oben genannten Operatoren noch weitere zur Verfügung. Beispielsweise tauscht der Operator swap die obersten beiden Stapelelemente.

Zur Berechnung von Termen wird die Umgekehrt Polnische Notation, die mithilfe der Stapeloperationen eine Klammersetzung (und damit auch Punkt-vor-Strich-Regeln) überflüssig macht.