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.
Ein Stack ist eine Datenstruktur nach dem LIFO-Prinzip (Last In, First Out): das zuletzt eingefügte Element wird zuerst entfernt. Stell dir einen Bücherstapel vor: oben drauflegen (push), oben wegnehmen (pop), kein Zugriff auf Bücher in der Mitte.
Die zentralen Operationen, alle in O(1):
Klausur-typische Anwendungen: Klammern-Matching (jede ( pusht, jede ) popt), Funktionsaufrufe in einem Programm (Call-Stack), Undo-Funktion in Editoren, Tiefensuche (DFS) auf Graphen. Wenn die Aufgabe nach "letzter eingefügter Wert zuerst" klingt, ist es ein Stack.
LIFO — Last In, First Out: was zuletzt rein kam, kommt zuerst raus.
| 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.
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)Überall, wo man rückwärts durch eine Verarbeitung muss:
{[()]} ist gültig — push bei "auf", pop bei "zu" und vergleichenPush 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)
Alle Tabs der Lerneinheit (Stack · Queue · Vergleich · Quiz) als durchgehender Text. Ideal zum Wiederholen vor der Klausur — und für Suchmaschinen wie Google, Bing und KI-Suche (ChatGPT, Perplexity).
Ein Stack ist eine Datenstruktur nach dem LIFO-Prinzip (Last In, First Out): das zuletzt eingefügte Element wird zuerst entfernt. Stell dir einen Bücherstapel vor: oben drauflegen (push), oben wegnehmen (pop), kein Zugriff auf Bücher in der Mitte.
Der intuitive Sortieralgorithmus: zwei verschachtelte Schleifen, größere Werte blubbern nach oben. Einfach zu erklären, in der Praxis aber zu langsam: O(n²).
Teile und Herrsche. Garantierte O(n log n) durch rekursives Halbieren plus Merge. Stabil, aber braucht O(n) Zusatzspeicher. Klausur-Klassiker schlechthin.
Der schnellste der Klassiker im Average Case: O(n log n), in-place, partitioniert um einen Pivot. Bei sortiertem Input rutscht er aber auf O(n²) ab.
Die zentralen Operationen, alle in O(1):
Klausur-typische Anwendungen: Klammern-Matching (jede ( pusht, jede ) popt), Funktionsaufrufe in einem Programm (Call-Stack), Undo-Funktion in Editoren, Tiefensuche (DFS) auf Graphen. Wenn die Aufgabe nach "letzter eingefügter Wert zuerst" klingt, ist es ein Stack.
LIFO — Last In, First Out: was zuletzt rein kam, kommt zuerst raus.
| 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.
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)Java: ArrayDeque ist die empfohlene Stack-Implementierung. Die ältere Stack-Klasse ist veraltet (synchronisiert, langsam).
stack = []
stack.append(1) # [1]
stack.append(2) # [1, 2]
stack.append(3) # [1, 2, 3]
top = stack[-1] # 3 — nur reingucken
x = stack.pop() # 3 — entfernt
y = stack.pop() # 2
empty = len(stack) == 0 # FalsePython: list ist gleichzeitig Stack-Implementierung. append() = push, pop() = pop, [-1] = peek.
Überall, wo man rückwärts durch eine Verarbeitung muss:
{[()]} ist gültig — push bei "auf", pop bei "zu" und vergleichenPush neue Werte, mach pop, schau dir mit peek das Top-Element an. Beobachte: das Element, das oben liegt, ist immer das zuletzt gepushte.
Interaktive Visualisierung
Stack (LIFO) und Queue (FIFO) mit push/pop bzw. enqueue/dequeue im Vergleich.
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)
Eine Queue ist eine Datenstruktur nach dem FIFO-Prinzip (First In, First Out): das zuerst eingefügte Element wird zuerst entfernt. Stell dir die Schlange am Bäcker vor: hinten anstellen (enqueue), vorne bedient werden (dequeue).
Die zentralen Operationen, alle in O(1):
Klausur-typische Anwendungen: Druckerwarteschlange, Breitensuche (BFS) auf Graphen, Event-Verarbeitung, Buffer in der Inter-Prozess-Kommunikation. Wenn die Aufgabe nach "wer zuerst da war, kommt zuerst dran" klingt, ist es eine Queue.
FIFO — First In, First Out: was zuerst rein kam, kommt zuerst raus.
| Operation | Was sie tut | Komplexität |
|---|---|---|
| enqueue(x) | x hinten anhängen | O(1) |
| dequeue() | vordersten Wert entfernen + zurückgeben | O(1) |
| front() / peek() | vordersten Wert anschauen, ohne zu entfernen | O(1) |
| isEmpty() | true wenn Queue leer | O(1) |
Alle Operationen O(1) — wie beim Stack. Aber Achtung: das gilt nur mit der richtigen Datenstruktur darunter.
import java.util.ArrayDeque;
import java.util.Queue;
Queue<Integer> queue = new ArrayDeque<>();
queue.add(1); // [1]
queue.add(2); // [1, 2]
queue.add(3); // [1, 2, 3]
int front = queue.peek(); // 1 — nur reingucken
int x = queue.poll(); // 1 — entfernt (front)
int y = queue.poll(); // 2
boolean empty = queue.isEmpty(); // false (3 noch drin)Java: ArrayDeque implementiert sowohl Stack als auch Queue. add() ist enqueue, poll() ist dequeue.
from collections import deque
queue = deque()
queue.append(1) # [1]
queue.append(2) # [1, 2]
queue.append(3) # [1, 2, 3]
front = queue[0] # 1 — nur reingucken
x = queue.popleft() # 1 — entfernt (front)
y = queue.popleft() # 2
empty = len(queue) == 0 # FalsePython: collections.deque hat O(1) für beide Enden. WICHTIG: nicht list mit pop(0) verwenden — das wäre O(n)!
Du könntest denken: "Eine Queue baue ich einfach mit list und pop(0)." — NEIN.
my_queue = [1, 2, 3, 4, 5]
my_queue.pop(0) # entfernt 1, ABER...
Nach pop(0) müssen alle anderen Elemente eine Position nach links rutschen. Das ist O(n). Bei einer Queue mit vielen dequeue-Operationen wird das richtig langsam.
Lösung: collections.deque hat O(1) auf beiden Seiten.
Überall, wo faire Reihenfolge wichtig ist:
Interaktive Visualisierung
Stack (LIFO) und Queue (FIFO) mit push/pop bzw. enqueue/dequeue im Vergleich.
Klausur-Trick: Beim Queue immer dran denken: vorne raus, hinten rein. Genau wie eine Schlange beim Bäcker.
Du kennst jetzt beide. Die zwei Datenstrukturen sehen ähnlich aus, verhalten sich aber gegensätzlich.
| Stack | Queue | |
|---|---|---|
| Prinzip | LIFO | FIFO |
| Hinzufügen | push (oben) | enqueue (hinten) |
| Entfernen | pop (oben) | dequeue (vorne) |
| Anschauen | peek (oben) | front (vorne) |
| Komplexität | alle O(1) | alle O(1) |
| Java | ArrayDeque | ArrayDeque |
| Python | list | collections.deque |
| Beispiel | Bücherstapel | Bäcker-Schlange |
Operationen: 1, 2, 3 hinzufügen, dann entfernen
STACK (LIFO) QUEUE (FIFO)
push 1: [1] enq 1: [1]
push 2: [1, 2] enq 2: [1, 2]
push 3: [1, 2, 3] enq 3: [1, 2, 3]
pop: → liefert 3 deq: → liefert 1
pop: → liefert 2 deq: → liefert 2
Gleiche Eingabe, umgekehrte Ausgabe-Reihenfolge. Das ist der ganze Trick.
Klick durch die Operationen und beobachte beide gleichzeitig. Push 3× auf den Stack und enqueue 3× in die Queue, dann pop und dequeue: du siehst sofort, dass aus dem Stack das letzte rauskommt, aus der Queue das erste.
Interaktive Visualisierung
Stack (LIFO) und Queue (FIFO) mit push/pop bzw. enqueue/dequeue im Vergleich.
Faustregel zum Mitnehmen: Stack = Bücherstapel (oben), Queue = Schlange (vorne raus). Genau dieser Kontrast steckt in jeder Klausurfrage zum Thema.
Klausurfragen mit Lösungen (7)
Antwort: Last In, First Out — was zuletzt rein kam, kommt zuerst raus
Erklärung: LIFO = Last In, First Out. Das Prinzip eines Stacks: der zuletzt gepushte Wert kommt mit pop als erster wieder raus.
Antwort: 8
Erklärung: Nach push(5,8,3): Stack ist [5, 8, 3] mit 3 oben. Erstes pop entfernt 3. Zweites pop entfernt 8. Antwort: 8.
Antwort: Druckaufträge in der Reihenfolge des Eingangs abarbeiten
Erklärung: Druckaufträge sind ein klassisches FIFO-Problem: wer zuerst druckt, soll zuerst gedruckt werden. Undo, Klammerprüfung und DFS sind alle Stack-Aufgaben.
Antwort: O(1)
Erklärung: Sowohl ArrayDeque als auch deque haben O(1) für enqueue UND dequeue. Das ist der Grund, warum man nicht einfach list mit pop(0) nimmt — pop(0) wäre O(n).
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);
stack.push(2);
stack.push(3);
System.out.println(stack.peek());Antwort: 3
Erklärung: peek (Java) bzw. stack[-1] (Python) gibt das oberste Element zurück, ohne es zu entfernen. Nach push(1,2,3) ist 3 oben.
Antwort: pop(0) ist O(n), weil alle Elemente nach links rutschen müssen
Erklärung: list.pop(0) entfernt das erste Element, danach müssen alle anderen eine Position nach links wandern: O(n). collections.deque hat O(1) auf beiden Seiten.
Antwort: Stack (LIFO)
Erklärung: DFS = Depth-First Search: tief rein, dann zurück. Das ist genau das Stack-Verhalten. BFS (Breitensuche) dagegen nutzt eine Queue.