Java Queue Interface

Queue<E> ist Collection<E> plus das Konzept eines Kopfes. Der Kopf ist das nächste Element, das entfernt wird; alle anderen warten dahinter. Die Standardsemantik — und die, die fast jede Implementierung im JDK verwendet — ist FIFO: first in, first out. Produzenten fügen Elemente per offer am Ende ein; Konsumenten entnehmen sie per poll vom Kopf. Dieses Kapitel behandelt den Vertrag: die sechs Methoden, die zwei Fehlerbehandlungsstile, die Null-Behandlungsregel und welche Implementierung in welcher Situation verwendet werden sollte.

Zwei Wege für jede Operation — by Design

Jede Warteschlangenoperation gibt es in zwei Varianten: eine, die bei einem Fehler eine Ausnahme wirft, und eine, die einen speziellen Wert zurückgibt. Das Javadoc stellt dies als 3×2-Raster dar:

Die Spalte „wirft" ist diejenige, die von Collection und List geerbt wurde — sie ist vertraut, aber unpraktisch, wenn der leere/volle Fall normal ist (Konsument wartet auf den nächsten Job, begrenzte Warteschlange lehnt einen überschüssigen Produzenten ab). Die Spalte „gibt speziellen Wert zurück" wurde für Warteschlangen hinzugefügt, damit man Schleifen schreiben kann, die nicht auf Ausnahmen für die Steuerung des Kontrollflusses angewiesen sind:

String item;
while ((item = queue.poll()) != null) {
  process(item);
}

Verwende standardmäßig die Returns-Form. Greife auf remove/element nur zurück, wenn eine leere Warteschlange an diesem Punkt ein echter Fehler wäre, der als Ausnahme auftauchen soll.

Null und Queue passen nicht zusammen

Da poll() und peek() null zurückgeben, um „leer" zu signalisieren, ist das Zulassen von null als echtes Element ein Rezept für Mehrdeutigkeit. Jede allgemeine Queue im JDK außer LinkedList lehnt null ab — ArrayDeque, PriorityQueue, ArrayBlockingQueue, alle nebenläufigen Warteschlangen. LinkedList erlaubt das Hinzufügen von null, aber damit bricht man den Vertrag: Es gibt keine Möglichkeit mehr, „Kopf ist null" von „Warteschlange ist leer" zu unterscheiden.

Die Regel: Speichere kein null in einer Warteschlange. Wähle ArrayDeque statt LinkedList, und die Sprache erzwingt es für dich.

FIFO ist der Standard — aber nicht universell

Queue erfordert kein FIFO. Das Interface definiert einen Kopf und Operationen, die von diesem entnehmen; wie der Kopf bestimmt wird, liegt bei der Implementierung. Die zwei Implementierungen in java.util, die kein FIFO sind:

• PriorityQueue — der Kopf ist immer das kleinste Element (gemäß natürlicher Ordnung oder einem Comparator). Einfügungen erfolgen dort, wo der Heap es vorgibt, nicht am Ende.
• Die blockierenden Varianten in java.util.concurrent — PriorityBlockingQueue, DelayQueue usw. — ordnen nach Priorität, Fälligkeit usw. um.

Alles andere (ArrayDeque, LinkedList, ArrayBlockingQueue, LinkedBlockingQueue, ConcurrentLinkedQueue) ist FIFO.

Eine Implementierung auswählen

Für den single-threaded Fall:

• ArrayDeque — der Standard. Zirkuläres Array, keine Allokation pro Element, schnell. Verwende es als Queue<E> oder als Deque<E>, je nachdem ob du Zugriff an beiden Enden benötigst.
• LinkedList — funktioniert, implementiert auch List. Wähle es nur, wenn du wirklich beide Interfaces am selben Objekt benötigst. Das Kapitel über LinkedList behandelt die Kompromisse.
• PriorityQueue — wenn du „kleinstes wartendes Element zuerst" statt FIFO willst.

Für den multi-threaded Fall (wird im Kapitel über Nebenläufigkeit später ausführlich behandelt — hier nur Verweise):

• ConcurrentLinkedQueue — lock-freies FIFO. Unbegrenzt.
• ArrayBlockingQueue — begrenzt, Array-basiert, blockiert put wenn voll und take wenn leer. Die klassische Producer/Consumer-Warteschlange.
• LinkedBlockingQueue — optional begrenzt, Linked-Node-Form derselben.
• PriorityBlockingQueue — nebenläufige PriorityQueue. Unbegrenzt.

Die meisten Anwendungen verwenden eine der ersten vier. Die blockierenden Warteschlangen sind das Mittel, um Worker-Pools und Back-Pressure zu bauen.

Was du auf jeder Queue aufrufen kannst

Über die sechs kopfspezifischen Methoden hinaus ist eine Queue auch eine Collection — also funktionieren size, isEmpty, contains, iterator, forEach, stream, clear, toArray alle. Die Iterationsreihenfolge ist die Reihenfolge, in der Elemente bei FIFO-Implementierungen (ArrayDeque, LinkedList) abgerufen werden, aber bei PriorityQueue ist die Iteratorreihenfolge nicht die Prioritätsreihenfolge — sie durchläuft das zugrunde liegende Heap-Array so wie es ist. Wenn du Elemente in Prioritätsreihenfolge möchtest, musst du die Warteschlange mit poll leeren.

Ein ausgearbeitetes Beispiel: Producer/Consumer in einem Thread

Das Programm unten verwendet ein ArrayDeque als FIFO-Warteschlange, um ein kleines Druckauftragssystem zu modellieren: Jobs kommen im Laufe der Zeit an (wir stellen das dar, indem wir in Batches per offer hinzufügen), und der Worker leert jeden Batch mit poll. Das Fehler-Stilpaar wird oben gezeigt, damit du genau siehst, wann jede Form ausgelöst wird.

Ein paar Dinge, die aus der Ausgabe abzulesen sind:

• poll und peek gaben stillschweigend null zurück, als die Warteschlange leer war; remove und element warfen Ausnahmen. Beide Verhaltensweisen sind Teil des Vertrags — wähle diejenige, die dazu passt, ob „leer" ein Fehler oder nur ein Zustand ist.
• offer(null) warf bei ArrayDeque. Die Implementierung erzwingt damit die Regel, von der das Interface abhängt.
• Die PriorityQueue pollte 10, 20, 30, 40 — sortierte Reihenfolge, nicht Einfügereihenfolge. Dasselbe Queue-Interface, aber eine völlig andere Kopf-Auswahlregel.

Was kommt als Nächstes

Die erste Nicht-FIFO-Implementierung verdient ein eigenes Kapitel — PriorityQueue ist eine Heap-basierte Warteschlange, bei der der Kopf immer das kleinste Element ist. Das ist der grundlegende Baustein für praktisch jeden „verarbeite die dringendste Aufgabe als nächstes"-Scheduler im JDK.

Übungen