Deque Datenstruktur

In diesem Tutorial lernst du alles über die Datenstruktur "Deque" (ausgesprochen "Deck"):

• Was ist ein Deque?
• Welche Operationen bietet ein Deque an?
• Was sind die Anwendungsgebiete für Deques?
• Welche Deque-Interfaces und -Klassen liefert das JDK?
• Welches Deque-Implementierung sollte man für welche Einsatzzwecke verwenden?
• Wie implementiert man ein Deque selbst in Java?

Was ist ein Deque?

Ein Deque ist eine Liste 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 Seiten einfügen und wieder entnehmen.

Deque-Operationen

Die Operationen des Deques lauten analog zur Queue auf beiden Seiten "Enqueue" und "Dequeue":

• "Enqueue at front": Anhängen von Elementen an den Kopf des Deques
• "Enqueue at back": Anhängen von Elementen an das Ende des Deques
• "Dequeue at front": Entnehmen von Elementen vom Kopf des Deques
• "Dequeue at back": Entnehmen von Elementen vom Ende des Deques

(So wie bei der Queue werden auch beim Deque die entsprechenden Methoden der Java-Implementierungen anders bezeichnet; dazu mehr im nächsten Teil des Tutorials, "Java Deque-Interface".)

Anwendungsgebiete für Deqeues

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.

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. In beiden Fällen ist der Aufwand für das Einfügen und Entnehmen von Elementen auf beiden Seiten unabhängig von der Länge des Deques, also konstant.

Die Zeitkomplexität dieser Operationen beträgt somit: O(1)

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.