Why Should I Use Deque Over Stack

Why should I use Deque over Stack?

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

Why should I use Deque over Stack and LinkedList over Queue?

Most of this question is specific to Java, but the part about using an array-list as a queue is more general.

In Java specifically, you should use an ArrayDeque or another deque implementation instead of the Stack class: according to the documentation,

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.

Another reason to prefer ArrayDeque for most use-cases is that Stack extends Vector, which is a synchronized implementation. Synchronization has a performance penalty, and is unnecessary when the stack will only be accessed from a single thread (i.e. almost all of the time).

An ArrayDeque is better than an ArrayList as a stack, because to simulate the pop method on an ArrayList you have to write s.remove(s.size() - 1), which is inconvenient and less clear.

The reason you should use a LinkedList "instead of" a Queue is because Queue is an interface, not a class, so you simply can't write new Queue<>() to create a queue; this will give a compilation error.

Note that it's still best to declare the type of your variable as Queue<...>.

The reason you shouldn't use an ArrayList as a queue is more general: it is a dynamic array data structure, so it only supports add and remove operations in O(1) time at one end. Adding or removing at the other end takes O(n) time. So it is unsuitable to use as a queue because a queue should enqueue and poll at different ends, and the operation at one end will be inefficient compared to other more suitable queue data structures.

Why to use a Deque instead of inbuilt Stack?

Java generics were added after initial implementations of collections; Stack is from Java 1.0 - and rather then break existing code when they added generics, it was decided to add classes that duplicate functionality (but provide a consistent API). That is why you should prefer a Deque - it provides an API consistent with all of the other Java Collections.

How is ArrayDeque faster than stack?

ArrayDeque is part of the Java Collections Framework and is not written to be inherently thread safe.

Stack, together with Vector and Hashtable came with Java 1.0 and were implemented with thread safe operations (because it seemed like a good idea at the time). Acquiring and releasing thread locks is relatively expensive time wise, hence those data structures will be much slower than their compatriots in the JCF.

Should I use a Python deque or list as a stack?

Your mileage may vary according to your application and precise use case, but in the general case, a list is well suited for a stack:

append is O(1)

pop() is O(1) - as long as you do not pop from an arbitrary position; pop() only from the end.

Deques are also O(1) for these operations, but require importing a module from the standard library, require 'O(n)' for random access. An argument could be made to prefer using vanilla lists though, unless for specific applicatins.

Correction:

from this post by Raymond Hettinger, a principal author of the C code for both list and deque, it appears that deques may perform slightly better than lists: The pop() operation of deques seem to have the advantage.

In [1]: from collections import deque

In [2]: s = list(range(1000))      # range(1000) if python 2

In [3]: d = deque(s)

In [4]: s_append, s_pop = s.append, s.pop

In [5]: d_append, d_pop = d.append, d.pop

In [6]: %timeit s_pop(); s_append(None)
10000000 loops, best of 3: 115 ns per loop

In [7]: %timeit d_pop(); d_append(None)
10000000 loops, best of 3: 70.5 ns per loop

the real differences between deques and list in terms of performance
are:
Deques have O(1) speed for appendleft() and popleft() while lists have
O(n) performance for insert(0, value) and pop(0).

List append
performance is hit and miss because it uses realloc() under the hood.
As a result, it tends to have over-optimistic timings in simple code
(because the realloc doesn't have to move data) and really slow
timings in real code (because fragmentation forces realloc to move all
the data). In contrast, deque append performance is consistent because
it never reallocs and never moves data.

Why do we need Deque data structures in the real world?

A nice application of the deque is storing a web browser's history. Recently visited URLs are added to the front of the deque, and the URL at the back of the deque is removed after some specified number of insertions at the front.
Another common application of the deque is storing a software application's list of undo operations.
One example where a deque can be used is the A-Steal job scheduling algorithm.[5] This algorithm implements task scheduling for several processors. A separate deque with threads to be executed is maintained for each processor. To execute the next thread, the processor gets the first element from the deque (using the "remove first element" deque operation). If the current thread forks, it is put back to the front of the deque ("insert element at front") and a new thread is executed. When one of the processors finishes execution of its own threads (i.e. its deque is empty), it can "steal" a thread from another processor: it gets the last element from the deque of another processor ("remove last element") and executes it. - Courtesy Wikipedia

Why are deques used as the underlying container for stacks by default, when vectors would do the trick?

I don't see any reason to prefer deques.

A reason to prefer deque that applies to the stack use case is that individual push back has worst case constant complexity compared to vector whose individual push back is linear in worst case (it has amortised constant complexity over multiple push backs). This was particularly significant prior to C++11 when reallocating vector had to copy the elements which could be very expensive. Consider case where the elements themselves are long strings.

Another reason to prefer deques is that they release memory as they shrink. Vectors don't. Hence, if you have a stack that temporarily grows large, then shrinks and remains small for the rest of the execution, then an underlying vector would be wasting a lot of memory.

Historically, when STL was designed and thus when the default was chosen, there used to also be issues with very large vectors because the size of the address space didn't exceed (significantly, or at all) the amount of memory (this was before 64 bit processing was common). The consequence of the limited address space was that memory fragmentation would make it expensive or impossible to allocate large contiguous blocks of memory that a large vector would require. Furthermore, the way that vector grows by deallocating old buffers is a behaviour that causes such fragmentation.