Was ist eine Queue und wo wird sie verwendet?

Question

Accepted Answer

Eine **Queue** ist eine **FIFO**-Sammlung (First-In, First-Out): Elemente werden am **Ende** hinzugefügt und vom **Anfang** entfernt, wie eine Schlange von Menschen. ## Operationen ```text enqueue(1) enqueue(2) enqueue(3) dequeue()->1 front ->[1][2][3]<- back front ->[2][3]<- back ``` ## Beispiel ```python from collections import deque queue = deque() queue.append('a') # enqueue (back) queue.append('b') first = queue.popleft() # dequeue (front) -> 'a' ``` Eine einfache Python `list` macht `pop(0)` zu einer **O(n)**-Operation, daher sollte `deque` für **O(1)** an beiden Enden verwendet werden. | Operation | Zeit (deque) | |---|---| | enqueue | O(1) | | dequeue | O(1) | | peek front | O(1) | ## Häufige Anwendungen - **Aufgaben- / Job-Planung** — Arbeit in Ankunftsreihenfolge verarbeiten. - **Breadth-first Search (BFS)** — Knoten Ebene für Ebene besuchen. - **Pufferung** — Producer/Consumer-Pipelines, Druckspooler, Request-Warteschlangen. ## Warum es wichtig ist Queues erzwingen Fairness und Reihenfolge, was für Scheduler, Messaging-Systeme und BFS kritisch ist. Wann immer Arbeit "in der Reihenfolge ihres Eintreffens" abgearbeitet werden muss, ist eine Queue die natürliche Lösung.