Deque In Java – Deque Implementation And Examples

This Tutorial Provides Detailed Explanation of Deque or “Double-ended Queue” in Java. You will learn about Deque Interface, API Methods, Implementation, etc:

The Deque or “double-ended queue” in Java is a data structure in which we can insert or delete elements from both the ends. The deque is an interface in Java belonging to java.util package and it implements java.queue interface.

We can implement deque as a stack (Last In, First Out) structure or as a queue (first-in-first-out). Deque is faster than Stack and/or LinkedList. Deque is pronounced as “deck” as in the “deck of cards”.

=> Check Here To See A-Z Of Java Training Tutorials Here.

Deque In Java

Deque In Java

A typical deque collection will look as shown below:

Deque collection in Java

Deque is mostly used to implement stack, queue, or list data structures. It can also be used to implement priority queues. The features of undo or history mostly present in the web browsers can be implemented using deques.

Java Deque Interface

The diagram below shows the hierarchy for the double-ended queue or deque. As shown in the below diagram, the Deque interface extends to the Queue interface that in turn extends the Collection interface.

deque hierarchy

To use a deque interface in our program, we have to import the package that holds deque functionality using an import statement as shown below.

import java.util.deque;

or

import java.util.*;

As the deque is an interface, we need concrete classes to implement the functionality of the deque interface.

The two classes below, implement the deque interface.

  • ArrayDeque
  • LinkedList

Hence we can create deque objects using these two classes as shown below:

Deque<String> numdeque = new ArrayDeque<> ();
Deque<String> strDeque = new LinkedList<> ();

Thus once the above deque objects are successfully created, they can use the functionality of the deque interface.

Given below are a few important points to be noted about deque:

  • Deque interface supports resizable arrays that can grow as required.
  • Array deques do not allow the use of Null values.
  • Deque does not support concurrent access by more than one thread.
  • Deque is not thread-safe unless an external synchronization is provided.

ArrayDeque In Java

ArrayDeque belongs to java.util package. It implements the deque interface. Internally, the ArrayDeque class makes use of a dynamically resizable array that grows as the number of elements is increased.

The below diagram shows the hierarchy for the ArrayDeque class:

hierarchy for the ArrayDeque class

As shown in the diagram, the ArrayDeque class inherits the AbstractCollection class and implements the Deque interface.

We can create a deque object using the ArrayDeque class as shown below:

Deque deque_obj = new ArrayDeque ();

Deque Example

The following Java program demonstrates a simple example to better understand the deque. Here, we have used the ArrayDeque class to instantiate the deque interface. We have just added some elements to the deque object and then printed them using a forEach loop.

import java.util.*;  
public class Main {  
   public static void main(String[] args) {  
        //Creat a Deque and add elements  
        Deque<String> cities_deque = new ArrayDeque<String>();  
        cities_deque.add("Delhi");    
        cities_deque.add("Mumbai");     
        cities_deque.add("Bangaluru");    
        System.out.println("Deque Contents:");
        //Traverse the Deque  
        for (String str : cities_deque) {  
            System.out.print(str + " ");  
        }  
   }  
}  

Output:

OUTPUT - Content Example

Deque API Methods In Java

As the deque interface implements a queue interface, it supports all the methods of the queue interface. Besides, the deque interface provides the following methods that can be used to perform various operations with the deque object.

Let's summarize these methods in the below table.

MethodMethod PrototypeDescription
addboolean add(E e)Adds given element e into the deque (at the tail) without violating capacity restrictions and returns true if success. Throws IllegalStateException if no space available in the deque.
addFirstvoid addFirst(E e)Adds given element e to the front of the queue without violating capacity restrictions.
addLastvoid addLast(E e)Adds element e to the last of the deque without violating capacity restrictions.
containsboolean contains(Object o)Checks if the deque contains given element o. Returns true if yes.
descendingIteratorIterator < E > descendingIterator()This method returns reverse order iterator for the deque.
elementE element()Returns the first element or head of the deque. Note that it does not delete the element.
getFirstE getFirst()Retrieve the first element of the deque without removing it.
getLastE getLast()Gets the last element of the deque without removing it.
iteratorIterator< E > iterator()Returns a standard iterator over the elements of the deque.
offerboolean offer(E e)Adds given element e to the deque (as a tail) without violating capacity restrictions. Returns true on success and false on failure.
offerFirstboolean offerFirst(E e)Insert the given element e to the front of the deque without violating capacity restrictions.
offerLastboolean offerLast(E e)Insert the given element e at the end of the deque without violating capacity restrictions.
peekE peek()Returns head of the deque (first element) or null if a queue is empty. ** does not delete the head
peekFirstE peekFirst()Returns the first element in the deque without deleting it. Returns null if the deque is empty.
peekLastE peekLast()Retrieves the last element in the deque without removing it. Returns null if the deque is empty.
pollE poll()Deletes and returns the head of the deque. Returns null if the deque is empty.
pollFirstE pollFirst()Returns and removes the first element of the deque. Returns null if the deque is empty.
pollLastE pollLast()Returns and removes the last element of the deque. Returns null if the deque is empty.
popE pop()Pop the element from the stack that is represented using deque.
pushvoid push(E e)Push given element e on to the stack represented using deque without violating the capacity restrictions. Returns true on success or IllegalStateException if no space is available on deque.
removeE remove()Remove and return the head of the deque.
removeboolean remove(Object o)Remove the first occurrence of the given element o from the deque.
removeFirstE removeFirst()Remove and return the first element of the deque.
removeFirstOccurrenceboolean removeFirstOccurrence(Object o)Removes the first occurrence of the given element o from the deque.
removeLastE removeLast()Retrieves and deletes the last element in the deque.
removeLastOccurrenceboolean removeLastOccurrence(Object o)Deletes the last occurrence of a given element o from the deque.
sizeint size()Returns the size or number of elements in the deque.

Deque Implementation In Java

Let's now implement a Java program to demonstrate some of the major deque methods discussed above.

In this program, we use a String type deque and then add elements to this deque using various methods like add, addFirst, addLast, push, offer, offerFirst, etc. Then we display the deque. Next, we define the standard and reverse iterators for the deque and traverse through the deque to print the elements.

We also use the other methods like contains, pop, push, peek, poll, remove, etc.

import java.util.*; 
public class Main { 
    public static void main(String[] args) { 
        //Declare Deque object 
        Deque<String> deque = new LinkedList<String>(); 
        // add elements to the queue using various methods 
        deque.add("One");           //add ()
        deque.addFirst("Two");      //addFirst ()
        deque.addLast("Three");     //addLast ()
        deque.push("Four");         //push ()
        deque.offer("Five");        //offer ()
        deque.offerFirst("Six");    //offerFirst ()
        deque.offerLast("Seven");   //offerLast ()
        System.out.println("Initial Deque:");
        System.out.print(deque + " "); 
     
       // Iterate using standard iterator
        System.out.println("\n\nDeque contents using Standard Iterator:"); 
        Iterator iterator = deque.iterator(); 
        while (iterator.hasNext()) 
            System.out.print(" " + iterator.next()); 
       
       // Iterate using Reverse order iterator 
        Iterator reverse = deque.descendingIterator(); 
        System.out.println("\n\nDeque contents using Reverse Iterator:"); 
        while (reverse.hasNext()) 
            System.out.print(" " + reverse.next()); 
         
        // Peek () method
        System.out.println("\n\nDeque Peek:" + deque.peek()); 
        System.out.println("\nDeque,After peek:" + deque); 
       
         // Pop () method 
        System.out.println("\nDeque Pop:" + deque.pop()); 
        System.out.println("\nDeque,After pop:" + deque); 
  
        // contains () method
        System.out.println("\nDeque Contains Three: " +  deque.contains("Three")); 
  
        deque.removeFirst();        //removeFirst () 
        deque.removeLast();         //removeLast ()
        System.out.println("\nDeque, after removing "  + "first and last elements: " + deque); 
   } 
}

Output:

output - implementation

Frequently Asked Questions

Q #1) Is Deque thread-safe Java?

Answer: ArrayDeque is not thread-safe. But the BlockingDeque interface in the java.util.concurrent class represents the deque. This deque is thread-safe.

Q #2) Why is Deque faster than stack?

Answer: The ArrayDeque interface that implements the deque interface is memory efficient as it need not keep a track of the previous or next nodes. Also, it is a resizable implementation. Thus deque is faster than the stack.

Q #3) Is Deque a stack?

Answer: A deque is a double-ended queue. It permits LIFO behavior and thus it can be implemented as a stack though it is not a stack.

Q #4) Where is Deque used?

Answer: A deque is mostly used to implement features like undo and history.

Q #5) Is Deque circular?

Answer: Yes, Deque is circular.

Conclusion

This completes our tutorial on the Deque interface in Java. The deque interface is implemented by a deque data structure which is a collection that can insert and delete elements from both the ends.

The two classes i.e. ArrayDeque and LinkedList implement the deque interface. We can use these classes to implement the functionality of the deque interface.

=> Visit Here For The Exclusive Java Training Tutorial Series.