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.

Java deque interface hierarchy diagram

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.


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.


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 source 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>();
	
  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 create a 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 source 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 create another 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 source 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. add elements at its tail using addLast() or offerLast() method.
  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: true

How 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 source 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
     50

Let’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 source 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
       30

Hope that this tutorial has covered almost all the important points related to deque interface in java with example programs. I hope that you will have understood this topic.
Thanks for reading!!!
Next ⇒ ArrayDeque in Java

⇐ Prev Next ⇒