Queue Datenstruktur

In diesem Tutorial lernst du alles über den abstrakten Datentyp "Queue" (im deutschen auch als "Warteschlange" bezeichnet):

• Wie funktioniert eine Queue?
• Was sind die Anwendungsgebiete für Queues?
• Welche Queue-Interfaces und -Klassen gibt es im JDK?
• Was sind blocking, non-blocking, bounded und unbounded Queues?
• Wie implementiert man eine Queue in Java?

Was ist eine Queue?

Eine Queue ist eine Liste von Elementen, bei der die Elemente auf einer Seite eingefügt und in derselben Reihenfolge auf der anderen Seite wieder entnommen werden.

Man kann sich das wie eine Warteschlange an einer Kasse oder bei einer Behörde vorstellen:

Ankommende Personen stellen sich am Ende der Schlange (rechts im Bild) an. Sobald ein Kunde abgefertigt wurde, kommt der nächste Kunde vom Kopf der Schlange (links) an die Reihe.

Die Person, die sich zuerst angestellt hat, kommt somit auch zuerst an die Reihe. Daher sprechen wir vom First-in-First-out-Prinzip (FIFO).

FIFO-Prinzip bei Queues

Beim abstrakten Datentyp "Queue" kann das wie im folgenden Beispiel aussehen:

Die Grafik zeigt eine Queue, die die Elemente 6, 7, 8, usw. bis 13 enhält. Die 5 wurde gerade vom Kopf der Queue (englisch "Front" oder "Head", links im Bild) entnommen und die 14 wird gerade an das Ende der Queue ("Back", "Tail" oder "Rear" im englischen, rechts im Bild) eingefügt.

Queue Operationen: Enqueue und Dequeue

Die Operationen der Queue bezeichnen wir wie folgt:

• "Enqueue": Einfügen neuer Elemente am Ende der Queue
• "Dequeue": Entnehmen von Elementen vom Kopf der Queue
• "Peek" oder "Front": Betrachten des Elements am Kopf, ohne es zu entnehmen (optional)

(Die entsprechenden Methoden der Java-Queue-Implementierungen heißen übrigens anders; mehr dazu im nächsten Teil des Tutorials, "Java Queue-Interface".)

Anwendungsgebiete für Queues

Ein Anwendungsbereich von Queues, den wir alle kennen, ist die Druckerwarteschlange. Verschiedene Programme stellen dort Druckaufträge ein. In der Regel gibt es nur einen Drucker, der diese dann der Reihe nach abarbeitet.

Ein technisches Anwendungsbeispiel ist die Verarbeitung von HTTP-Requests in einem Webserver. Ein Webserver arbeitet in der Regel mit einem Threadpool für gleichzeitig abzuarbeitende Requests. Wenn mehr Anfragen hereinkommen als gleichzeitig abgearbeitet werden können, ist der Threadpool ausgelastet. Zusätzliche Requests werden dann in eine Warteschlange gestellt und in First-in-First-out-Reihenfolge abgearbeitet, sobald wieder Threads zur Verfügung stehen.

Zeitkomplexität der Queue-Operationen

Eine Einführung in das Thema Zeitkomplexität findest du im Artikel "O-Notation und Zeitkomplexität – anschaulich erklärt".

Queues werden in der Regel mit Arrays oder verketteten Listen implementiert. Bei beiden Varianten ist der Aufwand für die Enqueue- und Dequeue-Operationen jeweils konstant, d. h. der Aufwand ändert sich nicht mit der Länge der Queue.

Die Zeitkomplexität dieser Operationen lautet also: O(1).

Zu Übungszwecken kann man eine Queue auch mit Stacks implementieren (dazu mehr in einem späteren Teil des Tutorials). Die Zeitkomplexität ist dann allerdings höher.

Wenn du noch Fragen hast, stelle sie gerne über die Kommentar-Funktion. Möchtest du über neue Tutorials und Artikel informiert werden? Dann klicke hier, um dich für den HappyCoders.eu-Newsletter anzumelden.