Deque-Datenstruktur: Was ist ein Deque (Double-ended Queue)?

In diesem Tutorial lernst du die Datenstruktur „Deque“ kennen (ausgesprochen „Deck“):

• Was ist ein Deque?
• Welche Operationen bietet ein Deque an – und wie heißen sie in Java?
• Welche Varianten des Deques gibt es?
• Was sind die Anwendungsgebiete für Deques?
• Wie aufwendig sind die Deque-Operationen?

Was ist ein Deque?

Ein Deque ist eine Folge von Elementen, bei der die Elemente sowohl auf der einen als auch auf der anderen Seite eingefügt und entnommen werden können. Deque steht für „Double-ended Queue“, also für eine Queue mit zwei Enden:

Ein Deque kann sowohl als Queue als auch als Stack eingesetzt werden:

• Als Queue (FIFO, first-in-first-out), indem Elemente auf einer Seite eingefügt und auf der anderen Seite wieder entnommen werden.
• Als Stack (LIFO, last-in-first-out), indem Elemente an derselben Seite eingefügt und wieder entnommen werden.

Wir müssen uns beim Deque aber nicht auf FIFO- oder LIFO-Funktionalität beschränken. Wir können die Elemente jederzeit an einer beliebigen Seite einfügen und wieder entnehmen.

Deque-Operationen

Die Operationen des Deques heißen analog zur Queue auf beiden Seiten „Enqueue“ und „Dequeue“; dazu kommt „Peek“:

• „Enqueue at front“: Einfügen eines Elements am Kopf des Deques
• „Enqueue at back“: Einfügen eines Elements am Ende des Deques
• „Dequeue at front“: Entnehmen eines Elements vom Kopf des Deques
• „Dequeue at back“: Entnehmen eines Elements vom Ende des Deques
• „Peek at front“ und „Peek at back“: Betrachten des Elements am Kopf bzw. am Ende, ohne es zu entnehmen (optional)

Aus einem leeren Deque können die Dequeue-Operationen nichts entnehmen. Hat ein Deque eine feste Kapazität und ist es voll, können die Enqueue-Operationen nichts einfügen. Wie eine Implementierung darauf reagiert – mit einem speziellen Rückgabewert oder mit einer Exception –, legt sie selbst fest.

Die Deque-Operationen in Java

Das Deque-Interface des JDK bietet jede der sechs 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 at front	addFirst()	offerFirst() – false, wenn das Deque voll ist
Enqueue at back	addLast()	offerLast() – false, wenn das Deque voll ist
Dequeue at front	removeFirst()	pollFirst() – null, wenn das Deque leer ist
Dequeue at back	removeLast()	pollLast() – null, wenn das Deque leer ist
Peek at front	getFirst()	peekFirst() – null, wenn das Deque leer ist
Peek at back	getLast()	peekLast() – null, wenn das Deque leer ist

addFirst() und addLast() werfen eine IllegalStateException, die übrigen vier Methoden der mittleren Spalte eine NoSuchElementException. Von den Deque-Implementierungen des JDK kann übrigens nur LinkedBlockingDeque eine Kapazitätsgrenze haben – alle anderen sind nie voll.

Varianten des Deques

Wie die Queue gibt es auch das Deque in mehreren Abwandlungen:

• Bounded und Blocking Deque: Ein bounded Deque hat eine feste Kapazität. Ein blocking Deque lässt den aufrufenden Thread warten, bis ein Element verfügbar ist (beim Entnehmen) bzw. bis Platz frei ist (beim Einfügen). Das JDK bietet dafür das BlockingDeque-Interface mit der Implementierung LinkedBlockingDeque an.
• Threadsicheres, nicht blockierendes Deque: Mehrere Threads dürfen gleichzeitig an beiden Seiten einfügen und entnehmen. Anders als beim blocking Deque wartet dabei kein Thread: Aus einem leeren Deque liefert pollFirst() sofort null. Das JDK bietet dafür die Klasse ConcurrentLinkedDeque an.
• Input-restricted und Output-restricted Deque: Beim ersten ist das Einfügen nur an einer Seite erlaubt, beim zweiten das Entnehmen. Diese beiden Varianten stammen aus der Lehrbuch-Theorie; das JDK hat keine eigenen Klassen dafür.

Anwendungsgebiete für Deques

Das klassische Anwendungsgebiet für Deques ist eine Undo-Liste. Jeder ausgeführte Bearbeitungsschritt wird auf das Deque gelegt. Beim Aufruf der „Undo“-Funktion wird die zuletzt auf das Deque gelegte Bearbeitung entnommen und wieder rückgängig gemacht.

Bis hierhin ist das ein klassisches LIFO-Prinzip, könnte also auch mit einem Stack realisiert werden.

Aus Speichergründen sollten wir die Undo-Historie allerdings limitieren, z. B. auf 100 Einträge. Bei Verwendung eines Stacks würden die ältesten Elemente am Boden des Stacks liegen und könnten dort nicht entfernt werden. Bei einem Deque stellt das jedoch kein Problem dar, da Elemente an beiden Seiten entnommen werden können.

Die folgende Grafik zeigt eine Undo-Historie, die auf fünf Einträge begrenzt ist. Die Zahlen nummerieren die Bearbeitungsschritte; die Historie war mit den Schritten 1 bis 5 voll. Für den neuen Schritt 6 entnimmt die Dequeue-Operation am Ende den ältesten Schritt 1, und die Enqueue-Operation legt Schritt 6 am Kopf ab:

Die „Undo“-Funktion entnimmt den jüngsten Schritt am Kopf – an derselben Seite, an der die Enqueue-Operation ihn abgelegt hat.

Auch das JDK selbst setzt Deques ein: Jeder Worker-Thread eines ForkJoinPool – auf dem z. B. parallele Streams laufen – verwaltet seine Aufgaben in einem eigenen Deque. Neue Teilaufgaben legt er an einer Seite ab und nimmt sie im Standardmodus dort auch wieder heraus, also nach dem LIFO-Prinzip.

Hat ein Thread keine Aufgaben mehr, holt er sich welche aus dem Deque eines anderen Threads – und zwar von dessen anderer Seite, nach dem FIFO-Prinzip. Dieses Verfahren heißt Work Stealing. Der Thread, dem das Deque gehört, und der Thread, der Aufgaben daraus holt, arbeiten so an verschiedenen Seiten.

Zeitkomplexität der Deque-Operationen

Eine Einführung in das Thema Zeitkomplexität findest du im Artikel „O-Notation und Zeitkomplexität – anschaulich erklärt“.

Deques werden in der Regel mit Arrays oder verketteten Listen implementiert. Bei beiden Varianten ist der Aufwand für alle sechs Operationen jeweils konstant, d. h., er ändert sich nicht mit der Länge des Deques.

Die Zeitkomplexität dieser Operationen lautet also: O(1).

Eine Ausnahme gibt es beim Array: Ist es voll und soll das Deque 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 (im ArrayDeque 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).

Ausblick

Im nächsten Teil des Tutorials lernst du das Deque-Interface von Java im Detail kennen: seine Methoden, die Klassenhierarchie und welche der JDK-Implementierungen du wann einsetzt. Wie du ein Deque selbst mit einem Array implementierst, zeige ich dir später in dieser Serie.