Last Updated on September 10, 2021 by jt

A

Deque is a linear collection that supports element insertion and removal at both ends. The name deque is short for “double ended queue” and is usually pronounced “deck”.

The

Deque interface defines methods to access the elements at both ends of the deque. Methods are provided to insert, remove, and examine the element. Each of these methods exists in two forms: one throws an exception if the operation fails, the other returns a special value (either null or false, depending on the operation).

In this post, you”ll learn about all implementing classes of

Deque, their creation and methods supported by each of them.

Representation of a Deque

In

Deque the insertion and removal of elements can either be performed from the front or the rear. Thus, it does not follow FIFO rule (First In First Out).

Types of Deque

Input Restricted Deque

In this deque, input is restricted at a single end but allows deletion at both the ends.

Output Restricted Deque

In this deque, output is restricted at a single end but allows insertion at both the ends.

Implementing Classes of Deque Interface

• ArrayDeque
  ArrayDeque
• ConcurrentLinkedDeque
  ConcurrentLinkedDeque
• LinkedBlockingDeque
  LinkedBlockingDeque

ArrayDeque

ArrayDeque

It is a resizable-array implementation of the

Deque interface with no capacity restrictions.

Features of

ArrayDeque

• These are not thread-safe which means that in the absence of external synchronization,
  ArrayDeque
  ArrayDeque does not support concurrent access by multiple threads.
• Null elements are prohibited in the
  ArrayDeque
  ArrayDeque.
• ArrayDeque
  ArrayDeque class is likely to be faster than
  Stack
  Stack when used as a stack.
• ArrayDeque
  ArrayDeque class is likely to be faster than
  LinkedList
  LinkedList when used as a queue.

ArrayDeque

ArrayDeque Constructors

There are three constructors to instantiate an instance of

ArrayDeque

• ArrayDeque()
  ArrayDeque()
• ArrayDeque(int numOfElements)
  ArrayDeque(int numOfElements)
• ArrayDeque(Collection<? extends E> c)
  ArrayDeque(Collection<? extends E> c)

This is the code to understand the use of each one of the constructors.

ArrayDequeExampleDemo.java

package org.springframework.guru;

import java.util.ArrayDeque;
import java.util.Deque;

public class ArrayDequeExampleDemo {
    public static void main(String[] args) {
        Deque arrayDeque = new ArrayDeque<>();

        arrayDeque.add("first element");

        System.out.println(arrayDeque);

        Deque arrayDeque1 = new ArrayDeque(2);
        arrayDeque1.add("element one");
        arrayDeque1.add("element two");

        System.out.println(arrayDeque1);

        Deque arrayDeque2 = new ArrayDeque(arrayDeque1);
        System.out.println(arrayDeque2);
 }
}

In Line 8, the

ArrayDeque()constructor creates an empty array deque with a capacity to hold 16 elements.

Line 14 uses the

ArrayDeque(int numOfElements) which sets the deque to contain a specified number of elements, which in our case is 2.

The

ArrayDeque(Collection<? extends E> c) constructor in line 20, is used to create an ArrayDeque containing all the elements the same as that of the specified collection.

The output on running the code in IntelliJ is this.

ArrayDeque

ArrayDeque Operations

The various operations of add, remove, access and iterate elements in

ArrayDeque are explained below.

Adding elements
In order to add an element to the

ArrayDeque, we can use the methods add(), addFirst(), addLast(), offer(), offerFirst(), offerLast() methods.

This is the code to understand the use of various methods to insert elements.

ArrayDequeExampleDemo.java

package org.springframework.guru;

import java.util.ArrayDeque;
import java.util.Deque;

public class ArrayDequeExampleDemo {
    public static void main(String[] args) {
        Deque arrayDeque = new ArrayDeque<>();
        arrayDeque.add("first string using add");
        arrayDeque.addFirst("first string using addFirst");
        arrayDeque.addLast("last string using addLast");
        System.out.println(arrayDeque);
 }
}

The

add() and addFirst() method inserts element to the front.

The

addLast() in Line 11 adds the element at the tail or end.

The output of the preceding code is this.

Remove elements

In order to remove an element from a deque, there are various methods available. Since we can also remove from both the ends, the deque interface provides us with

removeFirst(), removeLast() methods. Apart from that, this interface also provides us with the poll(), pop(), pollFirst(), pollLast() methods where pop() is used to remove and return the head of the deque.

The code to remove elements using remove methods is this.

ArrayDequeExampleDemo.java

package org.springframework.guru;

import java.util.ArrayDeque;
import java.util.Deque;

public class ArrayDequeExampleDemo {
    public static void main(String[] args) {
        Deque arrayDeque = new ArrayDeque<>();
        arrayDeque.add("first string using add");
        arrayDeque.addFirst("first string using addFirst");
        arrayDeque.addLast("last string using addLast");
        arrayDeque.add("element 1");
        System.out.println(arrayDeque);

        System.out.println(arrayDeque.pop());
        System.out.println(arrayDeque.poll());
        System.out.println(arrayDeque.pollFirst());
        System.out.println(arrayDeque.pollLast());
        System.out.println(arrayDeque);
 }
}

Here is the output.

Access elements

After adding the elements, if we wish to access the elements, we can use inbuilt methods like

getFirst(), getLast(), peek(), peekFirst(), and peekLast().

Here is the code to access elements in an

ArrayDeque

ArrayDequeExampleDemo.java

package org.springframework.guru;

import java.util.ArrayDeque;
import java.util.Deque;

public class ArrayDequeExampleDemo {
    public static void main(String[] args) {
        Deque arrayDeque = new ArrayDeque<>();
         arrayDeque.add("one");
        arrayDeque.addFirst("two");
        arrayDeque.addLast("three");
        arrayDeque.add("four");
        System.out.println(arrayDeque);

        System.out.println(arrayDeque.getFirst());
        System.out.println(arrayDeque.getLast());
        System.out.println(arrayDeque.peek());
        System.out.println(arrayDeque.peekFirst());
        System.out.println(arrayDeque.peekLast());
 }
}

The methods to access elements are self-explanatory and you can see the output to have a better understanding.

The output on running the code in IntelliJ is this.

ConcurrentLinkedDeque

ConcurrentLinkedDeque

It is used to implement

Deque with the help of LinkedList concurrently. Insertion, removal, and access operations happen concurrently. They do not throw ConcurrentModificationException when you try to modify a Collection, and may proceed concurrently with other operations.

ConcurrentLinkedDeque

ConcurrentLinkedDeque Constructors

There are two constructors to instantiate a

ConcurrentLinkedDeque which are:

• ConcurrentLinkedDeque()
  ConcurrentLinkedDeque()
• ConcurrentLinkedDeque(Collection<E> c)
  ConcurrentLinkedDeque(Collection<E> c)

This is the code to explain the use of both the constructors to create a concurrent linked deque.

ConcurrentLinkedDequeExampleDemo.java

package org.springframework.guru;

import java.util.concurrent.ConcurrentLinkedDeque;

public class ConcurrentLinkedDequeExampleDemo {
   public static void main(String[] args) {
       ConcurrentLinkedDeque concurrentLinkedDeque = new ConcurrentLinkedDeque();

       concurrentLinkedDeque.add(100);
       concurrentLinkedDeque.addFirst(200);
       concurrentLinkedDeque.addFirst(300);
       concurrentLinkedDeque.add(400);
       concurrentLinkedDeque.addFirst(500);

       System.out.println(concurrentLinkedDeque);

       ConcurrentLinkedDeque concurrentLinkedDeque1 = new ConcurrentLinkedDeque(concurrentLinkedDeque);
       System.out.println(concurrentLinkedDeque1);
 }
}

In Line 7,

ConcurrentLinkedDeque() constructor constructs an empty deque.

And, in Line 17,

ConcurrentLinkedDeque(Collection<E> c)constructor constructs a deque with the elements of the Collection passed as the parameter.

The output on running the code in IntelliJ is this.

Operations of

ConcurrentLinkedDeque

ConcurrentLinkedDeque

The methods are provided to perform operations like insert, remove, access, and iterate the elements.

Adding Elements

To add an element or Collection of elements,

ConcurrentLinkedDeque provides methods like add(E e), addAll(Collection<? extends E> c), addFirst(E e), addLast(E e) methods.

The code to explain the preceded methods is this.

ConcurrentLinkedDequeExampleDemo.java

package org.springframework.guru;

import java.util.concurrent.ConcurrentLinkedDeque;

public class ConcurrentLinkedDequeExampleDemo {
   public static void main(String[] args) {
       ConcurrentLinkedDeque concurrentLinkedDeque = new ConcurrentLinkedDeque();

       concurrentLinkedDeque.add(70);
       concurrentLinkedDeque.add(50);
       concurrentLinkedDeque.add(90);
       concurrentLinkedDeque.add(10);

       System.out.println("ConcurrentLinkedDeque"+ concurrentLinkedDeque);

       concurrentLinkedDeque.addFirst(80);

       System.out.println("ConcurrentLinkedDeque after using addFirst"+ concurrentLinkedDeque);

       concurrentLinkedDeque.addLast(40);
       System.out.println("ConcurrentLinkedDeque after using addLast"+ concurrentLinkedDeque);

       ConcurrentLinkedDeque concurrentLinkedDeque1 = new ConcurrentLinkedDeque();
       concurrentLinkedDeque1.addAll(concurrentLinkedDeque);
       System.out.println("ConcurrentLinkedDeque after using addAll"+ concurrentLinkedDeque1);
 }
}

The

add() and addLast() methods in Line number 9 and 20 respectively adds elements to the tail.

The

addFirst() method in Line 16 adds element to the head.

In Line 24, the

addAll() method adds all the elements of the ConcurrentLinkedDeque to the instance of ConcurrentLinkedDeque1.

Note : The

addLast() is equivalent to add() method.

This is the output of the preceding code.

Remove Elements

To remove an element,

ConcurrentLinkedDeque provides methods like remove(), removeFirst(), removeLast() and remove(Object).

This is the code to demonstrate the use of different methods to remove elements from a

concurrentLinkedDeque.

ConcurrentLinkedDequeExampleDemo.java

package org.springframework.guru;

import java.util.concurrent.ConcurrentLinkedDeque;

public class ConcurrentLinkedDequeExampleDemo {
    public static void main(String[] args) {
        ConcurrentLinkedDeque concurrentLinkedDeque = new ConcurrentLinkedDeque();

        concurrentLinkedDeque.add(70);
        concurrentLinkedDeque.add(50);
        concurrentLinkedDeque.add(90);
        concurrentLinkedDeque.add(10);

        System.out.println("ConcurrentLinkedDeque"+ concurrentLinkedDeque);

        concurrentLinkedDeque.remove(10);
        System.out.println(concurrentLinkedDeque);
        concurrentLinkedDeque.remove();
        System.out.println(concurrentLinkedDeque);
        concurrentLinkedDeque.removeFirst();
        System.out.println(concurrentLinkedDeque);
        concurrentLinkedDeque.removeLast();
        System.out.println(concurrentLinkedDeque);   
 }
}

In Line 16, the

remove(Object) method removes 10 from the deque.

Line 18 uses the

remove() method to remove the first element in the ConcurrentLinkedDeque.

The

removeFirst() method in Line 20 is also used to remove the first element.

And, in Line 22,

removeLast() method removes the last element.

Note : The

remove() method is equivalent to removeFirst().

The output of the preceding code is this.

Iterating Elements

You can iterate the

ConcurrentLinkedDeque using iterator() or descendingIterator() methods.

Here is the code to explain the use of both the iterators.

ConcurrentLinkedDequeExampleDemo.java

package org.springframework.guru;

import java.util.Iterator;
import java.util.concurrent.ConcurrentLinkedDeque;

public class ConcurrentLinkedDequeExampleDemo {
   public static void main(String[] args) {
       ConcurrentLinkedDeque concurrentLinkedDeque = new ConcurrentLinkedDeque();

       concurrentLinkedDeque.add(70);
       concurrentLinkedDeque.add(50);
       concurrentLinkedDeque.add(90);
       concurrentLinkedDeque.add(10);

       System.out.println("ConcurrentLinkedDeque"+ concurrentLinkedDeque);

       Iterator iterator = concurrentLinkedDeque.iterator();
       System.out.println("The values of ConcurrentLinkedDeque are:");
       while(iterator.hasNext()) {
           System.out.println(iterator.next());
       }

       Iterator descendingIterator = concurrentLinkedDeque.descendingIterator();
       System.out.println("The values of ConcurrentLinkedDeque using descendingIterator are:");
       while(descendingIterator.hasNext()) {
           System.out.println(descendingIterator.next());
       }
   }
}

The only difference in using

descendingIterator()is it traverses through the values in reverse order unlike the Iterator().

Here is the output for the preceding code.

LinkedBlockingDeque

LinkedBlockingDeque

LinkedBlockingDeque is a deque that blocks a thread if that thread tries to take elements out of it while the Deque is empty. It implements the BlockingDeque and provides an optionally-bounded functionality based on linked nodes.

This optional capacity bound constructor argument serves as a way to prevent excessive expansion and memory wastage.

LinkedBlockingDeque

LinkedBlockingDeque Constructors

There are three constructors to create an instance of

LinkedBlockingDeque.

• LinkedBlockingDeque()
  LinkedBlockingDeque()
• LinkedBlockingDeque(int capacity)
  LinkedBlockingDeque(int capacity)
• LinkedBlockingDeque(Collection c)
  LinkedBlockingDeque(Collection c)

This is the code to demonstrate all three of the above-mentioned constructors.

LinkedBlockingDequeExampleDemo.java

package org.springframework.guru;

import java.util.concurrent.LinkedBlockingDeque;

public class LinkedBlockingDequeExampleDemo {
   public static void main(String[] args) throws InterruptedException {

       LinkedBlockingDeque linkedBlockingDeque = new LinkedBlockingDeque();
       linkedBlockingDeque.add(12345);
       linkedBlockingDeque.add(23456);


       LinkedBlockingDeque linkedBlockingDeque1 = new LinkedBlockingDeque(2);
       linkedBlockingDeque1.add(1234567);
       linkedBlockingDeque1.add(234567);
//        linkedBlockingDeque1.add(345678);

       LinkedBlockingDeque linkedBlockingDeque2 = new LinkedBlockingDeque(linkedBlockingDeque1);

       System.out.println(linkedBlockingDeque);
       System.out.println(linkedBlockingDeque1);
       System.out.println(linkedBlockingDeque2);
 }
}

In Line 8, the simple

LinkedBlockingDeque() constructor is used to create a LinkedBlockingDeque with a capacity of Integer.MAX_VALUE.

In Line 13, the capacity is fixed which is set to 2 here. And in Line 14, I am trying to add a third element to the deque, which will throw a

Deque Full exception for me.

In Line 18, the

LinkedBlockingDeque(Collection c) constructor creates a deque containing the elements of the given collection. Thus, it will contain all the elements of the specified collection which is here set to LinkedBlockingDeque1 instance.

The output on running the code in IntelliJ is this.

Operations of

LinkedBlockingDeque

LinkedBlockingDeque

This class and its iterator implement all of the optional methods of the Collection and Iterator interfaces.

There are various methods provided by

LinkedBlockingDeque to perform different operations of adding and removing the elements at both ends, accessing and iterating the elements.

Adding elements

There are methods like

add(), addFirst(), addLast(), and addAll() to add or insert methods at both ends.

This code demonstrates the use of the preceding methods.

LinkedBlockingDequeExampleDemo.java

package org.springframework.guru;

import java.util.concurrent.LinkedBlockingDeque;

public class LinkedBlockingDequeExampleDemo {
   public static void main(String[] args) throws InterruptedException {

       LinkedBlockingDeque linkedBlockingDeque = new LinkedBlockingDeque();

       linkedBlockingDeque.addFirst(1234567);
       linkedBlockingDeque.add(65404);
       linkedBlockingDeque.addLast(6754321);

       System.out.println("Linked Blocking Deque: " + linkedBlockingDeque);
  }
}

In Line 10, the

addFirst() method is used to insert integer to the head or start.

In Line 11, the

add() method inserts a number to the end of the deque.

And in Line 12,

addLast() method adds an integer to the tail or end.

Note : When both add() and addLast() methods are used, the element inserted through addLast() method gets inserted at the tail or end.

This is the output on running the code in IntelliJ.

Removing elements

There are methods like

remove(), removeFirst() and removeAll() to remove elements from a LinkedBlockingDeque.

Here is the code to understand the use of each one of them.

LinkedBlockingDequeExampleDemo.java

package org.springframework.guru;

import java.util.concurrent.LinkedBlockingDeque;

public class LinkedBlockingDequeExampleDemo {
    public static void main(String[] args) throws InterruptedException {

        LinkedBlockingDeque linkedBlockingDeque = new LinkedBlockingDeque();
        linkedBlockingDeque.addFirst(35658786);
        linkedBlockingDeque.addFirst(5006566);
        linkedBlockingDeque.addFirst(87654678);
        linkedBlockingDeque.add(1230089);
        linkedBlockingDeque.add(7654321);

        System.out.println("Linked Blocking Deque: " + linkedBlockingDeque);

        linkedBlockingDeque.remove();
        System.out.println("Linked Blocking Deque: " + linkedBlockingDeque);

        linkedBlockingDeque.removeFirst();
        System.out.println("Linked Blocking Deque: " + linkedBlockingDeque);

        linkedBlockingDeque.removeLast();
        System.out.println("Linked Blocking Deque: " + linkedBlockingDeque);

        }
    }

Line 17 uses the

remove() method to remove the first element.

In Line 20, the

removeFirst() method also removes the first element.

The

removeLast() method in Line 23, removes the last element of the deque.

Note : The

removeFirst() method is equivalent to remove().

This is the output on running the code in IntelliJ.

Iterating Elements

The

Iterator() method of LinkedBlockingDeque returns an iterator over the elements in deque in proper sequence. The elements will be returned in order from first (head) to last (tail).

The code to iterate over elements in a

LinkedBlockingDeque is this.

LinkedBlockingDequeExampleDemo.java

package org.springframework.guru;

import java.util.Iterator;
import java.util.concurrent.LinkedBlockingDeque;

public class LinkedBlockingDequeExampleDemo {
   public static void main(String[] args) throws InterruptedException {

       LinkedBlockingDeque linkedBlockingDeque = new LinkedBlockingDeque();

       linkedBlockingDeque.addFirst(1234567);
       linkedBlockingDeque.addFirst(35658786);
       linkedBlockingDeque.addFirst(5006566);
       linkedBlockingDeque.addFirst(87654678);

       Iterator iteratorVals = linkedBlockingDeque.iterator();

       System.out.println("The iterator values"
               + " of LinkedBlockingDeque are:");
       while (iteratorVals.hasNext()) {
           System.out.println(iteratorVals.next());
       }
   }
}

The output of the preceding code is this.

Summary

There are not many places where

Deque is used, but it finds its application in storing a web browser’s history or for storing a software application’s list of undo operations. It also helps in implementing both stacks and queues.
Moreover, we use LinkedBlockingDeque only when a single thread operates on our data and when we need blocking for our application. The ConcurrentLinkedDeque, on the other hand is used for a multi-threaded application and when we want that each one of our thread can access the data.