Java Deque vs. Stack: Why Deque Is the Better Choice

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 and removed at both ends:

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

The Stack class is thread-safe: pop(), peek(), and search() are marked with the synchronized keyword; push() and empty() call synchronized methods of Vector.

This protects every single method call, but not a sequence of calls: Between empty() and pop(), another thread can remove the last element – pop() then throws an EmptyStackException.

For a single-threaded application, this synchronization is superfluous. What it costs depends on the Java version and the JIT compiler.

Up to Java 14, biased locking optimized the case where the same thread repeatedly calls synchronized methods of the same object. It has been disabled by default since Java 15 and was removed from the JVM in Java 18 (JDK-8256425).

What remains is so-called lock coarsening: The JIT compiler can merge several consecutive calls to synchronized methods of the same object so that the lock is acquired and released only once.

If multiple threads access the stack, 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 deque 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 ultimately 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);
}

The output of this sample code is:

Stack: 
A
B
C

Deque: 
C
B
A

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, you call the reversed() method, available since Java 21. It returns a reversed view of the deque, not a copy.

You iterate over this view with a for-each loop:

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

The loop prints the elements in insertion order:

A
B
C

Before Java 21, you had to retrieve an iterator via descendingIterator():

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

Empty Stack and null Elements

Stack and Deque also behave differently when the stack is empty:

• With Stack, peek() throws an EmptyStackException. With a Deque, peek() returns null.
• With Stack, pop() also throws an EmptyStackException; with a Deque, it throws a NoSuchElementException.

Stack allows null elements. ArrayDeque, LinkedBlockingDeque, and ConcurrentLinkedDeque, on the other hand, throw a NullPointerException on push(null), because with a Deque, null is the return value for “empty”. Of the deque implementations, only LinkedList accepts null elements.

You can find all differences between Stack and ArrayDeque as a table in the Stack Alternatives section of the article about the Stack class.

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 retainAll() 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.

Since Java 21, Stack also has methods such as addFirst() and removeFirst() via the SequencedCollection interface; they operate on the bottom of the stack.

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 section “Stack Interface” of the article on the Stack class.

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 see only one point in which the Deque interface is more consistent than Stack: The iterator of a deque runs in removal order, while the iterator of Stack runs against it (see section “Iteration” above).

What both have, on the other hand, are methods that a stack or deque data structure should not have (see section “Violation of the Interface Segregation Principle” above).

Nevertheless, 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:

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

The Javadoc of ArrayDeque notes: “This class is likely to be faster than Stack when used as a stack”.

It would be nicer if the JDK 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.

I recommend ArrayDeque if only one thread accesses the stack, and ConcurrentLinkedDeque if several do.

The section “Deque Implementations in Java: Which One to Use?” explains when one of the other deque implementations is the better fit.