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).
Teil 1·Erklärung
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):
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.
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)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.
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)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.
Faustregel zum Mitnehmen: Stack = Bücherstapel (oben), Queue = Schlange (vorne raus). Genau dieser Kontrast steckt in jeder Klausurfrage zum Thema.
Anmelden, um den Fortschritt zu speichern.
Nächster Schritt
Aktives Abrufen festigt Wissen schneller als nochmal lesen.
Diese Lerneinheit wurde für typische Bachelor-Klausuren konzipiert. So prüfen wir · Fehler entdeckt? Melde ihn uns oder markiere die fragliche Stelle direkt im Text oben.
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: 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):
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) |
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.
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.
Überall, wo man rückwärts durch eine Verarbeitung muss:
{[()]} ist gültig, push bei "auf", pop bei "zu" und vergleichenPush 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)
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) |
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).
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)!
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.
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.
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.