Java Queue: Methoden, Implementierungen, Beispiel

Das JDK enthält seit Java 5.0 das Interface java.util.Queue und mehrere Queue-Implementierungen, die sich in diversen Eigenschaften (wie bounded/unbounded, blocking/non-blocking, threadsicher/nicht threadsicher) unterscheiden.

In diesem Artikel stelle ich dir das Queue-Interface und seine Methoden vor, vergleiche die Queue-Implementierungen des JDK und zeige dir, welche du wann einsetzen solltest.

Java Queue Klassenhierarchie

Bevor ich die Java-Queue im Detail vorstelle, möchte ich einen Überblick in Form eines UML-Klassendiagramms geben:

Das BlockingQueue-Interface werde ich im nächsten Teil des Tutorials beschreiben.

Die konkreten Queue-Klassen ConcurrentLinkedQueue, PriorityQueue, ArrayBlockingQueue, DelayQueue, LinkedBlockingQueue, PriorityBlockingQueue und SynchronousQueue folgen im Anschluss. Das TransferQueue-Interface erkläre ich zusammen mit der LinkedTransferQueue.

Du kannst zu den entsprechenden Teilen jederzeit über die Tutorial-Navigation am rechten Rand springen.

Die grau eingezeichneten Interfaces Deque und BlockingDeque mitsamt ihren Implementierungen werden in der Tutorial-Serie „Deques“ behandelt. Seit Java 21 erweitert Deque außerdem SequencedCollection.

Worin sich Queue und Deque unterscheiden – und wann du welche der beiden brauchst –, erkläre ich im Artikel Queue vs. Deque in Java.

Java Queue Methoden

Das Queue-Interface definiert sechs Methoden zum Einfügen, Entnehmen und Betrachten von Elementen. Für jede der drei Queue-Operationen „Enqueue“, „Dequeue“ und „Peek“ definiert das Interface jeweils zwei Methoden: eine, die im Fehlerfall eine Exception wirft, und eine, die einen speziellen Wert (false oder null) zurückliefert.

Methoden zum Einfügen in die Queue

Zunächst ein grafischer Überblick über die Enqueue-Methoden:

Queue.add()

Diese Methode ist bereits im Collection-Interface definiert und fügt ein Element in die Queue ein. Bei Erfolg gibt die Methode true zurück. Wenn eine größenbeschränkte Queue voll ist, wirft diese Methode eine IllegalStateException.

Queue.offer()

offer() fügt wie add() ein Element in die Queue ein und gibt bei Erfolg true zurück. Wenn eine größenbeschränkte Queue voll ist, gibt diese Methode false zurück, anstatt eine IllegalStateException zu werfen.

Methoden zum Entnehmen aus der Queue

Auch für die Dequeue-Methoden zunächst ein grafischer Überblick:

Queue.remove()

remove() entnimmt das Element vom Kopf der Queue. Ist die Queue leer, wirft die Methode eine NoSuchElementException.

Queue.poll()

Auch poll() entnimmt das Element am Kopf der Queue. Anders als remove() wirft die Methode bei einer leeren Queue keine Exception, sondern gibt null zurück.

Methoden zum Betrachten des Kopf-Elements

Und wieder zunächst ein Überblick über die Methoden:

Queue.element()

Die element()-Methode gibt das Element vom Kopf der Queue zurück, ohne es aus der Queue zu entnehmen. Ist die Queue leer, wird eine NoSuchElementException geworfen.

Queue.peek()

Genau wie element() gibt auch peek() das Kopf-Element zurück, ohne es aus der Queue zu entfernen. Bei einer leeren Queue gibt diese Methode allerdings – genau wie poll() – null zurück.

Queue-Methoden – Zusammenfassung

Die folgende Tabelle zeigt noch einmal die sechs Methoden gruppiert nach Operation und Art der Fehlerbehandlung:

	im Fehlerfall: Exception	im Fehlerfall: Rückgabewert
Element anhängen (enqueue):	add(E e)	offer(E e)
Element entnehmen (dequeue):	remove()	poll()
Element ansehen (peek):	element()	peek()

Wie erzeugt man eine Queue?

java.util.Queue ist ein Interface. Ein Interface kann nicht instanziiert werden, da es lediglich beschreibt, welche Methoden eine Klasse anbietet, jedoch keine Implementierungen dieser Methoden beinhaltet.

Was passiert, wenn man es dennoch versucht?

public class QueueTest {
  public static void main(String[] args) {
    Queue<Integer> queue = new Queue<>(); // <-- Don't do this!
  }
}

Beim Versuch, diesen Code zu kompilieren, würdest du folgende Fehlermeldung sehen:

QueueTest.java:5: error: Queue is abstract; cannot be instantiated
    Queue<Integer> queue = new Queue<>(); // <-- Don't do this!
                           ^
1 error

Daher muss eine der konkreten Queue-Implementierungen ausgewählt werden, z. B. die ConcurrentLinkedQueue:

Queue<Integer> queue = new ConcurrentLinkedQueue<>();

Das JDK bietet acht Klassen an, die Queue implementieren, aber nicht Deque. Sie unterscheiden sich in Threadsicherheit, Blockierverhalten und Kapazität – der nächste Abschnitt vergleicht sie.

Queue-Implementierungen in Java: Welche einsetzen?

Der Klassenname in der folgenden Tabelle ist jeweils mit demjenigen Artikel der Tutorial-Serie verlinkt, in dem die jeweilige Queue-Implementierung mit all ihren Eigenschaften im Detail erklärt wird. Die vier Deque-Implementierungen vergleiche ich im Artikel über das Deque-Interface.

Eine Erklärung der Begriffe blocking, non-blocking, fairness policy, bounded und unbounded findest du im Artikel über das BlockingQueue-Interface.

¹ Weakly consistent: Alle Elemente, die zum Zeitpunkt der Erzeugung des Iterators in der Queue liegen, werden vom Iterator genau einmal durchlaufen. Änderungen, die danach erfolgen, können – müssen aber nicht – durch den Iterator berücksichtigt werden.

² Fail-fast: Der Iterator wirft eine ConcurrentModificationException, wenn während der Iteration Elemente in die Queue eingefügt oder aus dieser entnommen werden.

³ Übergibst du dem Konstruktor keine Kapazität, liegt die Grenze bei Integer.MAX_VALUE Elementen.

Anhand dieser Eigenschaften kannst du die richtige Queue für jeden Einsatzzweck finden. Für den tagtäglichen Gebrauch der allgemeinen Queue-Implementierungen mache ich folgende Empfehlungen:

• ArrayDeque für single-threaded Anwendungen.
• ConcurrentLinkedQueue als threadsichere, nicht blockierende und unbounded Queue.
• ArrayBlockingQueue als threadsichere, blockierende, bounded Queue, sofern du niedrige bis mittlere Contention zwischen Producer- und Consumer-Threads erwartest.
• LinkedBlockingQueue als threadsichere, blockierende, bounded Queue, wenn du hohe Contention zwischen Producer- und Consumer-Threads erwartest (am besten testen, welche Implementierung für deinen Use Case performanter ist).

Die Wahl zwischen ConcurrentLinkedQueue und LinkedBlockingQueue hängt also davon ab, ob deine Threads warten sollen: ConcurrentLinkedQueue blockiert nie, ist unbounded und schützt ihre verkettete Liste mit Compare-and-set. LinkedBlockingQueue lässt Producer in put() warten, solange sie voll ist, und Consumer in take(), solange sie leer ist; sie schützt ihre verkettete Liste mit zwei Locks und ist bounded.

Hier das Ganze noch einmal als Entscheidungsbaum:

Optimierte MPMC-, MPSC-, SPMC- und SPSC-Queues

Alle vom JDK angebotenen threadsicheren Queue-Implementierungen können bedenkenlos in multi-producer-multi-consumer-Umgebungen eingesetzt werden. Das bedeutet, dass ein oder mehrere schreibende Threads sowie ein oder mehrere lesende Threads nebenläufig auf die JDK-Queues zugreifen können.

Mit speziellen Mechanismen ist es möglich, Queues so zu optimieren, dass der Overhead für das Gewährleisten der Threadsicherheit minimiert wird, wenn es eine Beschränkung auf einen lesenden und/oder einen schreibenden Thread gibt.

Dementsprechend unterscheidet man folgende vier Fälle:

• Multi-producer-multi-consumer (MPMC)
• Multi-producer-single-consumer (MPSC)
• Single-producer-multi-consumer (SPMC)
• Single-producer-single-consumer (SPSC)

Die Open-Source-Bibliothek JCTools bietet für alle vier Fälle hochoptimierte Queue-Implementierungen.

Beispiel: Wie benutzt man eine Queue?

Das folgende Beispiel zeigt, wie man eine Queue erstellt, wie man diese mit einigen Werten befüllt und wie man die Werte wieder entnimmt. Du findest den Beispiel-Code auch auf GitHub.

public class JavaQueueDemo {
  public static void main(String[] args) {
    // 1.
    Queue<Integer> queue = new ConcurrentLinkedQueue<>();

    // 2.
    for (int i = 1; i <= 5; i++) {
      queue.offer(i);
      System.out.println("queue.offer(" + i + ") --> queue = " + queue);
    }

    System.out.println();

    // 3.
    System.out.println("queue.peek() = " + queue.peek());

    System.out.println();

    // 4.
    while (!queue.isEmpty()) {
      System.out.println("queue.poll() = " + queue.poll() + " --> queue = " + queue);
    }

    System.out.println();

    // 5.
    System.out.println("queue.poll() = " + queue.poll());
    System.out.println("queue.peek() = " + queue.peek());
  }
}

Das Programm tut Folgendes (die Nummerierung verweist auf die Kommentare im Quellcode):

1. Es erstellt eine Queue. Welche du benutzt, ist für dieses Beispiel irrelevant, da es keine speziellen Queue-Eigenschaften erfordert. Wir verwenden die ConcurrentLinkedQueue.
2. Die Werte 1 bis 5 werden mit Queue.offer() in die Queue geschrieben. Der Inhalt der Queue wird nach jedem Einfügen angezeigt.
3. Wir betrachten mit Queue.peek() das Kopf-Element der Queue.
4. Solange die Queue Elemente enthält (dies prüfen wir mit der isEmpty()-Methode, die das Queue-Interface von Collection erbt), werden diese mit Queue.poll() entnommen und angezeigt. Danach wird jeweils wieder der gesamte Inhalt der Queue angezeigt.
5. Nachdem die Queue geleert wurde, werden noch einmal die Rückgabewerte von poll() und peek() angezeigt.

Das Programm gibt Folgendes aus:

queue.offer(1) --> queue = [1]
queue.offer(2) --> queue = [1, 2]
queue.offer(3) --> queue = [1, 2, 3]
queue.offer(4) --> queue = [1, 2, 3, 4]
queue.offer(5) --> queue = [1, 2, 3, 4, 5]

queue.peek() = 1

queue.poll() = 1 --> queue = [2, 3, 4, 5]
queue.poll() = 2 --> queue = [3, 4, 5]
queue.poll() = 3 --> queue = [4, 5]
queue.poll() = 4 --> queue = [5]
queue.poll() = 5 --> queue = []

queue.poll() = null
queue.peek() = null

Es ist sehr gut zu sehen, wie die Elemente in derselben Reihenfolge entnommen werden, wie sie eingefügt wurden (First-in-First-out – FIFO).

Zusammenfassung und Ausblick

In diesem Teil des Tutorials hast du das Queue-Interface von Java und seine Methoden kennengelernt, die Queue-Implementierungen des JDK und wann du welche einsetzen solltest. Anhand eines Beispiels hast du gesehen, wie man die Java-Queue benutzt.

Im nächsten Teil schauen wir uns das Interface „BlockingQueue“ genauer an. Dort werde ich auch den Unterschied zwischen bounded und unbounded bzw. blocking und non-blocking Queues erklären.

Danach stelle ich dir jede Queue-Implementierung des JDK mit ihren Eigenschaften im Detail vor.