Why should I use Deque over Stack?

Question

I need a Stack data structure for my use case. I should be able to push items into the data structure and I only want to retrieve the last item from the Stack. The JavaDoc for Stack says :

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. For example:

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

I definitely do not want synchronized behavior here as I will be using this datastructure local to a method . Apart from this why should I prefer Deque over Stack here ?

P.S: The javadoc from Deque says :

Deques can also be used as LIFO (Last-In-First-Out) stacks. This interface should be used in preference to the legacy Stack class.

Answer 1

For one thing, it's more sensible in terms of inheritance. The fact that Stack extends Vector is really strange, in my view. Early in Java, inheritance was overused IMO - Properties being another example.

For me, the crucial word in the docs you quoted is consistent. Deque exposes a set of operations which is all about being able to fetch/add/remove items from the start or end of a collection, iterate etc - and that's it. There's deliberately no way to access an element by position, which Stack exposes because it's a subclass of Vector.

Oh, and also Stack has no interface, so if you know you need Stack operations you end up committing to a specific concrete class, which isn't usually a good idea.

Also as pointed out in the comments, Stack and Deque have reverse iteration orders:

Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);
stack.push(3);
System.out.println(new ArrayList<>(stack)); // prints 1, 2, 3


Deque<Integer> deque = new ArrayDeque<>();
deque.push(1);
deque.push(2);
deque.push(3);
System.out.println(new ArrayList<>(deque)); // prints 3, 2, 1

which is also explained in the JavaDocs for Deque.iterator():

Returns an iterator over the elements in this deque in proper sequence. The elements will be returned in order from first (head) to last (tail).

Answer 2

Here are a few reasons why Deque is better than Stack:

Object oriented design - Inheritance, abstraction, classes and interfaces: Stack is a class, Deque is an interface. Only one class can be extended, whereas any number of interfaces can be implemented by a single class in Java (multiple inheritance of type). Using the Deque interface removes the dependency on the concrete Stack class and its ancestors and gives you more flexibility, e.g. the freedom to extend a different class or swap out different implementations of Deque (like LinkedList, ArrayDeque).

Inconsistency: Stack extends the Vector class, which allows you to access element by index. This is inconsistent with what a Stack should actually do, which is why the Deque interface is preferred (it does not allow such operations)--its allowed operations are consistent with what a FIFO or LIFO data structure should allow.

Performance: The Vector class that Stack extends is basically the "thread-safe" version of an ArrayList. The synchronizations can potentially cause a significant performance hit to your application. Also, extending other classes with unneeded functionality (as mentioned in #2) bloat your objects, potentially costing a lot of extra memory and performance overhead.

Answer 3

One more reason to use Deque over Stack is Deque has the ability to use streams convert to list with keeping LIFO concept applied while Stack does not.

Stack<Integer> stack = new Stack<>();
Deque<Integer> deque = new ArrayDeque<>();

stack.push(1);//1 is the top
deque.push(1)//1 is the top
stack.push(2);//2 is the top
deque.push(2);//2 is the top

List<Integer> list1 = stack.stream().collect(Collectors.toList());//[1,2]

List<Integer> list2 = deque.stream().collect(Collectors.toList());//[2,1]

Answer 4

Here is my interpretation of inconsistency mentioned in the description of Stack class.

If you look at General-purpose Implementations here - you'll see there is a consistent approach to implementation of set, map and list.

• For set and map we have 2 standard implementations with hash maps and trees. The first one is most used and the second one is used when we need an ordered structure (and it also implements its own interface - SortedSet or SortedMap).

• We may use the preferred style of declaring like Set<String> set = new HashSet<String>();see reasons here.

But Stack class: 1) don't have its own interface; 2) is a subclass of Vector class - which is based on resizable array; so where is linked list implementation of stack?

In Deque interface we don't have such problems including two implementations (resizable array - ArrayDeque; linked list - LinkedList).

Answer 5

For me this specific point was missing: Stack is Threadsafe as it is derived from Vector, whereas the most deque implementations are not, and thus faster if you only use it in a single thread.

Answer 6

Performance might be a reason. An algorithm I used went down from 7.6 minutes to 1.5 minutes by just replacing Stack with Deque.

Answer 7

There are several reason that Deque is better than stack for implementation:

1. Deque is an interface and stack is a class: In class creation it is better to implement an interface than extend a class because after extending you cannot extend another class, you can only implement an interface in the other hand when you implement an interface you can extend a class and also implement another interfaces.

2. Synchronization: Because stack class is a subclass of the vector class which is asynchronized therefor stack is too But Deque is not. So if there is no need for synchronization then for better performance we should use Deque.

3. Deque‘s iterator works the way we expect for a stack: iteration in a stack is bottom to top (FIFO (First In First Out)). But iteration in a Deque is top to bottom (LIFO (Last In First Out)).

4. Stack isn't truly LIFO: We know that stack is a subclass of the vector class so we can access to elements by their indexes which is against LIFO contract.

Answer 8

If for some reason you want to switch from Stack to Deque, but want to preserve the same order when converting to an ArrayList, you can use Deque.descendingIterator().

However ArrayList does not have a constructor accepting an Iterator, so you might want to combine it with a library such as Guava (or Apache Commons):

Lists.newArrayList(deque.descendingIterator()) // Guava

Or Java 8:

List<Integer> list = new ArrayList<>();
deque.descendingIterator().forEachRemaining(list::add);