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

A typical deque collection will look as shown below:

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.

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:

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:

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.

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:

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.