Using Deque in Java
0 CommentsA 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
ArrayDequeConcurrentLinkedDequeLinkedBlockingDeque
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,
ArrayDequedoes not support concurrent access by multiple threads. - Null elements are prohibited in the
ArrayDeque. ArrayDequeclass is likely to be faster thanStackwhen used as a stack.ArrayDequeclass is likely to be faster thanLinkedListwhen 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.
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
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.
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.
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 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.
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.
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.
