Deque Data Structure

What is Deque in Data Structure?

The Deque stands for "Double Ended Queue".

Deque is an another type of queue which allows elements to be added or removed from both the front and the back which means we can insert and delete an element at the front end or rear end both.

Deque provides greater flexibility than a standard queue. This makes it particularly useful for scenarios where we need to access elements from both ends efficiently.

The following diagram represents a Deque in data structure.

Deque does not apply the concept of the FIFO (First-In-First-Out) so we can insert and delete elements from both ends of the queue.

Types of Deque in Data Structure

Operations performed on Deque

Apart from the insert and delete operations, we can also perform the following operations on the deque data structure.

Example: Deque Implementation in Java

After understanding Deque with the help of the given definition and diagram, let's look at how it's implemented in Java.

  
  // A Java program to implement Deque with all operations
  class Deque {
    int dequeArray[];
    int front;
    int rear;
    int size;
  
    public Deque(int size) {
      // Create an int data type array that stores 10 elements.
      dequeArray = new int[10];
      front = -1;
      rear = 0;
      this.size = size;
    }
  
    // Function to check Deque is full
    boolean isFull() {
      return ((front == 0 && rear == size - 1) || front == rear + 1);
    }
  
    // Function to check Deque is empty
    boolean isEmpty() {
      return (front == -1);
    }
  
    // Function to insert an element from front
    void insertFront(int element) {
      // Before inserting, make sure queue should not be full
      if (isFull()) {
        System.out.println("Overflow");
        return;
      }
  
      if (front == -1) {
        front = 0;
        rear = 0;
      } else if (front == 0) {
        front = size - 1;
      } else {
        front = front - 1;
      }
      dequeArray[front] = element;
    }
  
    // Function to insert an element at rear
    void insertRear(int element) {
      // Before inserting, make sure queue should not be full
      if (isFull()) {
        System.out.println(" Overflow ");
        return;
      }
  
      if (front == -1) {
        front = 0;
        rear = 0;
      } else if (rear == size - 1) {
        rear = 0;
      } else {
        rear = rear + 1;
      }
  
      dequeArray[rear] = element;
    }
  
    // Function to delete an element from the front
    void deleteFront() {
      // Before deleting, make sure queue should not be empty
      if (isEmpty()) {
        System.out.println("Queue Underflow\n");
        return;
      }
  
      // Deque has only one element
      if (front == rear) {
        front = -1;
        rear = -1;
      } else if (front == size - 1) {
        front = 0;
      } else {
        front = front + 1;
      }
    }
  
    // Function to delete an element from the rear
    void deleteRear() {
      // Before deleting, make sure queue should not be empty
      if (isEmpty()) {
        System.out.println(" Underflow");
        return;
      }
  
      if (front == rear) {
        front = -1;
        rear = -1;
      } else if (rear == 0) {
        rear = size - 1;
      } else {
        rear = rear - 1;
      }
    }
  
    // Function to get a value from the front
    int getFront() {
      // Before accessing element, make sure queue should not be empty
      if (isEmpty()) {
        System.out.println(" Underflow");
        return -1;
      }
      return dequeArray[front];
    }
  
    // Function to get a value from rear
    int getRear() {
      // Before accessing element, make sure queue should not be empty
      // Or, rear should not be less than 0
      if (isEmpty() || rear < 0) {
        System.out.println(" Underflow\n");
        return -1;
      }
      return dequeArray[rear];
    }
  
    public static void main(String[] args) {
      Deque deque = new Deque(5);
  
      System.out.println("Insert element 10 at the REAR end");
      deque.insertRear(10);
  
      System.out.println("insert element 20 at the REAR end");
      deque.insertRear(20);
  
      System.out.println("get REAR element: " + deque.getRear());
  
      deque.deleteRear();
      System.out.println("After deletion, get REAR: " + deque.getRear());
  
      System.out.println("Insert element 30 at the FRONT end");
      deque.insertFront(30);
  
      System.out.println("Insert element 40 at the FRONT end.");
      deque.insertFront(40);
  
      System.out.println("get FRONT: " + deque.getFront());
  
      deque.deleteFront();
      System.out.println("After deletion, FRONT element: "+ deque.getFront());
    }
  }

Insert element at REAR end: 10
insert element at REAR end: 20
get REAR element : 20
After delete, get REAR element: 10
Insert element at FRONT end: 30
Insert element at FRONT end: 40
get FRONT element: 40
After delete, FRONT element: 30

Operations	Time Complexity	Space Complexity
Insert Front	O(1)	O(n)
Insert Rear	O(1)	O(n)
Delete Front	O(1)	O(n)
Delete Rear	O(1)	O(n)
Search	O(n)	O(n)

Operations

Time Complexity

Space Complexity

Insert Front

O(1)

O(n)

Insert Rear

O(1)

O(n)

Delete Front

O(1)

O(n)

Delete Rear

O(1)

O(n)

Search

O(n)

Advantages of Deque

Deque allows to insert and delete elements from both the front and back ends of the queue.

Deques size is not fixed. It can grow or shrink its size dynamically when required.

Deques provide an efficient time complexity of O(1) for the insertion and deletion of elements from both ends.

Deques can be implemented as stacks (LIFO), queues (FIFO), or a combination of both of them.

Deques do not require reallocation of memory when elements are inserted or removed.

When elements are inserted or deleted from a deque, no memory reallocation is required.

Deque is more efficient and fast in inserting and deleting the elements to the end or beginning of the queue.

Deques can be thread-safe if properly synchronized.

Disadvantages of Deque

Deques required extra pointers to maintain the double-ended structure, so than other data structures, it has higher memory overhead.

Compared to a normal queue, Deques are less memory efficient.

It has synchronization issues when working with multiple threads.

Not every platform may support deques.

Not suitable to implement sorting or searching operations.

Compared to other data structures, Deque has a lower number of functionalities.

What is Deque in Data Structure?

Types of Deque in Data Structure

Operations performed on Deque

Example: Deque Implementation in Java

Time and Space Complexity of Deque Operations

Advantages of Deque

Disadvantages of Deque