Table of Contents
Overview
In this post, we are going to learn about Deque in Java (pronounced deck) and its implementation.
It may surprise you to see LinkedList is a queue. LinkedList is a queue and also a list. That means it has all the characteristics of a List and also a Deque.
What is a Deque in Java?
Deque is short for Double Ended queue. As you recall from the previous post, you can only add an element to the end of a queue and remove an element from its head. However, with Deque, that’s no longer true. You can add and remove from the head and tail of a queue.
That’s why it’s called a double-ended queue.
Let’s take a look at the Queue family in Java again:
As you can see from the diagram, there are four concrete implementations of the Deque interface, two of them are thread-safe and two aren’t.
Let’s discover the non-thread-safe options first.
ArrayDeque and LinkedList
Both ArrayDeque and LinkedList implement the Deque interface so they have all capabilities of a Deque. However, since LinkedList also inherits from the List interface, it has additional capabilities of a List that ArrayDeque doesn’t have.
Here are some notable differences between ArrayDeque and LinkedList
| ArrayDeque | LinkedList | |
| Can add null element? | NO | YES |
| Keep track of head and tail elements | Use head and tail index (int) | Use first node and last node (object) |
| Internal data structure | Use an array of Object to store the elements | Use a doubly linked list |
Let’s take a look at the functionalities of the Deque interface by writing some code.
package com.datmt.java_core.collection.queue;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;
import java.util.NoSuchElementException;
import java.util.Queue;
public class DeQueueOperation {
public static void main(String[] args) {
Deque<String> people = new ArrayDeque<>();
//Adding elements
people.add("Jane");
people.offer("Jake");
people.addFirst("Derek");
people.addLast("Bob");
System.out.println("people are: " + people); //people are: [Derek, Jane, Jake, Bob]
//Getting elements from the tail of the queue
System.out.println(people.peekLast());//Get the last element, not removing
System.out.println(people.pollLast());//Get the last element, removing
System.out.println("people are: " + people); //people are: [Derek, Jane, Jake]
//Getting elements from the head of the queue
System.out.println(people.getFirst()); //get the first element, not removing but throws exception on empty queue
System.out.println(people.peekFirst()); //same as get first, but not throwing an exception
System.out.println(people.removeFirst()); //get the first element and remove it
System.out.println("people are: " + people); //people are: [Jane, Jake]
}
}
Here is the output of the running code:
In addition to the standard add/remove methods, you can also remove the first/last occurrence of an element in a Deque:
private static void removeOccurrence() {
Deque<String> people = new ArrayDeque<>();
//Adding elements
people.add("Jane");
people.offer("Jake");
System.out.println("people are: " + people); //people are: [Jane, Jake]
//Add element to the beginning and end of the queue
people.addFirst("Jim");
people.addLast("Jim");
//Remove first, last occurrence of an element
System.out.println("people are: " + people); //people are: [Jim, Jane, Jake, Jim]
System.out.println(people.removeFirstOccurrence("Jim"));
System.out.println("people are: " + people); //people are: [Jane, Jake, Jim]
System.out.println(people.removeLastOccurrence("Jim"));
System.out.println("people are: " + people); //people are: [Jane, Jake]
}Here is the output of that code snippet:
As you can see, the removeFirstOccurence and removeLastOccurence methods return boolean values. Internally, they do equals operation on the queue and do the removal on that element. Due to the difference between the internal data structure of ArrayDeque and LinkedList (array vs doubly linked list), the performance would be different.
Using Deque in Concurrent programming
If you are using a Deque in concurrent programming, LinkedList and ArrayDeque are not safe choices. Instead, you would need concurrent-friendly implementation of Deque.
First, let’s consider an example where we use ArrayDeque in concurrent code:
private static void nonSafeDequeOperations() throws InterruptedException {
Deque<Integer> numberQueue = new ArrayDeque<>();
for (int i =0 ; i < 20; i++) {
numberQueue.offer(i);
}
//Do some concurrent removing
ExecutorService service = Executors.newFixedThreadPool(10);
for (int i = 0; i < 10; i++)
service.submit(() -> System.out.println("Taking element: " + numberQueue.remove()));
service.shutdown();
service.awaitTermination(10, TimeUnit.SECONDS);
System.out.println("Number now: " + numberQueue);
}When writing code like this, you possibly expect to have the first 10 elements of the queue removed. However, this is not the case when you use ArrayDeque.
Here is one possible output of the code:
Here is another:
What should you do? You use a thread-safe deque instead.
There are quite some ways to mitigate this situation, the below code is one:
private static void safeDequeOperations() throws InterruptedException {
Deque<Integer> numberQueue = new ConcurrentLinkedDeque<>();
for (int i =0 ; i < 20; i++) {
numberQueue.offer(i);
}
//Do some concurrent removing
ExecutorService service = Executors.newFixedThreadPool(10);
for (int i = 0; i < 10; i++)
service.submit(() -> System.out.println("Taking element: " + numberQueue.remove()));
service.shutdown();
service.awaitTermination(10, TimeUnit.SECONDS);
System.out.println("Number now: " + numberQueue);
}Here are some possible outputs:
As you can see, while the logs “Taking element:…” are in different order between different runs, the final queue stays the same and this is expected. We cannot know for sure which thread will run first but the queue at the end always has the first 10 elements removed.
In the example above, instead of using ConcurrentLinkedDeque, I can use LinkedBlockingDeque to produce the same result.
Using Deque as Stack
Stack is a last in – first out data structure (LIFO) while a queue is a (FIFO) data structure. Why can we use Deque as Stack?
Well, it turned out that since we can add and remove elements at both ends of a Deque, it’s a perfect candidate to implement a stack.
Using offer/addLast and removeLast
You can use offer, addLast to add elements to the end of a queue and use removeLast to remove from the end.
private static void dequeAsStack() {
Deque<String> stack = new ArrayDeque<>();
stack.addLast("Jake");
stack.offer("Jim");
System.out.println(stack.removeLast());//Jim
System.out.println(stack.removeLast());//Jake
}Using addFirst and removeFirst
In addition to the implementation above, you can use addFirst and removeFirst to achieve the functionality of a Stack:
private static void dequeAsStackUsingRemoveFirst() {
Deque<String> stack = new ArrayDeque<>();
stack.addFirst("Jake");
stack.addFirst("Jim");
System.out.println(stack.removeFirst());//Jim
System.out.println(stack.removeFirst());//Jake
}
Conclusion
In this post, we’ve learned how to use Deque in normal and concurrent contexts. Deque is a powerful kind of queue since we can add and remove elements and both ends. When needed, we can use deque as a stack. Actually, it is the recommended implementation of stack according to the Java documentation.
I build softwares that solve problems. I also love writing/documenting things I learn/want to learn.