Stack und Queue
Zwei fundamentale Datenstrukturen: Stack (LIFO) wie ein Bücherstapel, Queue (FIFO) wie eine Schlange. Alle Operationen O(1). Brücke zu Bäumen und Graphen.
Stack
Stell dir einen Bücherstapel vor. Du legst neue Bücher oben drauf und nimmst auch oben drauf welche weg. Das letzte Buch, das du draufgelegt hast, ist das erste, das du wieder runternimmst.
LIFO — Last In, First Out: was zuletzt rein kam, kommt zuerst raus.
Operationen
| Operation | Was sie tut | Komplexität |
|---|---|---|
| push(x) | x oben drauflegen | O(1) |
| pop() | obersten Wert entfernen + zurückgeben | O(1) |
| peek() / top() | obersten Wert anschauen, ohne zu entfernen | O(1) |
| isEmpty() | true wenn Stack leer | O(1) |
Alle Operationen O(1) — der Stack ist eine der schnellsten Datenstrukturen überhaupt.
Implementierung
import java.util.ArrayDeque;
import java.util.Deque;
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1); // [1]
stack.push(2); // [1, 2]
stack.push(3); // [1, 2, 3]
int top = stack.peek(); // 3 — nur reingucken
int x = stack.pop(); // 3 — entfernt
int y = stack.pop(); // 2
boolean empty = stack.isEmpty(); // false (1 ist noch drin)Wofür brauchst du einen Stack?
Überall, wo man rückwärts durch eine Verarbeitung muss:
- Function-Call-Stack: jede Funktion legt ihre lokalen Variablen oben drauf, beim return wird oben wieder runter
- Undo-Funktion in Editoren: jede Aktion oben drauf, Strg+Z = pop
- Browser-Verlauf (Zurück-Button): Stack der besuchten Seiten
- Klammerprüfung:
{[()]}ist gültig — push bei "auf", pop bei "zu" und vergleichen - Tiefensuche (DFS) bei Bäumen und Graphen
Probier es selbst
Push neue Werte, mach pop, schau dir mit peek das Top-Element an. Beobachte: das Element, das oben liegt, ist immer das zuletzt gepushte.
Klausur-Trick: Bei einer Frage wie "Was kommt mit pop heraus nach push(1), push(2), push(3)?" immer mitschreiben:
push 1: [1]
push 2: [1, 2]
push 3: [1, 2, 3]
pop: → 3 (das oberste)