Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Deque interface in Java
2.1.
Hierarchy of Java Deque Interface
2.2.
Declaration
2.3.
Creating Deque Objects
2.4.
Example of a Deque:
3.
ArrayDeque Class
3.1.
Example
4.
Operations using the Deque Interface and the ArrayDeque class
4.1.
Addition of Elements
4.2.
Removing Elements
4.3.
Iterating through the Deque
5.
Deque Methods
6.
Frequently Asked Questions
7.
Conclusion
Last Updated: Mar 27, 2024

Deque

Author Sanjana Yadav
0 upvote

Introduction

The Deque interface, which is included in the java.util package is a variant of the queue interface. The Deque is similar to a double-ended queue in that it allows elements to be added or removed from either end of the data structure. It can function as either a queue (first-in-first-out/FIFO) or a stack (last-in-first-out/LIFO). Deque is an abbreviation for double-ended queue.

Also read, Duck Number in Java and Hashcode Method in Java

Deque interface in Java

Hierarchy of Java Deque Interface

The Java Deque interface extends the Queue interface to provide double-ended queues. It is implemented by the LinkedList and ArrayDeque classes, which may both be used to form a queue whose size can be increased as needed.

Java LinkedList is appropriate for queue operations because it is efficient for adding and deleting elements from both ends of a list.

ConcurrentLinkedDeque and LinkedBlockingDeque are two other implementation classes that implement the deque interface.

Declaration

Deque is a generic interface that may be declared in the following manner:

public interface Deque<objectType>
       extends Queue<objectType>

Creating Deque Objects

Objects of the type deque cannot be created because Deque is an interface. We always require a class that extends this list to build an object. Furthermore, since the introduction of Generics in Java 1.5, it is possible to limit the type of object that may be kept in the Deque. This type-safe queue is defined as follows:

// ObjectType is the type of object to be stored in Deque
Deque<ObjectType> deque = new ArrayDeque<ObjType> ();

Example of a Deque:

import java.util.*;
public class SampleDeque {
    public static void main(String[] args)
    {
        Deque<String> deque
            = new LinkedList<String>();
        // there are several ways to add elements to a deque
        // Add at last
        deque.add("1 Element (Last)");
        // Add at first
        deque.addFirst("2 Element (First)");
        // Add at last
        deque.addLast("3 Element (Last)");
        // Add at first
        deque.push("4 Element (First)");
        // Add at last
        deque.offer("5 Element (Last)");
        // Add at first
        deque.offerFirst("6 Element (First)");
        System.out.println(deque + "\n");
        // We can remove the first element
        // or the last element.
        deque.removeFirst();
        deque.removeLast();
        System.out.println("Deque after removing "
                        + "first and last elements: "
                        + deque);
    }
}

Output:

[6 Element (First), 4 Element (First), 2 Element (First), 1 Element (Last), 3 Element (Last), 5 Element (Last)]

Deque after removing first and last elements: [4 Element (First), 2 Element (First), 1 Element (Last), 3 Element (Last)]

Also see,  Swap Function in Java

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

ArrayDeque Class

The ArrayDeque class, implemented in the collection framework, allows us to use resizable-array. This unique array grows and allows users to add or delete elements from both sides of the queue. Array deques have no capacity constraints and increase as needed to meet consumption. They are not thread-safe, which implies that ArrayDeque does not enable concurrent access by multiple threads in the absence of external synchronization. When used as a stack, the ArrayDeque class is expected to be faster than Stack. When used as a queue, the ArrayDeque class is expected to be faster than the LinkedList class.

Example

Below is the java program to demonstrate the creation of a deque object in Java using the ArrayDeque class.

import java.util.*;
public class SampleArrayDeque {
    public static void main(String[] args)
    {
        // Initializing the deque
        Deque<Integer> dq
            = new ArrayDeque<Integer>(10);
        // add method to insert
        dq.add(50);
        dq.add(60);
        dq.add(70);
        dq.add(80);
        dq.add(90);
        System.out.println(dq);
        // clear() method
        dq.clear();
        // addFirst() method to insert the
        // elements at the head
        dq.addFirst(321);
        dq.addFirst(200);
        // addLast() method to insert the
        // elements at the tail
        dq.addLast(37);
        dq.addLast(15);
        System.out.println(dq);
    }
}

Output

[50, 60, 70, 80, 90]
[200, 321, 37, 15]

Operations using the Deque Interface and the ArrayDeque class

Addition of Elements

The add() function can be used to add an element to a deque. Since addition is possible from any direction in the deque, two more methods are available: addFirst() and addLast(), which are used to add entries at either end.

Example

import java.util.*;
public class SampleArrayDeque{
    public static void main(String[] args)
    {
        // Initializing an deque
        Deque<String> dq
            = new ArrayDeque<String>();


        // add() method to insert
        dq.add("Coding");
        dq.addFirst("Hello");
        dq.addLast("Ninjas");

        System.out.println(dq);
    }
}

Output

[Hello, Coding, Ninjas]

Removing Elements

There are several ways available for removing an element from a deque. Because we may remove from both ends, the deque interface includes removeFirst() and removeLast() methods. Aside from that, this interface offers us the poll(), pop(), pollFirst(), and pollLast() methods, with pop() being used to remove and return the deque's head. Poll(), on the other hand, is utilized since it provides the same functionality as pop() and does not throw an exception when the deque is empty.

Example

import java.util.*;
public class SampleArrayDeque {
    public static void main(String[] args)
    {
        // Initializing an deque
        Deque<String> dq
            = new ArrayDeque<String>();
        // add() method to insert
        dq.add("Coding");
        dq.addFirst("Hello");
        dq.addLast("Ninjas");

        System.out.println(dq);
        System.out.println(dq.pop());
        System.out.println(dq.poll());
        System.out.println(dq.pollFirst());
        System.out.println(dq.pollLast());
    }
}

Output

[Hello, Coding, Ninjas]
Hello
Coding
Ninjas
null

Iterating through the Deque

Because a deque may be iterated in both directions, the deque interface's iterator function offers us two options to iterate—one from the front and one from the back.

Example

import java.util.*;
public class SampleArrayDeque {
    public static void main(String[] args)
    {
        // Initializing an deque
        Deque<String> dq
            = new ArrayDeque<String>();


        // add() method to insert
        dq.add("Welcome to");
        dq.addFirst("Hello,");
        dq.addLast("Coding");
        dq.add("Ninjas");


        for (Iterator itr = dq.iterator();
            itr.hasNext();) {
            System.out.print(itr.next() + " ");
        }

        System.out.println();
        for (Iterator itr = dq.descendingIterator();
            itr.hasNext();) {
            System.out.print(itr.next() + " ");
        }
    }
}

Output

Hello, Welcome to Coding Ninjas
Ninjas Coding Welcome to Hello


Practice by yourself on online java compiler.

Deque Methods

In addition to methods inherited from the Collection and Queue interfaces, the Deque interface includes 17 additional methods to help with insertion, removal, and peeking operations at both ends.

  1. void addFirst(element): This method is used to add an element to the deque's head. If a capacity-restricted deque runs out of space, it throws an IllegalStateException exception.
     
  2. void addLast(element): This method inserts an element at the end of a deque. If a capacity-restricted deque runs out of space, it throws an IllegalStateException.
     
  3. boolean offerFirst(element): It is used to insert an element at the beginning of the deque. If the element is successfully added to the deque, it returns true; otherwise, it returns false. It does not, however, throw an exception on failure.
     
  4. boolean offerLast(element): It adds an element to the deque's tail. If the element is successfully added to the deque, it returns true; otherwise, it returns false. It does not, however, throw an exception on failure.
     
  5. ObjectType removeFirst( ): This method retrieves and removes the element from the deque's head. If the deque is empty, they throw a NoSuchElementException exception.
     
  6. ObjectType removeLast(): This method is used to get and remove an element from the deque's tail. If the deque is empty, they throw a NoSuchElementException exception.
     
  7. ObjectType pollFirst(): The pollFirst() method is equivalent to the removeFirst() method. If the deque is empty, it returns null.
     
  8. ObjectType pollLast(): The pollLast() method is equivalent to the removeLast() method. If the deque is empty, it returns null.
     
  9. ObjectType getFirst( ): It is used to obtain an element without deleting the initial element from the deque's head. If the deque is empty, it raises a NoSuchElementException.
     
  10. ObjectType getLast(): It is used to obtain the last element from the tail of a deque without deleting it. If the deque is empty, it raises a NoSuchElementException.
     
  11. ObjectType peekFirst( ): The peekFirst() method performs the same function as the getFirst() method. Instead of issuing an exception, it returns a null object if the deque is empty.
     
  12. ObjectType peekLast(): The peekLast() method performs the same function as getLast(). Instead of issuing an exception, it returns a null object if the deque is empty.
     
  13. void push(element): The push() function inserts (or pushes) an element into the deque's head. If a capacity-restricted deque runs out of space, it will issue an IllegalStateException. This function is similar to the addFirst() method.
     
  14. ObjectType pop( ): The pop() method pops (or removes) an element from the deque's head. If the deque is empty, a NoSuchElementException is thrown. This method is equivalent to the removeFirst() method.
     
  15. boolean removeFirstOccurrence(Object o): This method deletes the deque's first occurrence of the provided element. It returns true if the removal was successful and false if the deque did not contain the given element.
     
  16. boolean removeLastOccurrence(Object o): This function deletes the deque's last occurrence of the given element. It returns true if the element was successfully deleted and false if the deque did not contain the provided element.
     
  17. Iterator<ObjectType> descendingIterator( ): It returns an iterator object, which iterates over its members in reverse order (from tail to head). The descendingIterator() function works similarly to the iterator() method but in the opposite direction.

Frequently Asked Questions

  1. What is deque for?
    Double Ended or Deque Queue is an extended version of the Queue data structure that supports insert and delete operations at both ends.
     
  2. Where do we use deque?
    Deque is a Double Ended Queue that allows operations (Add/Remove) to be performed on both ends of the queue.
     
  3. Is deque a FIFO?
    As with the stack, the FIFO (first in, first out) attribute, rather than the names of the operations, is the primary distinguishing characteristic of the queue.

Conclusion

In this article, we have extensively discussed the deque interface in java. We learned to declare and create a deque object; we also learned about ArrayDeque class and several operations using the deque and ArrayDeque class.
In the end, we looked at several methods present in the deque interface.

We hope that this blog has helped you enhance your knowledge of the deque interface in java and if you would like to learn more about java, check out our articles, java archives. Do upvote our blog to help other ninjas grow. Happy Coding!

Previous article
Priority Blocking Queue
Next article
Introduction to Deque its applications
Live masterclass