Deque in Java | Methods, Example
A double ended queue or deque in Java is a linear data structure that supports insertion and removal of elements from both ends (head and tail). It is usually pronounced “deck”, not “de queue”.
Java deque is an extended version of queue to handle a double-ended queue. It extends Queue interface with additional methods for adding and removing elements from both ends of queues.
Deque interface was recently introduced in Java 1.6 version. It is now part of the Java collections framework. It is present in java.util.Deque package.
Double ended queue in Java can be used as FIFO (first-in, first-out) queue or LIFO (last-in, first-out) queue. Adding elements in the middle of queue is not supported.
Hierarchy of Java Deque Interface
Java Deque interface extends Queue interface to handle double ended queue. It is implemented by LinkedList and ArrayDeque classes, both of which can be used to create a queue whose size can grow as needed.
Java LinkedList is ideal for queue operations because it is efficient for adding and removing elements from both ends of a list. Other implementation classes are ConcurrentLinkedDeque, and LinkedBlockingDeque which also implement the deque interface.
The hierarchy diagram of deque interface in java is shown in the below figure.
Deque Interface Declaration
Deque is a generic interface that can be declared as follows:
public interface Deque<E>
extends Queue<E>Here, E represents the type of objects that deque will hold.
Features of Java Double ended queue
There are several interesting features of the deque in java that is as follows:
1. Java Deque interface orders elements in First In First Out or Last In First Out policy.
2. Deque does not allow to store null elements. If we try to add, NullPointerException will be thrown.
3. The most important features of Deque are push and pop. The push() and pop() methods are commonly used to enable a Deque to function as a stack.
To put an element on the top of the stack, call push( ) method. To remove the top element, call pop( ) method.
[adinserter block=”5″]
4. Elements can be retrieved and removed from both ends of the queue.
5. Elements can be added from both ends of the queue.
6. The LinkedList and ArrayDeque classes are two implementation classes for the Deque interface.
7. ArrayDeque class can be implemented if deque is used as a LIFO queue (or a stack).
8. The LinkedList implementation performs better if deque is used as a FIFO queue (or simply as a queue).
Deque Methods in Java
In addition to methods inheriting from the Collection interface and Queue, Deque interface adds 17 new methods to facilitate insertion, removal, and peeking operations at both ends. They are as follows:
1. void addFirst(E e): This method is used to add an element at the head of the deque. It throws an exception named IllegalStateException if a capacity-restricted deque is out of space.
2. void addLast(E e): This method is used to add an element at the tail of the deque. It throws an IllegalStateException if a capacity-restricted deque is out of space.
3. boolean offerFirst(E e): It is used to add an element at the head of the deque. It returns true if the element is added successfully in the deque otherwise returns false. However, it does not throw an exception on failure.
4. boolean offerLast(E e): It is used to add an element at the tail of the deque. It returns true if the element is added successfully in the deque otherwise returns false. However, it does not throw an exception on failure.
5. E removeFirst( ): This method is used to retrieve and remove the element from the head of the deque. They throw an exception named NoSuchElementException if the deque is empty.
6. E removeLast(): This method is used to retrieve and remove the element from the tail of the deque. They throw an exception named NoSuchElementException if the deque is empty.
7. E pollFirst( ): The pollFirst() method performs the same task as the removeFirst() method. However, it returns null if the deque is empty.
8. E pollLast(): The pollLast() method performs the same task as the removeLast() method. However, it returns null if the deque is empty.
9. E getFirst( ): It is used to retrieve without removing the first element from the head of deque. It throws NoSuchElementException if the deque is empty.
10. E getLast(): It is used to retrieve without removing the last element from the tail of deque. It throws NoSuchElementException if the deque is empty.
11. E peekFirst( ): The peekFirst() method works the same task as the getFirst() method. It returns null object if deque is empty instead of throwing an exception.
12. E peekLast(): The peekLast() method works the same task as the getLast() method. It returns null object if deque is empty instead of throwing an exception.
13. void push(E e ): The push() method adds (or pushes) an element to the head of the deque. It will throw an IllegalStateException if a capacity-restricted deque is out of space. This method is the same as addFirst() method.
14. E pop( ): The pop() method removes (or pops) an element from the head of deque. If the deque is empty, it will throw NoSuchElementException. This method is the same as removeFirst() method.
15. boolean removeFirstOccurrence(Object o): This method removes the first occurrence of the specified element from the deque. It returns true if successful removed and false if the deque did not contain the specified element.
[adinserter block=”2″]
16. boolean removeLastOccurrence(Object o): This method removes the last occurrence of the specified element from the deque. It will return true if successful removed and false if the deque did not contain the specified element.
17. Iterator<E> descendingIterator( ): It returns an iterator object that iterate over its elements in reverse order (from tail to head). The descendingIterator() method works the same as the iterator() method, except that it moves in the opposite direction.
Java Deque Implementation Example Programs
Let’s take an example program where we will perform operations based on getFirst(), removeFirst(), addFirst(), getLast(), removeLast(), and addLast() methods. We will implement ArrayDeque class for deque interface.
Program code 1:
import java.util.ArrayDeque;
import java.util.Deque;
public class DequeTestEx {
public static void main(String[] args)
{
// Create a Deque and add elements to the deque.
Deque<String> dq = new ArrayDeque<String>();
// Adding elements in the deque.
dq.offer("ABC");
dq.offer("PQR");
dq.offer("MNO");
dq.offer("IJK");
dq.offer("GHI");
System.out.println(dq);
System.out.println("dq.getFirst(): " +dq.getFirst());
System.out.println(dq);
System.out.println("dq.removeFirst(): " +dq.removeFirst());
System.out.println(dq);
// Adding new element at the head of queue.
dq.addFirst("ABC");
System.out.println(dq);
System.out.println("dq.getLast(): " +dq.getLast());
System.out.println(dq);
System.out.println("dq.removeLast(): " +dq.removeLast());
System.out.println(dq);
dq.addLast("GHI");
System.out.println(dq);
}
}Output:
[ABC, PQR, MNO, IJK, GHI]
dq.getFirst(): ABC
[ABC, PQR, MNO, IJK, GHI]
dq.removeFirst(): ABC
[PQR, MNO, IJK, GHI]
[ABC, PQR, MNO, IJK, GHI]
dq.getLast(): GHI
[ABC, PQR, MNO, IJK, GHI]
dq.removeLast(): GHI
[ABC, PQR, MNO, IJK]
[ABC, PQR, MNO, IJK, GHI]
Deque Implementation in Java using LinkedList
Let’s take an example program where we will use a deque as a FIFO queue (or simply as a queue). We will implement LinkedList class for the deque interface. LinkedList class performs better if we use deque as a FIFO queue. Look at the source code to understand better.
Program code 2: Using a deque as a FIFO queue
import java.util.Deque;
import java.util.LinkedList;
import java.util.NoSuchElementException;
public class DequeAsQueue {
public static void main(String[] args)
{
// Create a Deque and add elements at its tail using addLast() or offerLast() method
Deque<String> dq = new LinkedList<>();
dq.addLast("John");
dq.offerLast("Richard");
dq.offerLast("Donna");
dq.offerLast("Ken");
dq.offer("Peter");
System.out.println("Deque: " + dq);
// Remove elements from deque until it is empty.
while (dq.peekFirst() != null)
{
System.out.println("Head Element: " + dq.peekFirst());
System.out.println("Removed element from Deque: " +dq.removeFirst());
System.out.println("Elements in Deque: " + dq);
}
System.out.println("\n");
// Now, deque is empty. Try to call its peekFirst(), getFirst(), pollFirst() and removeFirst() methods.
System.out.println("deque.isEmpty(): " + dq.isEmpty());
System.out.println("deque.peekFirst(): " + dq.peekFirst());
System.out.println("deque.pollFirst(): " + dq.pollFirst());
try {
String str = dq.getFirst();
System.out.println("deque.getFirst(): " + str);
}
catch (NoSuchElementException e) {
System.out.println("deque.getFirst(): Deque is empty.");
}
try {
String str = dq.removeFirst();
System.out.println("deque.removeFirst(): " + str);
}
catch (NoSuchElementException e) {
System.out.println("deque.removeFirst(): Deque is empty.");
}
}
}Output:
Deque: [John, Richard, Donna, Ken, Peter]
Head Element: John
Removed element from Deque: John
Elements in Deque: [Richard, Donna, Ken, Peter]
Head Element: Richard
Removed element from Deque: Richard
Elements in Deque: [Donna, Ken, Peter]
Head Element: Donna
Removed element from Deque: Donna
Elements in Deque: [Ken, Peter]
Head Element: Ken
Removed element from Deque: Ken
Elements in Deque: [Peter]
Head Element: Peter
Removed element from Deque: Peter
Elements in Deque: []
deque.isEmpty(): true
deque.peekFirst(): null
deque.pollFirst(): null
deque.getFirst(): Deque is empty.
deque.removeFirst(): Deque is empty.
Deque Implementation in Java using ArrayDeque
Let’s take another example program where we will demonstrate how to use a Deque as a stack (or LIFO queue). We will implement ArrayDeque class for deque interface.
Program code 3: Using Deque as Stack (or LIFO queue)
import java.util.ArrayDeque;
import java.util.Deque;
public class DequeAsStack {
public static void main(String[] args)
{
// Create a Deque and use it as stack.
Deque<String> dq = new ArrayDeque<>();
dq.push("John");
dq.push("Richard");
dq.push("Donna");
dq.push("Ken");
dq.push("Peter");
System.out.println("Stack: " + dq);
// Remove all elements from the deque.
while (dq.peek() != null)
{
System.out.println("Element at top: " + dq.peek());
System.out.println("Popped: " + dq.pop());
System.out.println("Stack: " + dq);
}
System.out.println(" Is Stack empty: " + dq.isEmpty());
}
}Output:
Stack: [Peter, Ken, Donna, Richard, John]
Element at top: Peter
Popped: Peter
Stack: [Ken, Donna, Richard, John]
Element at top: Ken
Popped: Ken
Stack: [Donna, Richard, John]
Element at top: Donna
Popped: Donna
Stack: [Richard, John]
Element at top: Richard
Popped: Richard
Stack: [John]
Element at top: John
Popped: John
Stack: []
Is Stack empty: trueHow to Iterate over Deque in Java?
Let’s take an example program where we will iterate over elements of deque using iterator() method. The iterator() method returns an iterator object that iterates over elements of a deque in LIFO order. i.e. the elements will be traversed from head to tail.
Program code 4:
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Iterator;
public class IteratingDeque {
public static void main(String[] args)
{
Deque<Integer> dq = new ArrayDeque<Integer>();
dq.offer(50);
dq.offer(10);
dq.offer(20);
dq.offer(05);
dq.offer(30);
System.out.println("Elements in deque:");
System.out.println(dq);
// Iterating over elements of the deque.
System.out.println("\nIteration in forward direction:");
Iterator<Integer> itr = dq.iterator();
while(itr.hasNext())
{
System.out.println(itr.next());
}
// Iterating over elements in reverse order.
System.out.println("\nIteration in reverse order:");
Iterator<Integer> itr2 = dq.descendingIterator();
while(itr2.hasNext())
{
System.out.println(itr2.next());
}
}
}Output:
Elements in deque:
[50, 10, 20, 5, 30]
Iteration in forward direction:
50
10
20
5
30
Iteration in reverse order:
30
5
20
10
50Let’s take another example program where we will use enhanced for loop to iterate over elements of deque in LIFO order. Look at the source code.
Program code 5:
import java.util.ArrayDeque;
import java.util.Deque;
public class DequeAsQueue {
public static void main(String[] args)
{
Deque<Integer> dq = new ArrayDeque<Integer>();
dq.offer(50);
dq.offer(10);
dq.offer(20);
dq.offer(05);
dq.offer(30);
// Iterating over elements of deque using enhanced for loop.
System.out.println("Iterating using enhanced for loop");
for (Integer element: dq) {
System.out.println(element);
}
}
}Output:
Iterating using enhanced for loop
50
10
20
5
30In this tutorial, you have learned deque interface in Java with the help of example programs. Hope that you will have understood all the basic features of deque and practiced all example programs based on the methods provided by it. In the next, we will understand ArrayDeque in Java.
Thanks for reading!!!
