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).
Stack
Stack
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: ein Buch oben drauf legen (push) und oben wieder wegnehmen (pop). Auf Bücher in der Mitte kannst du nicht direkt zugreifen. Du lernst hier die zwei Kern-Datenstrukturen Stack (LIFO) und Queue (FIFO), ihre Standard-Operationen push/pop/peek bzw. enqueue/dequeue (alle in O(1) bei passender Implementierung), warum Suche und remove(Object) dagegen O(n) sind, wann du welche Struktur brauchst (Browser-Back, Funktions-Calls, BFS/DFS-Traversal, Druckwarteschlangen) und warum Java's veraltete Stack-Klasse durch Deque/ArrayDeque ersetzt werden sollte.
Die zentralen Operationen, alle in O(1):
- push(x): legt x oben drauf
- pop(): entfernt und liefert das oberste Element
- peek() / top(): liefert das oberste Element ohne es zu entfernen
- isEmpty(): prüft ob der Stack leer ist
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.
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) |
Kern-Operationen O(1) bei passenden Implementierungen, bei dynamischen Arrays amortisiert O(1) (gelegentliches Resize). Suchen oder Entfernen eines bestimmten Elements (contains, remove(Object)) ist nicht O(1), sondern linear.
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)Java: `ArrayDeque` ist die empfohlene Stack-Implementierung. `java.util.Stack` ist eine **Legacy-Klasse** (technisch nicht @Deprecated, aber synchronisiert und langsam), die offizielle Java-Doku empfiehlt explizit `Deque` für Stack-Verhalten. **Praxis-Hinweis**: dieser Java-spezifische Hinweis ist nicht durch die ALGORITHMS-Trusted-Sources gedeckt, sondern stammt aus der OpenJDK-Doku.
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.
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: stark vereinfachtes didaktisches Modell mit zwei Stacks (Back-Stack + Forward-Stack), bei "zurück" wandert das oberste Element vom Back-Stack auf den Forward-Stack. Reale Browser nutzen eher Verlaufslisten mit Index und behandeln tab-spezifische History und reverse-Navigation komplexer, also keine Eins-zu-eins-Abbildung mit einem Stack.
- 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, führe pop aus, 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)
Queue
Queue
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):
- enqueue(x): hängt x hinten an
- dequeue(): entfernt und liefert das vorderste Element
- front() / peek(): liefert das vorderste Element ohne es zu entfernen
- isEmpty(): prüft ob die Queue leer ist
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.
Operationen
| 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) |
Kern-Operationen O(1) bei passenden Implementierungen, bei dynamischen Arrays amortisiert O(1). Aber Achtung: das gilt nur mit der richtigen Datenstruktur darunter, bei Python list.pop(0) ist es z. B. O(n).
Implementierung
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. **Allgemeiner Queue-Stil**: offer() zum Einfügen (gibt false zurück bei kapazitätsbeschränkten Queues statt Exception), poll() zum Entfernen (null bei leerer Queue), peek() zum Anschauen (null bei leer).
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)!
Falle: pop(0) auf Python list
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.
Wofür brauchst du eine Queue?
Überall, wo faire Reihenfolge wichtig ist:
- Druckaufträge: wer zuerst druckt, ist zuerst dran
- Task-Queues in Servern: Anfragen abarbeiten in Reihenfolge des Eingangs
- Breitensuche (BFS) bei Bäumen und Graphen
- Producer-Consumer-Pattern: ein Thread füllt, ein anderer leert
Probier es selbst
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.
Vergleich
Stack vs Queue
Du kennst jetzt beide. Die zwei Datenstrukturen sehen ähnlich aus, verhalten sich aber gegensätzlich.
Übersicht
| 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 |
Der Unterschied in einem Bild
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.
Wann welche?
- Stack: wenn du rückwärts durch eine Verarbeitung musst (Undo, DFS, Klammern)
- Queue: wenn faire Reihenfolge wichtig ist (BFS, Druckaufträge, Tasks)
Live-Vergleich
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.
Code-Stepper: Stack push/pop mit internem Array
Hier siehst du wie ein Stack intern auf einem Array umgesetzt ist. top zeigt auf die nächste freie Position. push schreibt arr[top] und erhöht top, pop dekrementiert top und liefert das Element. Beide Operationen sind O(1), weil nur top verändert wird, nicht das ganze Array.
Interaktive Visualisierung
Interaktive Komponente: probiere sie im Topic-Player oben aus.
Quiz
Klausurfragen mit Lösungen (7)
- F1.Was bedeutet LIFO?
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.
- F2.Du startest mit leerem Stack. Operationen: push(5), push(8), push(3), pop, pop. Was wird beim letzten pop zurückgegeben?
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.
- F3.Welche der folgenden Anwendungen passt am besten zu einer Queue (FIFO)?
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.
- F4.Welche Komplexität hat enqueue in einer Queue, die mit Java's ArrayDeque oder Python's deque implementiert ist?
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).
- F5.Was passiert wenn du Folgendes ausführst?
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.
- F6.Warum ist es in Python eine schlechte Idee, eine Queue mit list und pop(0) zu implementieren?
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.
- F7.Du implementierst eine Tiefensuche (DFS) durch einen Baum. Welche Datenstruktur hilft dir intern?
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.
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);
stack.push(2);
stack.push(3);
System.out.println(stack.peek());
