Using Deque in Java

Home › Blog › Using Deque in Java
Using Deque in Java

Using Deque in Java

By SFG Contributor Java
0 Comments

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
  • ConcurrentLinkedDeque
  • LinkedBlockingDeque

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 does not support concurrent access by multiple threads.
  • Null elements are prohibited in the ArrayDeque.
  • ArrayDeque class is likely to be faster than Stack when used as a stack.
  • ArrayDeque class is likely to be faster than LinkedList when used as a queue.

ArrayDeque Constructors

There are three constructors to instantiate an instance of ArrayDeque

  • ArrayDeque()
  • ArrayDeque(int numOfElements)
  • 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.
constructors

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.

arrayDeque add methods

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.
remove methods

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.

access elements

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 Constructors

There are two constructors to instantiate a ConcurrentLinkedDeque which are:

  • ConcurrentLinkedDeque()
  • 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.
constructor-example

Operations of 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.
addition

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.

removing elements

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

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 Constructors

There are three constructors to create an instance of LinkedBlockingDeque.

  • LinkedBlockingDeque()
  • LinkedBlockingDeque(int capacity)
  • 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.
creation of lbd

Operations of 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.
adding elements

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.

4

About SFG Contributor

Staff writer account for Spring Framework Guru

    You May Also Like

    Leave a Reply

    Your email address will not be published. Required fields are marked *

    This site uses Akismet to reduce spam. Learn how your comment data is processed.