Java Deque vs. Stack

In this article, you will learn:

• What are the differences between the deque and stack data structures?
• How do the Java interfaces/classes Deque and Stack differ?
• Why should we use Deque instead of Stack?

Let's take a look at the data structures first.

Difference between Deque and Stack

A stack is a data structure that works according to the LIFO principle: Elements that are placed on the stack last are taken out first – and vice versa:

For more details, see the main article about the stack data structure.

A deque (pronounced "deck"), on the other hand, is a data structure where elements can be inserted into and removed from two sides:

For details, see the main article about the deque data structure.

A deque can be used as a stack by inserting and removing elements on the same side.

Difference between Java Stack and Deque

This section is about the differences between the Java interface java.util.Deque and the class java.util.Stack.

Class vs. Interface

Stack is a class (→ all details about the Stack class), so it is a concrete implementation of the stack data type.

Deque, on the other hand, is an interface (→ all details about the Deque interface) and has several implementations with different characteristics. Therefore, you can choose a suitable deque implementation based on your requirements.

Thread Safety

In the Stack class, all methods are marked with the synchronized keyword. Therefore, you can safely use Stack in a multithreaded application.

For a single-threaded application, however, this synchronization is superfluous and would hurt performance. Furthermore, synchronization by pessimistic locking is only useful in situations with many access conflicts ("thread contention"). Otherwise, optimistic locking makes more sense.

The JDK offers, on the one hand, non-thread-safe implementations that work without locks (ArrayDeque and LinkedList) – and, on the other hand, thread-safe implementations that use a pessimistic lock (LinkedBlockingDeque) or optimistic locking (ConcurrentLinkedDeque).

Iteration

Since Stack and Deque are collections, they eventually implement the Iterable interface so that we can conveniently iterate over the elements they contain.

However, the order in which the Stack and Deque iterators operate differs, as the following example shows:

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 language: Java (java)

The output of this sample code is:

Stack: 
A
B
C

Deque: 
C
B
ACode language: plaintext (plaintext)

Stack's iterator iterates over the elements from bottom to top, that is, in insertion order. Deque's iterator, on the other hand, iterates from top to bottom, i.e., in removal order.

To iterate over a deque in insertion order, we can retrieve a corresponding iterator via the descendingIterator() method:

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

Violation of the Interface Segregation Principle

Both Stack and Deque offer far more methods than these data structures should offer and thus violate the interface segregation principle.

Both inherit methods like remove(), removeIf(), removeAll(), and ratainAll() from Collection. These methods can be used to remove elements from the middle of the stack or deque.

Stack also provides an insertElementAt() method to insert an element at an arbitrary position.

Deque provides the methods removeFirstOccurrence() and removeLastOccurrence(), which can also be used to remove elements that are not at the head or tail of the deque.

You can find out what a stack interface should look like in the article "Implementing a Stack in Java".

You can read what a deque interface should look like in "Implementing a Deque Using an Array".

Why We Should Use Deque Instead of Stack

When the Deque interface was introduced in Java 6, the Stack class was annotated with the following:

"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."

I don't see that the Deque interface is more consistent than Stack. Both interfaces have numerous methods that a stack or deque data structure should not have (see section "Violation of the Interface Segregation Principle" above).

However, I agree that we should use Deque from now on. Deque is an interface and provides multiple implementations with different characteristics (see "Thread Safety" section above), whereas, with Stack, we are locked into one implementation.

For example, if we access our stack from only one thread, Stack's synchronization is unnecessary, and we should instead use ArrayDeque.

However, it would be nicer if the Java developers had additionally introduced a Stack interface.

Summary

This article taught you the differences between the stack and deque data structures and their corresponding Java classes and interfaces. You also learned why you should no longer use Java's Stack class. You can find the appropriate deque implementation for your use case in the article "Java Deque Implementations – Which One to Use?".

If you still have questions, please ask them via the comment function. Do you want to be informed about new tutorials and articles? Then click here to sign up for the HappyCoders.eu newsletter.