In diesem Tutorial lernst du den abstrakten Datentyp „Queue“ kennen (im Deutschen auch als „Warteschlange“ bezeichnet):
- Wie funktioniert eine Queue?
- Wie heißen ihre Operationen – und wie heißen sie in Java?
- Welche Varianten der Queue gibt es?
- Was sind die Anwendungsgebiete für Queues?
- Wie aufwendig sind die Enqueue- und Dequeue-Operationen?
Was ist eine Queue?
Eine Queue ist eine Folge 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 eine Person abgefertigt wurde, kommt die nächste 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 enthä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 (englisch „Back“, „Tail“ oder „Rear“, 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)
Aus einer leeren Queue kann die Dequeue-Operation nichts entnehmen. Hat eine Queue eine feste Kapazität und ist sie voll, kann die Enqueue-Operation nichts einfügen. Wie eine Implementierung darauf reagiert – mit einem speziellen Rückgabewert oder mit einer Exception –, legt sie selbst fest.
Die Queue-Operationen in Java
Das Queue-Interface des JDK bietet jede der drei Operationen in zwei Varianten an: Die eine wirft eine Exception, wenn die Operation nicht möglich ist, die andere liefert einen speziellen Rückgabewert.
| Operation | im Fehlerfall: Exception | im Fehlerfall: Rückgabewert |
|---|---|---|
| Enqueue | add() | offer() – false, wenn die Queue voll ist |
| Dequeue | remove() | poll() – null, wenn die Queue leer ist |
| Peek | element() | peek() – null, wenn die Queue leer ist |
add() wirft eine IllegalStateException, remove() und element() werfen eine NoSuchElementException. Die meisten Queue-Implementierungen haben übrigens keine Kapazitätsgrenze – bei ihnen schlägt das Einfügen nie fehl.
Varianten der Queue
In dieser Tutorial-Serie lernst du drei Abwandlungen der einfachen FIFO-Queue kennen:
- Priority Queue: Sie entnimmt die Elemente nicht in der Reihenfolge des Einfügens, sondern nach ihrer Priorität. Damit weicht sie vom FIFO-Prinzip ab. Das JDK bietet dafür u. a. die Klasse
PriorityQueuean. - Deque („Double-ended Queue“): Sie erlaubt das Einfügen und Entnehmen an beiden Enden. Mehr dazu erfährst du in der Tutorial-Serie über Deques.
- Bounded und Blocking Queue: Eine bounded Queue hat eine feste Kapazität. Eine blocking Queue lässt den aufrufenden Thread warten, bis ein Element verfügbar ist (beim Entnehmen) bzw. bis Platz frei ist (beim Einfügen). Beides erkläre ich im Artikel über das BlockingQueue-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.
Auch Algorithmen setzen Queues ein. Bei der Breitensuche im Binärbaum merkt sich der Algorithmus die noch zu besuchenden Knoten in einer Queue – so besucht er die Knoten Ebene für Ebene.
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., er ändert sich nicht mit der Länge der Queue.
Die Zeitkomplexität dieser Operationen lautet also: O(1).
Eine Ausnahme gibt es beim Array: Ist es voll und soll die Queue weiter wachsen, muss die Enqueue-Operation ein neues, größeres Array anlegen und alle Elemente dorthin umkopieren – dieser eine Aufruf kostet O(n). Weil das Array dabei jedes Mal proportional zu seiner Größe wächst (in der ArrayQueue dieser Serie auf das 1,5- bis 2-Fache), kommt das selten vor, und über viele Aufrufe gemittelt bleibt der Aufwand konstant. Man spricht von amortisiert O(1).
Zu Übungszwecken kann man eine Queue auch mit Stacks implementieren (dazu mehr in einem späteren Teil des Tutorials). Mit der dort gezeigten Variante kostet die Enqueue-Operation allerdings O(n): Für jedes neue Element werden alle vorhandenen Elemente zweimal umgeschichtet.
Ausblick
Im nächsten Teil des Tutorials lernst du das Queue-Interface von Java im Detail kennen: seine Methoden, die Klassenhierarchie und welche der JDK-Implementierungen du wann einsetzt.
Konntest du etwas aus diesem Artikel mitnehmen? Mit einer Bewertung auf meinem ProvenExpert-Profil hilfst du anderen Entwickler:innen einzuschätzen, ob sich das Lesen lohnt – und mir zu verstehen, welche Inhalte dir weiterhelfen.
