Deque in Data Structure

In this article, we are going to learn about the topic deque in data structure. Before getting started with the deque in data structure let us get a short overview of what is a data structure in this article.

Deque in data structure: A deque is a linear data structure, which stands for Double Ended Queue. Unlike queue, where the data can be only inserted from one end and deleted from another, in a deque, the data can be inserted and deleted from both front and rear ends.

Scope

• In this article we are going to learn about the topic deque in a data structure in detail. We are also going to learn about
  • Types of deque in data structures.
  • Operations that can be performed on deque in data structure.
  • How we can implement deque in data structure in different programming languages like java, python, c, c++.
  • Applications of the deque in data structure.

What is a Deque in Data Structure?

The deque in data structure stands for Double Ended Queue. We can say the deque in data structure is a generalized version of the queue. Now you must be wondering what is a queue, so let’s see a brief description of the queue.

Queue
A queue is a data structure that follows the FIFO policy (First in first out) , that is, whatever comes first will go out first. In a queue, the data is inserted from one end which is called as the rear end or tail, whereas the data is deleted from another end which is called as the front end or head of the queue.

A deque in data structure is a linear data structure that does not follow the FIFO rule (First in first out) , that is, in a deque data structure, the data can be inserted and deleted from both front and rear ends. However, in a queue, we may only insert and remove data from one end.

The representation of a deque in data structure is represented below –

Types of Deque in Data Structure

Basically, there are two types of deque in data structure

• Input restricted queue
• Output restricted queue

Let us discuss about them in detail.

Input restricted queue

In an input restricted queue, the data can be inserted from only one end, while it can be deleted from both the ends.

Let’s see a diagram to understand it more clearly.

Explanation: In the above example we can see how the data has been inserted from only one end that is the front end, and how it has been deleted from both the ends that are front and rear ends.

Output restricted queue

In an Output restricted queue, the data can be deleted from only one end, while it can be inserted from both the ends.

Let’s see a diagram to understand it more clearly.

Explanation: In the above example, we can see how the data has been inserted from both the ends(front and rear), and how it has been deleted from only one end(rear).

Operations on Deque in Data Structure

In this section, we are going to implement a dequ in data structure using the circular queue or array. So before going further let’s get a brief idea about what is a circular array.

Circular array: It is an array where the last element of the array is connected to the first element. Thus, it forms a circle like structure, that makes it reusable for the empty spaces in the previous indexes caused due to deletion operations.

In a circular array, if the array is full, we again start from the beginning. However in a linear array, if the array is full, we can’t insert elements anymore. In each of the operations explained below, if the array is full, an “overflow message” will be thrown.

In a deque in data structure we can perform the following operations:

• Insertion at front
• Insertion at rear
• Deletion at front
• Deletion at rear

Before performing the following operations, we must follow the below steps :

• Take a deque(array) of size n
• Set two pointers variables front = -1 and rear = 0 at the first position.

Now, let us understand the operations performed on deque in data structure with examples.

Insertion at the front end

With the help of the Insertion at the front end operation we can insert the element from the front end of the deque in data structure. There is a criterion before implementing the operation, at first we need to check whether the deque is full or not. If the deque is not full, then we can insert the element from the front end, by following the below conditions –

1. Initially, we will check the position of the front variable in our array

2. In case, the front variable is less than 1 (front < 1), we will reinitialize the front as the last index of the array (front = n-1).

3. Otherwise, we will decrease the front by 1.
4. Add the new key for example 5 here into our array at the index front – array[front].
5. Every time we insert a new element inside the deque the size increases by 1.

Insertion at the rear end

With the help of the Insertion at the rear end operation, we can insert the element from the rear end of the deque in data structure. We can insert the element from the rear end by following the below conditions –

1. At first, we need to check whether the deque in data structure is full or not.

2. If the deque data structure is full, we have to reinitialize the rear with 0 (rear = 0).
3. Else increase the rear by 1.

4. Add the new key for example 5 here into our array at the index rear – array[rear].
5. Every time we insert a new element inside the deque the size increases by 1.

Deletion at the front end

With the help of the Deletion at the front end operation, we can delete the element from the front end of the deque in data structure. We can delete the element from the front end by following the below conditions –

1. At first, we need to check whether the deque in data structure is empty or not.

2. If the deque data structure is empty i.e. front = -1, we cannot perform the deletion process and it will throw an error of underflow condition.
3. If the deque data structure contains only one element i.e. front = rear, set front = -1 and rear = -1.
4. Else if the front is at the last index i.e. front = n - 1, we point the front to the starting index of the deque data structure i.e. front = 0.
5. If none of the cases satisfy we simply increment our front by 1, front = front + 1.
6. Every time we delete any element from the deque data structure the size decreases by 1.

Deletion at the rear end

With the help of Deletion at the rear end operation, we can delete the element from the rear end of the deque in data structure. We can delete the element from the rear end by following the below conditions –

1. At first, we need to check whether the deque data structure is empty or not.

2. If the deque data structure is empty i.e. front = -1, we cannot perform the deletion process and it will throw an error of underflow condition.
3. If the deque data structure contains only one element i.e. front = rear, set front = -1 and rear = -1.
4. Else if the rear is at the starting index of the deque i.e. rear = 0, point the rear to the last index of the deque data structure i.e. rear = n-1.
5. If none of the cases satisfy we simply decrement our rear by 1, rear = rear - 1.
6. Every time we delete any element from the deque the size decreases by 1.

Check empty

With the help of the Check empty operation we can check whether the deque in data structure is empty or not. The deque in data structure is empty if the front is -1 (front = -1).

Check full

With the help of the Check full operation in our deque in data structure, we can check whether the deque data structure is full or not. If the front is at the starting index (front = 0) and the rear is at the last index (rear = n-1) OR the front is ahead of rear by one unit (front = rear + 1), the deque data structure is full.

Other operations like peek can also be performed in the deque in data structure. Usually with the peek operation we can get the front or rear elements from deque in data structure. So along with the above operations, we can also perform different peek operations as stated below :

• To Get the front item from the deque in data structure
• To Get the rear item from the deque in data structure
• To check whether the deque data structure is full or not
• To check whether the deque data structure is empty or not

Shape Your Coding Future! Join Our DSA Course and Navigate the World of Efficient Algorithms. Enroll Now!

Deque Implementation in Java, Python, C, and C++

Now, let us see the implementation of deque in data structure in different programming languages.

Deque Implementation in Java

The code for the implementation of Deque in data structure in Java is given below.

code:

// Deque implementation in Java
import java.util.*;

class Main {
  static final int MAX = 1000;
  int arr[];
  int front;
  int rear;
  int size;

  // Deque constructor.
  public Main(int size) {
    arr = new int[MAX];
    front = -1;
    rear = 0;
    this.size = size;
  }

  // Checking if the Deque is full.
  boolean isFull() {
    return ((front == 0 && rear == size - 1) || front == rear + 1);
  }

  // Checking if the Deque is full.
  boolean isEmpty() {
    return (front == -1);
  }

 // Inserting value in Deque from front.
  void insertFront(int key) {
    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;

    arr[front] = key;
  }

  // Inserting value in Deque from rear.
  void insertRear(int key) {
    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;

    arr[rear] = key;
  }

  // Deleting value from front in the Deque..
  void deleteFront() {
    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;
  }

  // Deleting value from rear in the Deque.
  void deleteRear() {
    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;
  }

  // Getting value from front in the Deque.
  int getFront() {
    if (isEmpty()) {
      System.out.println(" Underflow");
      return -1;
    }
    return arr[front];
  }

  // Getting value from rear in the Deque.
  int getRear() {
    if (isEmpty() || rear < 0) {
      System.out.println(" Underflow\n");
      return -1;
    }
    return arr[rear];
  }

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    System.out.println("Enter the size of the Deque: ");
    int data = 0;
    int n = sc.nextInt();
    Main dq = new Main(n);

    System.out.println("Enter the element to be inserted in the front end of Deque: ");
    data = sc.nextInt();
    dq.insertFront(data);

    System.out.println();

    System.out.println("Enter the element to be inserted in the front end of Deque: ");
    data = sc.nextInt();
    dq.insertFront(data);

    System.out.println();

    System.out.println("get front element: " + dq.getFront());
    dq.deleteFront();

    System.out.println();

    System.out.println("After delete front element new front become : " + +dq.getFront());

    System.out.println();

    System.out.println("Enter the element to be inserted in the rear end of Deque :");
    data = sc.nextInt();
    dq.insertRear(data);

    System.out.println();

    System.out.println("get rear element : " + dq.getRear());

    System.out.println();

    dq.deleteRear();
    System.out.println("After delete rear element new rear become : " + dq.getRear());

    System.out.println("Is the deque empty? : " + dq.isEmpty());

    System.out.println("Is the deque full? : " + dq.isFull());
  }
}

Output:

Enter the size of the Deque:
4
Enter the element to be inserted in the front end of Deque: 
10
Enter the element to be inserted in the front end of Deque: 
20
get front element: 20

After deleting the front element new front become : 10

Enter the element to be inserted in the rear end of Deque :
14
get rear element : 14
After deleting the rear element new rear become : 10
Is the deque empty? : false
Is the deque full? : false

Explanation

In the above code, we have implemented deque in data structure in the java programming language.

We are going to perform the following operations in our deque in data structure in this code:

• isFull() : This function is used to check whether the deque data structure is full or not.
• isEmpty() : This function is used to check whether the deque data structure is empty or not.
• insertFront() : This function is used to insert an element at the front end of the deque data structure
• insertRear() : This function is used to insert element at the rear end of the deque data structure
• deleteFront(): This function is used to delete elements from the front end of the deque in data structure
• deleteRear(): This function is used to delete elements from the rear end of the deque in data structure
• getFront(): This function is used to get or peek element from the front end of the deque in data structure
• getRear(): This function is used to get or peek element from the rear end of the deque in data structure

Deque Implementation in Python

The code for the implementation of deque in data structure in Python is given below.

code:

# Deque implementaion in python
class Deque:
    def __init__(self):
        self.items = []

    def isEmpty(self):
        return self.items == []

    def addRear(self, item):
        self.items.append(item)

    def addFront(self, item):
        self.items.insert(0, item)

    def removeFront(self):
        return self.items.pop(0)

    def removeRear(self):
        return self.items.pop()

    def size(self):
        return len(self.items)

def main():
    d = Deque()
    print(d.isEmpty())
    d.addRear(10)
    d.addRear(6)
    d.addFront(7)
    d.addFront(8)
    print(d.size())
    print(d.isEmpty())
    d.addRear(11)
    print(d.removeRear())
    print(d.removeFront())
    d.addFront(25)
    d.addRear(15)
    print(d.items)
    
if __name__ == '__main__':
    main()

Output:

True
4
False
11
8
[25, 7, 10, 6, 15]

Explanation:

We are basically performing the following operations in our deque in data structure in this code:

• size() : This function is used to get the size of the deque in data structure.
• isEmpty() : This function is used to check whether the deque in data structure is empty or not.
• addFront() : This function is used to insert element at the front end of the deque in data structure
• addRear() : This function is used to insert element at the rear end of the deque in data structure
• removeFront(): This function is used to delete elements from the front end of the deque in data structure
• removeRear(): This function is used to delete elements from the rear end of the deque in data structure
• getFront(): This function is used to get or peek elements from the front end of the deque in data structure
• getRear(): This function is used to get or peek element from the rear end of the deque in data structure

Deque Implementation in C

The code for the implementation of deque in data structure in C is given below.

code:

// Deque implementation in C

#include <stdio.h>

#define MAX 10

void addFront(int *, int, int *, int *);
void addRear(int *, int, int *, int *);
int delFront(int *, int *, int *);
int delRear(int *, int *, int *);
void display(int *);
int count(int *);

int main() {
  int arr[MAX];
  int front, rear, i, n;

  front = rear = -1;
  for (i = 0; i < MAX; i++)
    arr[i] = 0;

  addRear(arr, 6, &front, &rear);
  addFront(arr, 10, &front, &rear);
  addRear(arr, 20, &front, &rear);
  addFront(arr, 25, &front, &rear);
  addRear(arr, 64, &front, &rear);
  addFront(arr, 18, &front, &rear);

  printf("\nElements in a deque: ");
  display(arr);

  i = delFront(arr, &front, &rear);
  printf("\nremoved item: %d", i);

  printf("\nElements in a deque after deletion: ");
  display(arr);

  addRear(arr, 16, &front, &rear);
  addRear(arr, 7, &front, &rear);

  printf("\nElements in a deque after addition: ");
  display(arr);

  i = delRear(arr, &front, &rear);
  printf("\nremoved item: %d", i);

  printf("\nElements in a deque after deletion: ");
  display(arr);

  n = count(arr);
  printf("\nTotal number of elements in deque: %d", n);
}

void addFront(int *arr, int item, int *pfront, int *prear) {
  int i, k, c;

  if (*pfront == 0 && *prear == MAX - 1) {
    printf("\nDeque is full.\n");
    return;
  }

  if (*pfront == -1) {
    *pfront = *prear = 0;
    arr[*pfront] = item;
    return;
  }

  if (*prear != MAX - 1) {
    c = count(arr);
    k = *prear + 1;
    for (i = 1; i <= c; i++) {
      arr[k] = arr[k - 1];
      k--;
    }
    arr[k] = item;
    *pfront = k;
    (*prear)++;
  } else {
    (*pfront)--;
    arr[*pfront] = item;
  }
}

void addRear(int *arr, int item, int *pfront, int *prear) {
  int i, k;

  if (*pfront == 0 && *prear == MAX - 1) {
    printf("\nDeque is full.\n");
    return;
  }

  if (*pfront == -1) {
    *prear = *pfront = 0;
    arr[*prear] = item;
    return;
  }

  if (*prear == MAX - 1) {
    k = *pfront - 1;
    for (i = *pfront - 1; i < *prear; i++) {
      k = i;
      if (k == MAX - 1)
        arr[k] = 0;
      else
        arr[k] = arr[i + 1];
    }
    (*prear)--;
    (*pfront)--;
  }
  (*prear)++;
  arr[*prear] = item;
}

int delFront(int *arr, int *pfront, int *prear) {
  int item;

  if (*pfront == -1) {
    printf("\nDeque is empty.\n");
    return 0;
  }

  item = arr[*pfront];
  arr[*pfront] = 0;

  if (*pfront == *prear)
    *pfront = *prear = -1;
  else
    (*pfront)++;

  return item;
}

int delRear(int *arr, int *pfront, int *prear) {
  int item;

  if (*pfront == -1) {
    printf("\nDeque is empty.\n");
    return 0;
  }

  item = arr[*prear];
  arr[*prear] = 0;
  (*prear)--;
  if (*prear == -1)
    *pfront = -1;
  return item;
}

void display(int *arr) {
  int i;

  printf("\n front:  ");
  for (i = 0; i < MAX; i++)
    printf("  %d", arr[i]);
  printf("  :rear");
}

int count(int *arr) {
  int c = 0, i;

  for (i = 0; i < MAX; i++) {
    if (arr[i] != 0)
      c++;
  }
  return c;
}

Output:

Elements in a deque: 
front:    18  25  10  6  20  64  0  0  0  0  :rear
removed item: 18
Elements in a deque after deletion: 
 front:    0  25  10  6  20  64  0  0  0  0  :rear
Elements in a deque after addition: 
 front:    0  25  10  6  20  64  16  7  0  0  :rear
removed item: 7
Elements in a deque after deletion: 
 front:    0  25  10  6  20  64  16  0  0  0  :rear
Total number of elements in deque: 6

Explanation:

We are going to perform the following operations in our deque in data structure in this code:

• count() : This function is used to count the total number of elements in the deque in data structure. This can be done by iterating over the whole deque in data structure.
• addFront() : This function is used to insert an element at the front end of the deque in data structure.
• addRear() : This function is used to insert element at the rear end of the deque in data structure
• delFront(): This function is used to delete elements from the front end of the deque in data structure
• delRear(): This function is used to delete elements from the rear end of the deque in data structure
• display(): This function is used to get or peek all the elements from the deque in data structure

Deque Implementation in C++

The code for the implementation of deque in data structure in C++ is given below.

code:

// Deque implementation in C++

#include <iostream>
using namespace std;

#define MAX 10

class Deque {
  int arr[MAX];
  int front;
  int rear;
  int size;

   public:
  Deque(int size) {
    front = -1;
    rear = 0;
    this->size = size;
  }

  void insertfront(int key);
  void insertrear(int key);
  void deletefront();
  void deleterear();
  bool isFull();
  bool isEmpty();
  int getFront();
  int getRear();
};

bool Deque::isFull() {
  return ((front == 0 && rear == size - 1) ||
      front == rear + 1);
}

bool Deque::isEmpty() {
  return (front == -1);
}

void Deque::insertfront(int key) {
  if (isFull()) {
    cout << "Overflow\n"
       << endl;
    return;
  }

  if (front == -1) {
    front = 0;
    rear = 0;
  }

  else if (front == 0)
    front = size - 1;

  else
    front = front - 1;

  arr[front] = key;
}

void Deque ::insertrear(int key) {
  if (isFull()) {
    cout << " Overflow\n " << endl;
    return;
  }

  if (front == -1) {
    front = 0;
    rear = 0;
  }

  else if (rear == size - 1)
    rear = 0;

  else
    rear = rear + 1;

  arr[rear] = key;
}

void Deque ::deletefront() {
  if (isEmpty()) {
    cout << "Queue Underflow\n"
       << endl;
    return;
  }

  if (front == rear) {
    front = -1;
    rear = -1;
  } else if (front == size - 1)
    front = 0;

  else
    front = front + 1;
}

void Deque::deleterear() {
  if (isEmpty()) {
    cout << " Underflow\n"
       << endl;
    return;
  }

  if (front == rear) {
    front = -1;
    rear = -1;
  } else if (rear == 0)
    rear = size - 1;
  else
    rear = rear - 1;
}

int Deque::getFront() {
  if (isEmpty()) {
    cout << " Underflow\n"
       << endl;
    return -1;
  }
  return arr[front];
}

int Deque::getRear() {
  if (isEmpty() || rear < 0) {
    cout << " Underflow\n"
       << endl;
    return -1;
  }
  return arr[rear];
}

int main() {
  Deque dq(4);

  cout << "insert element at rear end \n";
  dq.insertrear(5);
  dq.insertrear(11);

  cout << "rear element: "
     << dq.getRear() << endl;

  dq.deleterear();
  cout << "after deletion of the rear element, the new rear element: " << dq.getRear() << endl;

  cout << "insert element at front end \n";

  dq.insertfront(8);

  cout << "front element: " << dq.getFront() << endl;

  dq.deletefront();

  cout << "after deletion of front element new front element: " << dq.getFront() << endl;
}

Output:

insert an element at the rear end 
rear element: 11
after deletion of the rear element, the new rear element: 5
insert an element at the front end 
front element: 8
after deletion of the front element new front element: 5

Explanation: We are going to perform the following operations in our deque in data structure in this code:

• isFull() : This function is used to check whether the deque in data structure is full or not.
• isEmpty() : This function is used to check whether the deque in data structure is empty or not.
• insertFront() : This function is used to insert an element at the front end of the deque in data structure
• insertRear() : This function is used to insert an element at the rear end of the deque in data structure
• deleteFront(): This function is used to delete elements from the front end of the deque in data structure
• deleteRear(): This function is used to delete elements from the rear end of the deque in data structure
• getFront(): This function is used to get or peek elements from the front end of the deque in data structure
• getRear(): This function is used to get or peek element from the rear end of the deque in data structure

Applications of the deque in data structure

There are innumerable applications of the deque in the data structure. It is vastly applied in most fields of computer science. Let us look into a few of them to understand their importance.

• Palindrome Checker: The string or a number that is the same when we read it from both forward and backward directions is known as a palindrome. Some of the examples of palindrome are “aba”, 121, 1001, etc. Our deque in data structure can be used to implement the program to check whether a number is a palindrome or not.
• Multiprocessor Scheduling: When multiple processes in a system are being carried out by multiple processors like CPU, or Core, at that time that system uses a multiprocessor scheduling algorithm. All the processors use our deque data structure to store all the different threads of processes. We also call this algorithm the A-Steal algorithm for scheduling.
• Deque can be also used for implementing both the stack and queue, and it supports both of their operations.
• Deque can be also used to store the history in the browser, or the browsing history
• Deque is widely implemented for the undo operations in software.

Equip yourself to tackle complex C++ projects with confidence. Enroll in C++ Data Structures Course by Scaler Topics now!

Conclusion

In this article, we learned about deque in data structure. Let us recap the points we discussed throughout the article:

• A data structure helps in organizing the data in a particular manner, such that we can efficiently perform numerous operations on them.
• A deque in data structure is a linear data structure, which stands for Double Ended Queue. In a deque, the data can be inserted and deleted from both front and rear ends.
• Unlike queue, deque in data structure doesn’t follow the FIFO rule (First in first out).
• There are two types of deque in data structure Input restricted queue and Output restricted queue
• In input restricted queue, the data can be inserted from only one end, while it can be deleted from both ends.
• In Output restricted queue, the data can be deleted from only one end, while it can be inserted from both ends.
• We usually implement deque in data structure using a circular array. As in a linear array implementation, if the array is full, no more elements can be inserted, and if we try to insert it will throw an “overflow message” error.
• In a deque in data structure we can perform operations like Insertion at front, Insertion at rear, Deletion at front, Deletion at rear.
• We can insert the element from the front end and the rear end of the deque.
• We can delete the element from the front end and the rear end of the deque.
• We can also check whether a deque is empty or full.
• We can also use the peek operation to get the front or rear element of the deque.
• We have also implemented deque in different programming languages like Java, Python, C, and C++.
• Applications of deque in data structure are like the undo operations, used in storing the browsing history, implementations of stack and queues, etc.