queue-datenstruktur

Queue (Warteschlange)

Kurz: Eine Queue ist eine Datenstruktur nach dem Prinzip FIFO (First In, First Out): Elemente werden hinten angestellt und vorne entnommen – wie an einer Supermarktkasse.

Genauer: Die Hauptoperationen heißen enqueue (hinten anfügen) und dequeue (vorne entnehmen). Queues verwalten Aufträge, die der Reihe nach abgearbeitet werden: Druckaufträge, Netzwerkpakete, Aufgaben für Hintergrundprozesse und Nachrichten in Message-Brokern.

Im Detail

Eine Queue lässt sich mit einer verketteten Liste (Zeiger auf Anfang und Ende) oder einem Ringpuffer umsetzen. Eine Python-Liste ist für pop(0) ungeeignet (O(n)); besser ist collections.deque.

from collections import deque
 
warteschlange = deque()
warteschlange.append("Auftrag 1")    # enqueue
warteschlange.append("Auftrag 2")
warteschlange.append("Auftrag 3")
print(warteschlange.popleft())        # Auftrag 1 (zuerst hinein, zuerst heraus)
print(len(warteschlange))             # 2

Varianten

• Deque (Double-Ended Queue): Einfügen und Entfernen an beiden Enden.
• Prioritätswarteschlange (Priority Queue): Das Element mit der höchsten Priorität kommt zuerst – meist als Heap umgesetzt, genutzt bei Dijkstra und Task-Schedulern.
• Ringpuffer: Feste Größe, überschreibt die ältesten Daten; typisch bei Audio- und Sensordaten.
• Message Queues (RabbitMQ, Kafka) entkoppeln Programme: Der Sender legt Nachrichten ab, der Empfänger verarbeitet sie später.

Breitensuche

Die Breitensuche in Graphen und Bäumen nutzt eine Queue, um Knoten Ebene für Ebene zu besuchen – im Gegensatz zur Tiefensuche mit einem Stack.

Siehe auch: Stack, Liste, Nebenläufigkeit, Datenstrukturen