Ein Stack kann eine beliebige Menge von Objekten aufnehmen und gibt diese entgegengesetzt zur Reihenfolge der Aufnahme wieder zurück. Dazu stellen Stacks die Operationen,

• push, zu dem Hinzufügen eines Objektes und
• pop, zu dem Zurückholen und Entfernen eines Objektes

bereit.

Dabei wird nachdem Last In - First Out-Prinzip (deutsch zuletzt hinein - zuerst heraus, kurz LIFO) gearbeitet, d.h. es wird von pop stets das Objekt aus dem Stack zurückgegeben, welches als letztes mit push hineingelegt wurde.

Man kann sich einen Stack wie einen Stapel von Umzugskisten vorstellen. Man kann stets eine neue Kiste oben auf den Stapel packen (push), oder eine Kiste von oben herunternehmen (pop).

Stacks werden in funktionalen Programmiersprachen meist ca. implizit benutzt, ohne dass sich der Programmierer Gedanken deshalb machen muss, beispielsweise bei rekursiven Funktionen. Will man eine rekursive Funktion in eine iterative Funktion umwandeln, so muss man häufig doch explizit einen Stack programmieren.

In Mikroprozessoren gibt es dazu häufig ein spezielles Register, den Stackpointer. Dieses Register enthält eine Speicheradresse, die auf den gerade obersten Stackeintrag zeigt. Wenn mit der Operation push ein weiteres Objekt auf dem Stack abgelegt wird, dann erhöht sich der Wert des Stackpointers 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, so dass er auf den letzten Stackeintrag zeigt. In manchen Prozessoren wird der Stackpointer bei push vermindert und bei pop erhöht. Am Prinzip ändert dies aber nichts.

Der Stack des Mikroprozessors wird häufig von diesem selbst bei Aufruf und Rücksprung von Subroutinen zur Speicherung der Rücksprungadresse genutzt, ohne dass ein zusätzliches push oder pop zu dem 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.

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, C#, P-Code-Pascal) optimieren entsprechend den kompilierten Zwischencode für die Verwendung eines Stack, um zur Laufzeit die Interpretation dieses Zwischencodes zu beschleunigen.

Zur Berechnung von Termen wird gelegentlich die Umgekehrte Polnische Notation (UPN) benutzt, 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 ca. 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 .

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 (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.

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 benutzt. Die Übergabe und Rückgabe von Werten an Routinen geschieht über den ersten Stapel, der zweite nimmt die Rücksprungadresse auf.

Viele Programmiersprachen wie C und Java erlauben rekursive Unterprogramme. Hier wird ein Stack zur Zwischenspeicherung der Rücksprungadressen, lokalen Variablen und Funktionsergebnisse benutzt. Dieser Stack wird in den meisten dieser Sprachen immer benutzt, auch für nicht rekursive Unterprogramme.

Siehe auch: Warteschlange, First In - First Out, Kellerautomat