Java Deque vs. Stack

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 einmal 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 auf zwei 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

Bei der Klasse Stack sind alle Methoden mit dem synchronized-Keyword versehen. Du kannst Stack also problemlos in einer Multithreading-Anwendung einsetzen.

Für eine single-threaded Anwendung ist diese Synchronisation allerdings überflüssig und würde die Performance negativ beeinflussen. Außerdem 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 Implementierungen, die ohne Locks arbeiten (ArrayDeque und LinkedList) – und zum anderen threadsichere Implementierungen, die ein pessimistisches Lock (LinkedBlockingDeque) oder optimistischen 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);
}Code-Sprache: Java (java)

Die Ausgabe dieses Beispiel-Codes lautet:

Stack: 
A
B
C

Deque: 
C
B
ACode-Sprache: Klartext (plaintext)

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

Um über ein Deque in Einfügereihenfolge zu iterieren, kann über die Methode descendingIterator() ein entsprechender Iterator abgerufen werden:

for (Iterator<String> iterator = deque.descendingIterator(); iterator.hasNext(); ) {
  String s = iterator.next();
  // ... do something with s ...
}
Code-Sprache: Java (java)

Verletzung des Interface-Segregation-Prinzips

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

Beide erben Methoden wie remove(), removeIf(), removeAll() und ratainAll() 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.

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 eigentlich aussehen sollte, erfährst du im Artikel "Stack in Java implementieren".

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 nicht. Beide Interfaces haben zahlreiche Methoden, die eine Stack- bzw. eine Deque-Datenstruktur eigentlich nicht haben sollte (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.

Schöner wäre es allerdings, wenn die Java-Entwickler 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. Die geeignete Deque-Implementierung für deinen Use Case findest du im Artikel "Java Deque-Implementierungen – Welche einsetzen?"

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.