Enqueue und Dequeue in Java

In Java fügt Enqueue ein Element am Ende einer FIFO-Warteschlange ein, und Dequeue entfernt das Element an ihrem Anfang. Das Queue-Interface definiert diese Operationen; LinkedList ist eine Klasse, die es implementiert. Verwende offer und poll, wenn Rückgabewerte anzeigen sollen, ob das Einfügen erfolgreich war oder kein Element am Anfang verfügbar war.

Warteschlange und FIFO

Eine Warteschlange verarbeitet Elemente nach dem First-in-first-out-Prinzip (FIFO): Der zuerst hinzugefügte Wert wird als Erster entfernt. Eingefügt wird am Ende der Warteschlange, entfernt und geprüft wird am Anfang. Diese Reihenfolge ist nützlich, wenn ein Programm eingereichte Aufträge, Ereignisse oder Nachrichten in der Reihenfolge ihres Eingangs verarbeiten soll.

Javas Queue ist ein Interface des Collections Frameworks. Es beschreibt die üblichen Warteschlangenoperationen, ohne eine bestimmte Speicherstrategie vorzugeben. Implementierungen können sich in Kapazitätsgrenzen und Leistung unterscheiden. Wähle daher eine passende Implementierung, statt anzunehmen, dass sich alle Warteschlangen gleich verhalten.

Eine verwandte Erklärung des Ordnungsprinzips findest du im Java-Leitfaden zu FIFO-Warteschlangen.

Enqueue und Dequeue

Enqueue bezeichnet das Einfügen eines Elements am Ende der Warteschlange. Dequeue bezeichnet das Entfernen des Elements an ihrem Anfang. Diese Begriffe benennen Warteschlangenoperationen; Deque ist nicht dasselbe wie eine Dequeue-Operation. Deque ist ein separates Java-Interface für Collections, die das Einfügen und Entfernen an beiden Enden unterstützen.

Das erste Element einer Warteschlange lässt sich auch prüfen, ohne es zu entfernen. Das ist hilfreich, wenn der Code entscheiden muss, was als Nächstes verarbeitet wird, die Reihenfolge der Warteschlange aber erhalten bleiben soll.

Queue-Methoden in Java

Beim Einfügen fügen add(E) und offer(E) ein Element hinzu, wenn die Warteschlange es annimmt. Bei begrenzter Kapazität verhalten sie sich unterschiedlich: Verhindert eine Kapazitätsgrenze das Einfügen, wirft add eine IllegalStateException, während offer false zurückgibt. Eine Warteschlange ohne feste Kapazitätsgrenze kann sich anders verhalten; das Ergebnis hängt von der Implementierung ab.

Beim Entfernen gibt remove() das erste Element zurück und entfernt es. Ist die Warteschlange leer, wirft die Methode eine NoSuchElementException. Auch poll() gibt das erste Element zurück und entfernt es, liefert aber null, wenn kein Element vorhanden ist. Verwende poll(), wenn eine leere Warteschlange ein erwarteter Zustand ist, den der aufrufende Code anhand des Rückgabewerts behandeln soll.

element() und peek() prüfen das erste Element, ohne es zu entfernen. Ist die Warteschlange leer, wirft element() eine NoSuchElementException, während peek() null zurückgibt. Bei diesen Methodenpaaren kannst du wählen, ob eine leere Warteschlange durch eine Ausnahme oder einen speziellen Rückgabewert signalisiert werden soll. Da poll() und peek() null zurückgeben, wenn kein Element am Anfang verfügbar ist, solltest du keine null-Werte in der Warteschlange speichern, wenn dein Code diesen Fall von einem gespeicherten Wert unterscheiden muss.

Enqueue und Dequeue mit LinkedList implementieren

Das folgende vollständige Programm verwendet das Interface Queue<String> mit einer Implementierung vom Typ LinkedList<String>. Es fügt zwei Werte hinzu, prüft das erste Element und entfernt anschließend beide Werte in FIFO-Reihenfolge.

import java.util.LinkedList;
import java.util.Queue;

public class QueueExample {
    public static void main(String[] args) {
        Queue<String> queue = new LinkedList<>();

        queue.offer("First");
        queue.offer("Second");
        System.out.println("Head: " + queue.peek());
        System.out.println("Removed: " + queue.poll());
        System.out.println("Removed: " + queue.poll());
    }
}

Head: First
Removed: First
Removed: Second

Der protokollierte Lauf erzeugte die oben gezeigte Ausgabe. Die erste Prüfung liest First, ohne den Wert zu entfernen. Die beiden anschließenden Aufrufe von poll() entfernen erst First und dann Second. Der Typ ist als Queue<String> deklariert, sodass der Code nur von den benötigten Warteschlangenoperationen abhängt; LinkedList stellt die konkrete Implementierung bereit. Andere Queue-Implementierungen lassen sich einsetzen, wenn ihre Kapazitäts- und Reihenfolgeeigenschaften zur Anwendung passen.

Entscheidend ist, welche Regeln für leere Warteschlangen und Kapazitätsgrenzen der aufrufende Code benötigt: Verwende offer, poll und peek, wenn ihre Rückgabewerte zum regulären Programmablauf gehören. Verwende add, remove und element, wenn der jeweilige Ausnahmefall an den aufrufenden Code weitergegeben werden soll.