Deque – All That You Need To Know
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.
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.
You can also explore: Queue Data Structure: Types, Implementation, Applications
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:
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
Best-suited Data Structures and Algorithms courses for you
Learn Data Structures and Algorithms with these high-rated online courses
Types of Deque
Deque has two variants which are as follows:
- Input-restricted Deque
- 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.
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.
Operations on Deque
There are mainly four basic operations that can be performed on deque, which are as follows:
- insertFront()
- insertRear()
- deleteFront()
- deleteRear()
Other operations that can be performed are:
- getFront()
- getRear()
- isEmpty()
- 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:
- Check the front of the queue.
- If front<1, then front = n-1.
- Else, front–;
- 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:
- Check whether the queue is full or not.
- If rear is full, then rear = 0.
- Else, front++;
- 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:
- Check if the queue is empty.
- If the deque is empty front = -1, deletion can’t be done. [underflow]
- If the deque has only one element front== rear, then front = -1 and rear = -1
- Else, if front= n-1, then front=0;
- 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:
- Check if the queue is empty.
- If the deque is empty front = -1, deletion can’t be done. [underflow]
- If the deque has only one element front== rear, then front = -1 and rear = -1
- Else, if rear=0, then rear= n-1;
- 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; } }
You must also explore: 8 Most Important Data Structures Every Programmer Must Know
Applications of Deque:
- Deque supports both stack and queue operations.
- It can be used to store web browser history.
- It can be used in job scheduling algorithms.
- In undo operations.
Author: Kanika Joshi
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
Top Picks & New Arrivals
