Deque – All That You Need To Know

Deque – All That You Need To Know

4 mins read387 Views Comment
clickHere
Updated on Feb 23, 2023 18:18 IST

In this article, we will discuss “Deque” or “Double-ended queue” in great detail. But before exploring what a Deque data structure is, let’s first explore what a queue data structure is.

2022_12_MicrosoftTeams-image-194.jpg

The queue data structure in computer programming plays a very important role in organizing data efficiently, queue data structure follows the FCFS approach to organizing data, it is a collection of data elements in which each element is served based on a first come first serve basis. The queue data structure has various queue types, such as Simple queue, Circular queue, Priority queue, Double-ended queue or Deque.

In this article, we will learn what a deque is, its types, implementation, and operations performed, and finally, we will see some of its applications.

What is Deque?

Deque or double-ended queue is a special type of queue in the data structure, it can perform insertion and deletion or enque and deque operations at both ends of the queue. In a traditional queue, insertion is done from one end known as a rear-end or tail and deletion is done from another end known as a front end or head. 

Also explore: Data Structures and Algorithms Online Courses & Certifications

Whereas, In deque both the operation of deletion and insertion of elements can be performed from either side. Therefore, it is named the double-ended queue. Deque is also said as a generalized version of the queue. 

Representation of Deque:

The figure shows a Deque data structure.

In the above queue, both enque and deque operations can be performed at both ends of the queue. 

You can also explore: Difference between Stack and queue

Types of Deque

Deque has two variants which are as follows:

  1. Input-restricted Deque
  2. Output-restricted Deque

Also Read: Top Data Structure Interview Questions [DS and Algorthims]

Input-restricted Deque

In input-restricted deque, deletion operation can be performed at both ends but insertion can be done at one end only. This queue is useful when an item is needed to remove from the rear end of the queue. 

The figure shows an input-restricted deque.

Output-restricted Deque

In output-restricted deque, insertion operation can be performed at both ends but deletion can be done at one end only. This queue is useful when an item is needed to insert an element at the front of the queue. 

The figure shows an output-restricted deque

Operations on Deque

There are mainly four basic operations that can be performed on deque, which are as follows:

  1. insertFront()
  2. insertRear()
  3. deleteFront()
  4. deleteRear()

Other operations that can be performed are:

  1. getFront()
  2. getRear()
  3. isEmpty()
  4. isFull()

insertFront(): 

This operation is used to insert an item in the front. Before using insertFront() operation, we need to check if the queue is full or not. If the queue has space, then we can insert the element in the front of the queue. 

Algorithm:

  1. Check the front of the queue.
  2. If front<1, then front = n-1. 
  3. Else, front–;
  4. Insert the element to the front. 

insertRear():

This operation is used to insert an item in the rear. Before using insertRear() operation, we need to check if the queue is full or not. If the queue has space, then we can insert element in the rear of the queue. 

Algorithm:

  1. Check whether the queue is full or not.
  2. If rear is full, then rear = 0. 
  3. Else, front++;
  4. Insert the element to rear. 

deleteFront():

This operation is used to delete an item in the front. Before using deleteFront() operation, we need to check whether the queue is empty or not. 

Algorithm:

  1. Check if the queue is empty.
  2. If the deque is empty front = -1, deletion can’t be done. [underflow]
  3. If the deque has only one element front== rear, then front = -1 and rear = -1 
  4. Else, if front= n-1, then front=0;
  5. Else, front = front+1. 

deleteRear():

This operation is used to delete an item in the rear end. Before using the deleteRear() operation, we need to check whether the queue is empty or not. 

Algorithm:

  1. Check if the queue is empty.
  2. If the deque is empty front = -1, deletion can’t be done. [underflow]
  3. If the deque has only one element front== rear, then front = -1 and rear = -1 
  4. Else, if rear=0, then rear= n-1;
  5. Else, rear = rear-1. 

getFront():

This operation is used to retrieve the element present in the front end of the queue. 

getRear():

This operation is used to retrieve the element present at the rear end of the queue.

isEmpty():

This operation is used to check whether the queue is empty or not. 

isFull():

This operation is used to check whether the queue is full or not. 

Implementation of Deque

 
int main()
{
insert_front(30);
insert_front(40);
insert_rear(10);
insert_rear(80);
insert_rear(20);
insert_rear(50);
display();
getfront();
delete_front();
getrear();
delete_rear();
display();
return 0;
}
#include <stdio.h>
#define size 6
int deque[size];
int front = -1, rear = -1;
void insert_front(int x)
{
if((front==0 && rear==size-1) || (front==rear+1))
{
printf(“Overflow”);
}
else if((front==-1) && (rear==-1))
{
front=rear=0;
deque[front]=x;
}
else if(front==0)
{
front=size-1;
deque[front]=x;
}
else
{
front=front-1;
deque[front]=x;
}
}
void insert_rear(int x)
{
if((front==0 && rear==size-1) || (front==rear+1))
{
printf(“Overflow”);
}
else if((front==-1) && (rear==-1))
{
rear=0;
deque[rear]=x;
}
else if(rear==size-1)
{
rear=0;
deque[rear]=x;
}
else
{
rear++;
deque[rear]=x;
}
}
void display()
{
int i=front;
printf(“\n Elements present in deque are:);
while(i!=rear)
{
printf(%d “,deque[i]);
i=(i+1)%size;
}
printf(%d”,deque[rear]);
}
void getfront()
{
if((front==-1) && (rear==-1))
{
printf(“Deque is empty”);
}
else
{
printf(“\n Front element’s value is: %d”, deque[front]);
}
}
void getrear()
{
if((front==-1) && (rear==-1))
{
printf(“Deque is empty”);
}
else
{
printf(“\nRear element’s value is %d”, deque[rear]);
}
}
void delete_front()
{
if((front==-1) && (rear==-1))
{
printf(“Deque is empty”);
}
else if(front==rear)
{
printf(“\nDeleted element is: %d”, deque[front]);
front=-1;
rear=-1;
}
else if(front==(size-1))
{
printf(“\nDeleted element is: %d”, deque[front]);
front=0;
}
else
{
printf(“\nDeleted element is: %d”, deque[front]);
front=front+1;
}
}
void delete_rear()
{
if((front==-1) && (rear==-1))
{
printf(“Deque is empty”);
}
else if(front==rear)
{
printf(“\n Deleted element is: %d”, deque[rear]);
front=-1;
rear=-1;
}
else if(rear==0)
{
printf(“\nDeleted element is: %d”, deque[rear]);
rear=size-1;
}
else
{
printf(“\nThe deleted element is %d”, deque[rear]);
rear=rear-1;
}
}
Copy code

You must also explore: 8 Most Important Data Structures Every Programmer Must Know

Applications of Deque:

  1. Deque supports both stack and queue operations.
  2. It can be used to store web browser history.
  3. It can be used in job scheduling algorithms.
  4. In undo operations.

Author: Kanika Joshi

About the Author

This is a collection of insightful articles from domain experts in the fields of Cloud Computing, DevOps, AWS, Data Science, Machine Learning, AI, and Natural Language Processing. The range of topics caters to upski... Read Full Bio