Queue-Interface in Java (mit 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.

Auf all diese Eigenschaften werde ich im weiteren Verlauf dieses Tutorials eingehen.

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.

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 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 instatiiert 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!
  }
}Code-Sprache: Java (java)

Beim Versuch diesen Code zu compilieren 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 errorCode-Sprache: Klartext (plaintext)

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

Queue<Integer> queue = new ConcurrentLinkedQueue<>();Code-Sprache: Java (java)

(Die verschiedenen Queue-Klassen werden in weiteren Teilen des Tutorials erläutert. Im letzten Teil findest du eine Entscheidungshilfe, wann du welche Implementierung verwenden solltest.)

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());
  }
}
Code-Sprache: Java (java)

Das Programm tut folgendes (die Numerierung verweist auf die Kommentare im Quellcode):

Es erstellt eine Queue. Welche du benutzt, ist für dieses Beispiel irrelevant, da es keine speziellen Queue-Eigenschaften erfordert. Wir verwenden die ConcurrentLinkedQueue.
Die Werte 1 bis 5 werden mit Queue.offer() in die Queue geschrieben. Der Inhalt der Queue wird nach jedem Einfügen angezeigt.
Wir betrachten mit Queue.peek() das Kopf-Element der Queue.
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.
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() = nullCode-Sprache: Klartext (plaintext)

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 kennengelernt. 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 werden wir alle Queue-Implementierungen des JDK einzeln betrachten. Anhand deren besonderer Eigenschaften werde ich dir erklären, wann man welche Implementierung einsetzen sollte.

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.