Why Use Deque Instead Of Stack

Use Deque instead of Stack?

When solving algorithm problems using Java, I used to use Deque instead of Stack. While searching online, I often came across posts that suggested using Deque instead of Stack class.

However, I think I was using it vaguely without thinking deeply about why I should use Deque. We took this opportunity to learn more about the differences between Stack and Deque.

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<Integer>();
stack.push(1);

Java official documentation talks about the Stack class as follows: It says to use the Deque interface and its implementations rather than the Stack class.

In this post, we will take a closer look at Queue, Stack, and Deque. Let’s find out what advantages Deque has over Stack.

Queue/Stack/Deque

###Queue

Queue is a data structure that has the characteristics of FIFO(First In First Out). Java provides the corresponding data type through the java.util. Queue<E> interface.

Provided method

	Throws exception	Returns special value
Insert	add(e)	offer(e)
Delete	remove()	poll()
View	element()	peek()

Queue provides two methods for data manipulation. Depending on which method you use, it is determined whether an error occurred or Special Value is returned when an exception occurs.

• offer method
• If insertion was successful, true is returned.
• If insertion is not done properly, false is returned.
• poll and peek methods
• If data does not exist, null is returned.

Usage example

Queue<Integer> queue = new LinkedList<>();
queue.offer(1);

Queue usually uses LinkedList as its implementation.

Stack

Stack is a data structure that has the characteristics of LIFO(Last In First Out). In Java, the corresponding data type is provided through the java.util. Stack<E> class. It is implemented by inheriting the Vector class.

Provided method

Usage example

Stack<Integer> stack = new Stack<>();

Stack is itself an implementation, so use it like this:

###DequeDeque is short for Double Ended Queue, commonly called a two-way queue. Java provides the corresponding data type through the java.util. Deque<E> interface. It is implemented by inheriting the Queue interface.

Provided method

Stack/Queue methods vs. Deque method

Deque inherits the Queue interface, so it provides all the methods of Queue. The table above compares the methods of Queue and the methods of Deque.

Deque also provides all of the methods of Stack. The table above compares the methods of Stack and the methods of Deque.

What happens when you call a Stack/Queue method

But then I suddenly became curious. How does Deque support the methods of Queue and Stack? So, I looked at the actual Java code using IntelliJ.

The ArrayDeque class, which is an implementation of Deque, provides Stack methods as follows. When you use a method in Stack, such as the push, pop, and peek methods, you delegate to calling the corresponding method in Deque. This also applies to the method of Queue.

Usage example

Deque<Integer> deque = new ArrayDeque<>();
deque.addFirst(1);

Queue<Integer> queue = new ArrayDeque<>();
queue.offer(1);

Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);

In the case of Queue, it is the parent interface of Deque, so the data type can be declared as Queue.

In conclusion, Deque can be accessed and used as a two-way queue, but You can also use it like Stack or Queue. This means that there will be no problem even if code that previously used Stack and Queue is changed to Deque.

The father and the son

As mentioned briefly earlier, the Stack class is implemented by inheriting the Vector class. The Vector class is a class that implements List and has been provided since Java 1.0. However, its use is currently not recommended due to performance issues. As a result, the use of the Stack class is also not recommended.

Why Vector is not recommended

Vector consists of synchronized methods, making it safe in a multi-threaded environment. However, even in a single-threaded environment, overhead for synchronization processing may occur, resulting in performance degradation. Therefore, in a single-threaded environment, using ArrayList has a performance advantage. Since Java 1.5, Collections.synchronizedList is provided, allowing synchronization even when using the ArrayList class. Therefore, it is recommended to use ArrayList regardless of the thread environment. In fact, most projects using Java today don’t use Vector, they use ArrayList.

Why using Stack is not recommended

As you can easily see from the table, the relationship between Stack and ArrayDeque is very similar to the relationship between Vector and ArrayList. In other words, the reason why Stack should not be used can be seen as the same as the reason why Vector should not be used.

However, Deque does not have a separate method for synchronization processing. For example, methods such as Collections.synchronizedDeque are not provided. So how can we use it safely in a multi-threaded environment?

class SyncStack<E> {
    private final Deque<E> stack = new ArrayDeque<>();

    public synchronized void push(E e) {
        stack.push(e);
    }
}

These issues can be resolved through external synchronization. If synchronization is performed externally as shown in the example above, Deque can be used safely even in a multi-threaded environment.

Conclusion

This was an opportunity to take a closer look at Java data structures. I decided to become a developer who can properly understand and use it rather than blindly using it because I was told to use it.

Summary- Stack is implemented by inheriting Vector.

• Vector is not recommended for use due to poor performance in a single-threaded environment.
• Therefore, it is best not to use Stack, which inherits Vector.
• ArrayDeque is an implementation of Deque and supports both methods of Stack and Queue.
• Performance improvement can be expected by using ArrayDeque instead of Stack.
• If you want to use thread-safe ArrayDeque, use external synchronization.

References

• Java official documentation - Stack
• Java Official Documentation - Vector
• Java official documentation - Deque
• Java official documentation - Collections.synchronizedList
• ArrayList vs Vector synchronization & performance difference comparison