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.

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

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

Solution 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]

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

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

View more solutions

Comments

[Admin]

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?

[Free-Minded]

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

[Geek]

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?

[Jon Skeet]

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

[PeteyPabPro]

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.

[Jon Skeet]

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

[Pavel]

@JonSkeet also Stack's iterator is wrong, because it iterates from bottom to top instead of top to bottom. stackoverflow.com/questions/16992758/…

[rics]

@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

[Stevers]

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.

[Jon Skeet]

@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

[Stevers]

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

[roghayeh hosseini]

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

[Jon Skeet]

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

[roghayeh hosseini]

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

[Jon Skeet]

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

[roghayeh hosseini]

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

[Jon Skeet]

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

[Pacerier]

grep "Apart from this"

[Pacerier]

grep "Apart from this"

[sud007]

Good one thanks for the example.

[sud007]

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