Stacks und Queues mit deque
Ein Stack arbeitet nach LIFO (Last In, First Out), eine Queue nach FIFO (First In, First Out). Pythons collections.deque ist dafür ideal, weil beide Enden in O(1) manipuliert werden.
Stack
from collections import deque
stack = deque()
stack.append("a")
stack.append("b")
stack.pop() # "b"Queue
queue = deque()
queue.append("a")
queue.popleft() # "a"Warum nicht Liste?
list.pop(0) verschiebt alle Elemente – O(n). deque.popleft() ist O(1). Für reine Stack-Nutzung ist eine normale Liste aber völlig in Ordnung.
Anwendungen
- Undo/Redo in Editoren (Stack).
- Aufgaben-Warteschlangen (Queue).
- BFS-Graphenalgorithmen (Queue).
Weiterführend: Variablen und Datentypen und Kontrollfluss.