Was ist eine Queue und wo wird sie verwendet?

Question

IT Interview Practice · 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.

Operationen

Beispiel

Häufige Anwendungen

Warum es wichtig ist

Ähnliche Fragen