Stack (Stapel)
Zuletzt aktualisiert
Ein Stack ist eine Sammlung mit genau einem offenen Ende. Du legst einen Wert oben drauf (push) und nimmst ihn oben wieder herunter (pop), sodass der zuletzt abgelegte Wert immer als erster wieder herauskommt. Genau das bedeutet LIFO, last in, first out, und das ist die ganze Regel: An die Mitte kommst du nicht heran, ohne vorher alles zu entfernen, was darüber liegt. Drücke oben auf Abspielen und sieh zu, wie die Säule mit jedem push wächst und mit jedem pop am selben Ende wieder schrumpft.
Die Einschränkung ist der Punkt. Weil beide Operationen nur das obere Ende berühren, kostet jede von ihnen O(1), egal wie hoch der Stack wird, und diese Vorhersagbarkeit ist der Grund, warum Stacks unter so vielem in der Informatik stecken: der Aufrufstapel (Call Stack), auf dem Rekursion läuft, die Undo-Historie in einem Editor, die Klammernprüfung in einem Parser und der explizite Stack, der eine rekursive Tiefensuche in eine Schleife verwandelt. Vertausche das Ende, an dem entfernt wird, und du hast stattdessen eine Queue.
Zeit- und Speicherkomplexität
Für den üblichen Stack auf Basis eines Arrays oder einer verketteten Liste:
| Operation | Komplexität | Hinweise |
|---|---|---|
| Push (ablegen) | O(1) | Auf einem dynamischen Array amortisiert O(1), weil es gelegentlich seine Größe ändert. |
| Pop (entnehmen) | O(1) | Immer das oberste Element, es muss also nichts verschoben werden. |
| Peek (oben ansehen) | O(1) | Den obersten Wert lesen, ohne ihn zu entfernen. |
| Suchen | O(n) | Dafür ist ein Stack nicht gedacht: Du musst dich Wert für Wert nach unten arbeiten. |
| Speicher | O(n) | Ein Platz pro gespeichertem Wert. |
Schritt für Schritt
| Schritt | Was passiert |
|---|---|
| 1 | Der Stack startet leer, das obere Ende zeigt auf nichts. |
| 2 | Push schreibt den Wert an die oberste Position und schiebt das obere Ende um eins nach oben. |
| 3 | Jedes weitere Push landet direkt über dem vorherigen Wert. |
| 4 | Pop liest den Wert am oberen Ende und schiebt das obere Ende danach um eins nach unten. |
| 5 | Zurück kommt immer der Wert, der zuletzt abgelegt wurde. |
| 6 | Ein Pop auf einem leeren Stack ist ein Fehler, ein Stack Underflow, deshalb prüft echter Code vorher is_empty(). |
Durchgerechnetes Beispiel
3, 7 und 5 ablegen und den Stack danach leeren:
| Operation | Stack (unten nach oben) | Gibt zurück |
|---|---|---|
push(3) | [3] | nichts |
push(7) | [3, 7] | nichts |
push(5) | [3, 7, 5] | nichts |
pop() | [3, 7] | 5, der neueste Wert |
pop() | [3] | 7 |
pop() | [] | 3, der älteste Wert, zuletzt |
Wann man einen Stack verwendet
| Verwenden, wenn | Vermeiden, wenn |
|---|---|
| Du das zuletzt hinzugefügte Element zuerst zurückbrauchst: Undo, Zurück-Buttons, Klammernprüfung | Du das älteste Element zuerst brauchst, dafür ist eine Queue da |
| Du einen rekursiven Algorithmus in einen iterativen umschreibst | Du in der Mitte der Daten suchen oder indizieren musst |
| Du verschachtelte Strukturen parst, etwa Ausdrücke, JSON oder HTML | Viele Leser beliebigen Zugriff brauchen, wofür ein Array oder eine Map besser passt |
Du garantiert O(1) beim Einfügen und Entfernen willst, ohne Rebalancing | Du die Daten sortiert halten musst, was dir ein Heap oder ein Baum liefert |
Stack-Code
Eine saubere, lauffähige Stack-Implementierung in Python, JavaScript, Java, C++, C. Wähle eine Sprache, kopiere den Code oder öffne ihn vorgeladen im Coddy-Playground.
Stack-Code in Python
Python
1stack = []2
3# Push three values onto the top4for value in [3, 7, 5]:5 stack.append(value)6 print(f"push {value} -> {stack}")7
8# Pop them back off: last in, first out9while stack:10 value = stack.pop()11 print(f"pop {value} -> {stack}")12
13print("empty:", len(stack) == 0)Stack-Code in JavaScript
JavaScript
1const stack = [];2
3// Push three values onto the top4for (const value of [3, 7, 5]) {5 stack.push(value);6 console.log(`push ${value} ->`, stack);7}8
9// Pop them back off: last in, first out10while (stack.length > 0) {11 const value = stack.pop();12 console.log(`pop ${value} ->`, stack);13}14
15console.log('empty:', stack.length === 0);Stack-Code in Java
Java
1import java.util.ArrayDeque;2import java.util.Deque;3
4public class Main {5 public static void main(String[] args) {6 Deque<Integer> stack = new ArrayDeque<>();7
8 // Push three values onto the top9 for (int value : new int[] {3, 7, 5}) {10 stack.push(value);11 System.out.println("push " + value + " -> " + stack);12 }13
14 // Pop them back off: last in, first out15 while (!stack.isEmpty()) {16 int value = stack.pop();17 System.out.println("pop " + value + " -> " + stack);18 }19
20 System.out.println("empty: " + stack.isEmpty());21 }22}Stack-Code in C++
C++
1#include <iostream>2#include <stack>3
4int main() {5 std::stack<int> stack;6
7 // Push three values onto the top8 for (int value : {3, 7, 5}) {9 stack.push(value);10 std::cout << "push " << value << " -> size " << stack.size() << "\n";11 }12
13 // Pop them back off: last in, first out14 while (!stack.empty()) {15 int value = stack.top();16 stack.pop();17 std::cout << "pop " << value << " -> size " << stack.size() << "\n";18 }19
20 std::cout << "empty: " << std::boolalpha << stack.empty() << "\n";21 return 0;22}Stack-Code in C
C
1#include <stdio.h>2
3#define CAP 164
5int stack[CAP];6int top = 0; /* index of the next free slot */7
8int main(void) {9 int values[3] = {3, 7, 5};10
11 /* Push three values onto the top */12 for (int i = 0; i < 3; i++) {13 stack[top++] = values[i];14 printf("push %d -> size %d\n", values[i], top);15 }16
17 /* Pop them back off: last in, first out */18 while (top > 0) {19 int value = stack[--top];20 printf("pop %d -> size %d\n", value, top);21 }22
23 printf("empty: %d\n", top == 0);24 return 0;25}Stack FAQ
Was bedeutet LIFO?
Last in, first out: Der zuletzt abgelegte Wert wird als erster wieder entnommen. Das übliche Bild ist ein Stapel Teller, du nimmst den Teller, den du gerade abgestellt hast, nicht den ganz unten. Eine Queue folgt der umgekehrten Regel, FIFO.
Was ist der Unterschied zwischen einem Stack und einer Queue?
Nur das Ende, an dem entfernt wird. Beide fügen an einem Ende in
O(1) hinzu; ein Stack entfernt am selben Ende (LIFO), eine Queue am anderen (FIFO). Alles andere, auch die Komplexitätstabelle oben, ist identisch.Was sind die wichtigsten Stack-Operationen?
push legt einen Wert oben ab, pop entfernt den obersten Wert und gibt ihn zurück, peek (manchmal top) liest den obersten Wert, ohne ihn zu entfernen, und is_empty meldet, ob noch etwas übrig ist. Alle vier sind O(1).Was ist ein Stack Overflow?
Ein push auf einen Stack, der keinen Platz mehr hat. Der berühmte Fall ist der Aufrufstapel: Jeder Funktionsaufruf legt einen Frame ab, deshalb legt eine Rekursion, die ihren Basisfall nie erreicht, so lange weiter ab, bis das Stack-Limit der Laufzeitumgebung erreicht ist und das Programm abstürzt. Der spiegelbildliche Fehler, ein pop auf einem leeren Stack, heißt Stack Underflow.
Wie wird ein Stack implementiert?
Zwei übliche Wege. Ein dynamisches Array legt am Ende ab und entnimmt dort, amortisiert
O(1) und cache-freundlich: So arbeiten Pythons list und Javas ArrayDeque. Eine verkettete Liste legt am Kopf ab und entnimmt dort, im Worst Case O(1) ohne Umkopieren, kostet aber einen Zeiger pro Element. C++' std::stack ist ein Adapter, der standardmäßig auf std::deque läuft, einem segmentierten Array, und bei Bedarf einen anderen Container nimmt.Wo werden Stacks in echten Programmen eingesetzt?
Der Aufrufstapel für Funktionsaufrufe und Rekursion, die Undo- und Redo-Historie, die Zurück-Navigation im Browser, das Auswerten von Ausdrücken und die Klammernprüfung in Parsern sowie der explizite Stack, der eine rekursive Tiefensuche in eine iterative Schleife verwandelt.
Verwandte Ressourcen
Mehr Visualisierungen
