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.

Benedikt

It provides more baked-in methods, or rather "a more complete and consistent set" of them, which will reduce the amount of code you have to write if you take advantage of them? – Legate

baddotrobot.com/blog/2013/01/10/stack-vs-deque – Atomic

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

Blondellblondelle

the javadoc of ArrayDeque says " This class is likely to be faster than Stack when used as a stack, and faster than LinkedList when used as a queue." ..How do I specify whether I intend to use this as a stack or as a queue? – Benedikt

@Geek: You don't. The point is that if you want queuing behaviour, you could use LinkedList, but ArrayDequeue will (often) be faster. If you want stack behaviour, you could use Stack but ArrayDeque will (often) be faster. – Blondellblondelle

Isn't it less sensible in terms of abstraction though? I mean, neither solution is really good in terms of abstraction, because Stack has the rep exposure problem, but if I want a stack data structure I would like to be able to call methods like push, pop, and peek, and not things having to do with the other end of the stack. – Disencumber

@PeteyPabPro: I don't see it as being a problem, to be honest. It may not be absolutely ideal, but it's not a problem. – Blondellblondelle

@JonSkeet also Stack's iterator is wrong, because it iterates from bottom to top instead of top to bottom. #16993258 – Chacha

@PeteyPabPro: You are right. Using Dequeue as stack still allows non-LIFO usage as the inherited Vector methods of Stack. An explanation of the problem and a solution (with encapsulation) can be found here: baddotrobot.com/blog/2013/01/10/stack-vs-deque – Radiotransparent

I couldn't find any Java documentation for ArrayDequeue. Not sure this is an actual class... Never heard of it, and google doesn't product anything. – Millard

@SteveLivingston: I made a typo on the name in the first part of my comment (but not the second) - it's ArrayDeque, not ArrayDequeue. It definitely exists though: docs.oracle.com/javase/10/docs/api/java/util/ArrayDeque.html – Blondellblondelle

haha okay. I'm very familiar with ArrayDeque. I had just never heard of the "dequeue" version and the structure of your comment made me believe there was two different classes haha. Thanks for clarifying. I thought was going crazy :-p @JonSkeet – Millard

When I used this solution, I encountered this error: Type mismatch: inferred type is ArrayDeque<Int> but Deque<Int> was expected – Blanche

@roghayehhosseini: It's hard to know what you're doing wrong, but the code in the answer definitely compiles. I suggest you ask a new question with a minimal reproducible example. – Blondellblondelle

@JonSkeet After a lot of searching I couldn't figure out why this was happening. finally i use: var stack: Deque<Int> = LinkedList() – Blanche

@roghayehhosseini: Are you not actually using Java? Is this Kotlin, for example? If so, that would explain things - you shouldn't expect the exact rules of one language to apply in another. When you're saying that code in a Java answer doesn't work for you, please specify if you're not actually using Java. (And if you are using Java, var stack: Deque<Int> = LinkedList() presumably isn't your actual code...) – Blondellblondelle

@JonSkeet I use kotlin. but when i convert your code to kotlin i encountered error! – Blanche

@roghayehhosseini: Then a) it would have been worth saying that before; b) it makes it even more suitable for being in a new question rather than as a comment to an answer that's nearly 8 years old... especially as the implication is that the answer is broken, which it isn't. – Blondellblondelle

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.

Foiled

This is a nice, niche explanation. A brief Interview material no doubt. Thanks. – Ho

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]

Mandrake

Good one thanks for the example. – Ho

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

Disappear

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.

Tusche

grep "Apart from this" – Idaline

Answer 6

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);

Weeping

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 synchronized therefore 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.

Patrology

Answer 8

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.

Maturation

grep "Apart from this" – Idaline