Java Deque vs. Stack: Warum Deque die bessere Wahl ist

In diesem Artikel erfährst du:

• Was sind die Unterschiede zwischen den Datenstrukturen Deque und Stack?
• Wie unterscheiden sich die Java-Interfaces bzw. Klassen Deque und Stack?
• Warum sollten wir Deque statt Stack verwenden?

Schauen wir uns zunächst die Datenstrukturen an.

Unterschied zwischen Deque und Stack

Ein Stack ist eine Datenstruktur, die nach dem LIFO-Prinzip arbeitet: Elemente, die zuletzt auf den Stack gelegt werden, werden als Erstes wieder entnommen – und umgekehrt:

Weitere Details findest du im Hauptartikel über die Stack-Datenstruktur.

Ein Deque (ausgesprochen „Deck“) hingegen ist eine Datenstruktur, bei der Elemente an beiden Seiten eingefügt und entnommen werden können:

Details findest du im Hauptartikel über die Deque-Datenstruktur.

Ein Deque kann als Stack eingesetzt werden, indem Elemente an derselben Seite eingefügt und wieder entnommen werden.

Unterschied zwischen Java Stack und Deque

In diesem Abschnitt geht es um die Unterschiede zwischen dem Java-Interface java.util.Deque und der Klasse java.util.Stack.

Klasse vs. Interface

Stack ist eine Klasse (→ alle Details über die Stack-Klasse), also eine konkrete Implementierung des Stack-Datentyps.

Deque hingegen ist ein Interface (→ alle Details über das Deque-Interface) und hat mehrere Implementierungen mit unterschiedlichen Eigenschaften. Du kannst also – basierend auf deinen Anforderungen – eine geeignete Deque-Implementierung auswählen.

Thread-Sicherheit

Die Klasse Stack ist threadsicher: pop(), peek() und search() sind mit dem synchronized-Keyword versehen, push() und empty() rufen synchronisierte Methoden von Vector auf.

Geschützt ist damit jeder einzelne Methodenaufruf, nicht aber eine Folge von Aufrufen: Zwischen empty() und pop() kann ein anderer Thread das letzte Element entnehmen – pop() wirft dann eine EmptyStackException.

Für eine single-threaded Anwendung ist diese Synchronisation überflüssig. Was sie kostet, hängt von der Java-Version und vom JIT-Compiler ab.

Bis Java 14 hat Biased Locking den Fall optimiert, dass immer wieder derselbe Thread synchronisierte Methoden desselben Objekts aufruft. Seit Java 15 ist Biased Locking standardmäßig deaktiviert, seit Java 18 ist es aus der JVM entfernt (JDK-8256425).

Geblieben ist das sogenannte Lock Coarsening: Der JIT-Compiler kann mehrere aufeinanderfolgende Aufrufe synchronisierter Methoden desselben Objekts zusammenfassen, so dass das Lock nur einmal erworben und wieder freigegeben wird.

Greifen mehrere Threads auf den Stack zu, ist die Synchronisation durch pessimistische Locks nur in Situationen mit einer hohen Anzahl an Zugriffskonflikten („thread contention“) sinnvoll. Andernfalls ist optimistisches Locking sinnvoller.

Das JDK bietet zum einen nicht-threadsichere Deque-Implementierungen, die ohne Locks arbeiten (ArrayDeque und LinkedList) – und zum anderen threadsichere Implementierungen, die ein pessimistisches Lock (LinkedBlockingDeque) oder optimistisches Locking (ConcurrentLinkedDeque) verwenden.

Iteration

Da Stack und Deque Collections sind, implementieren sie letztendlich das Iterable-Interface, so dass wir komfortabel über die enthaltenen Elemente iterieren können.

Allerdings unterscheidet sich die Reihenfolge, in der die Iteratoren von Stack und Deque arbeiten, wie das folgende Beispiel zeigt:

Stack<String> stack = new Stack<>();
stack.push("A");
stack.push("B");
stack.push("C");

System.out.println("Stack: ");
for (String s : stack) {
  System.out.println(s);
}

Deque<String> deque = new ArrayDeque<>();
deque.push("A");
deque.push("B");
deque.push("C");

System.out.println("\nDeque: ");
for (String s : deque) {
  System.out.println(s);
}

Die Ausgabe dieses Beispiel-Codes lautet:

Stack: 
A
B
C

Deque: 
C
B
A

Der Iterator von Stack iteriert über die Elemente von unten nach oben, also in Einfügereihenfolge. Der Iterator von Deque hingegen iteriert von oben nach unten, also in Entnahmereihenfolge.

Um über ein Deque in Einfügereihenfolge zu iterieren, rufst du seit Java 21 die Methode reversed() auf. Sie gibt eine umgekehrte Sicht auf das Deque zurück, keine Kopie.

Über diese Sicht iterierst du mit einer for-each-Schleife:

for (String s : deque.reversed()) {
  System.out.println(s);
}

Die Schleife gibt die Elemente in Einfügereihenfolge aus:

A
B
C

Vor Java 21 musstest du dafür mit descendingIterator() einen Iterator abrufen:

for (Iterator<String> iterator = deque.descendingIterator(); iterator.hasNext(); ) {
  String s = iterator.next();
  System.out.println(s);
}

Leerer Stack und null-Elemente

Auch bei einem leeren Stack verhalten sich Stack und Deque unterschiedlich:

• peek() wirft bei Stack eine EmptyStackException. Bei einem Deque gibt peek() null zurück.
• pop() wirft bei Stack ebenfalls eine EmptyStackException, bei einem Deque hingegen eine NoSuchElementException.

Stack erlaubt null-Elemente. ArrayDeque, LinkedBlockingDeque und ConcurrentLinkedDeque hingegen werfen bei push(null) eine NullPointerException, denn null ist bei einem Deque der Rückgabewert für „leer“. Von den Deque-Implementierungen nimmt nur LinkedList null-Elemente an.

Alle Unterschiede zwischen Stack und ArrayDeque findest du als Tabelle im Abschnitt Stack-Alternativen des Artikels über die Stack-Klasse.

Verletzung des Interface-Segregation-Prinzips

Sowohl Stack als auch Deque bieten weitaus mehr Methoden, als diese Datenstrukturen anbieten sollten, und verletzen damit das Interface-Segregation-Prinzip.

Beide erben Methoden wie remove(), removeIf(), removeAll() und retainAll() von Collection. Mit diesen Methoden können Elemente aus der Mitte des Stacks bzw. des Deques entfernt werden.

Stack bietet außerdem eine insertElementAt()-Methode, um ein Element an beliebiger Position des Stacks einzufügen.

Seit Java 21 hat Stack über das Interface SequencedCollection auch Methoden wie addFirst() und removeFirst(), die am Boden des Stacks arbeiten.

Deque bietet die Methoden removeFirstOccurrence() und removeLastOccurrence(), mit denen ebenfalls Elemente entnommen werden können, die nicht am Kopf bzw. Ende des Deques liegen.

Wie ein Stack-Interface aussehen sollte, erfährst du im Abschnitt „Stack-Interface“ des Artikels über die Stack-Klasse.

Wie ein Deque-Interface aussehen sollte, liest du in „Deque mit einem Array implementieren“.

Warum wir Deque statt Stack verwenden sollten

Als in Java 6 das Deque-Interface eingeführt wurde, wurde die Stack-Klasse mit folgendem Hinweis versehen:

„A more complete and consistent set of LIFO stack operations is provided by the Deque interface and its implementations, which should be used in preference to this class.“

Dass das Deque-Interface konsistenter ist als Stack, sehe ich nur in einem Punkt: Der Iterator eines Deques läuft in Entnahmereihenfolge, der Iterator von Stack läuft ihr entgegen (s. Abschnitt „Iteration“ oben).

Methoden, die eine Stack- bzw. eine Deque-Datenstruktur nicht haben sollte, haben hingegen beide (s. Abschnitt „Verletzung des Interface-Segregation-Prinzips“ oben).

Dennoch stimme ich zu, dass wir fortan Deque verwenden sollten. Deque ist ein Interface und bietet mehrere Implementierungen mit verschiedenen Eigenschaften (s. Abschnitt „Thread-Sicherheit“ oben), während wir bei Stack auf eine Implementierung festgelegt sind.

Wenn wir beispielsweise von nur einem Thread auf unseren Stack zugreifen, ist die Synchronisation von Stack überflüssig, und wir sollten lieber ein ArrayDeque einsetzen:

Deque<String> stack = new ArrayDeque<>();

Im Javadoc von ArrayDeque heißt es: „This class is likely to be faster than Stack when used as a stack“.

Schöner wäre es, wenn die JDK-Entwickler:innen zusätzlich ein Stack-Interface eingeführt hätten.

Zusammenfassung

In diesem Artikel hast du die Unterschiede zwischen den Datenstrukturen Stack und Deque sowie den entsprechenden Java-Klassen bzw. -Interfaces kennengelernt. Du hast außerdem erfahren, warum du Javas Stack-Klasse nicht mehr verwenden solltest.

Ich empfehle ArrayDeque, wenn nur ein Thread auf den Stack zugreift, und ConcurrentLinkedDeque, wenn es mehrere sind.

Wann sich eine der anderen Deque-Implementierungen eignet, liest du im Abschnitt „Deque-Implementierungen in Java: Welche einsetzen?“.