Guide to Deque in Java

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:

The java Queue family

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

ArrayDequeLinkedList
Can add null element?NOYES
Keep track of head and tail elementsUse head and tail index (int)Use first node and last node (object)
Internal data structureUse an array of Object to store the elementsUse 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.


Leave a Reply

Your email address will not be published.