Last Updated on August 29, 2023 by Mayank Dham
We will study the data structure concept of dequeue or double ended queue in this article. Let’s first take a quick look at what a data structure is before we get started with the dequeue or double ended queue in data structures.
What is queue in data structure?
A queue represents a data structure that adheres to the principle of FIFO (First-In-First-Out), meaning that the item that enters first will be the first to exit. Deletion occurs at the front end or head of the queue, while insertion takes place at the rear end or tail. An instance of a queue in the real world can be observed in the line for tickets outside a movie theater. Here, the concept of a queue applies, as the individual who joins the line earliest is the one who obtains the ticket first, and the person who arrives last in line receives the ticket last.
What is a Deque or double ended queue in data structure
A deque, short for "double-ended queue," is a linear data structure that facilitates operations like insertion and deletion from both ends. It can be viewed as a broader version of a queue, offering increased flexibility. A deque permits the performance of insertion and deletion operations at both its front and rear ends, distinguishing it from adhering strictly to the FIFO principle. The following illustration represents the structure of a deque:
Types of deque
There are two types of deque –
- Input restricted queue
- Output restricted queue
Input restricted Queue
Only one end of an input-restricted queue may be used for insertion, but both ends can be used for deletion.
Output restricted Queue
Only one end of the output limited queue may be used for deletion operations, whereas both ends may be used for insertion operations.
Operations performed on deque
The operations that may be used on a deque are as follows:
- Insertion at front
- Insertion at rear
- Deletion at front
- Deletion at rear
Along with the overview of the previous, we can also execute peek operations in the deque. We may obtain the deque’s front and back components using the peek function. Therefore, in addition to the aforementioned procedures, deque additionally supports the following operations:
- Take the first item out of the deque
- Remove the rear item out of the deque
- Check if the queue is empty or not.
- Determines whether or not the queue is empty.
Let’s now use an example to comprehend the operation carried out on deque.
Insertion at the front end
The element is placed in this operation from the front of the queue. We must first determine if the queue is full or not before we can implement the operation. The following criteria can be used to insert the element from the front end if the queue is not full:
- Both the back and the front are initialized to 0 if the queue is empty. Both will now make a reference to the first element.
- Otherwise, if the front is less than 1 (front < 1), verify where it is located before reinitializing it using front = n – 1, or the final index of the array.
Insertion at the rear end
The element is placed in this operation from the back of the queue. We must confirm that the queue is not full once more before carrying out the procedure. The following criteria can be used to insert the element from the back end if the queue is not full:
- Both the the rear and the front are initialized to 0 if the queue is empty. Both will now make a reference to the first element.
- Otherwise, add one to the back. If the rear is at the final index (or size -1), we must make the rear equal to 0 rather than raising it by 1.
Deletion at the front end
The element is removed from the queue’s front end during this action. We must first determine if the queue is empty or not before we can implement the action.
We cannot conduct the deletion if the queue is empty, that is, if front = -1, which is the underflow condition. The following criteria can be used to insert the element from the front end if the queue is not full:
- Set the rear and front to -1 if the deque only has one element.
- Otherwise, set front = 0 if the front is at the end (meaning front = size – 1).
- In all other cases, raise the front by one (i.e., front = front + 1).
Deletion at the rear end
The element is removed from the back of the queue during this procedure. We must first determine if the queue is empty or not before we can implement the action.
We cannot conduct the deletion if the queue is empty, that is, if front = -1, which is the underflow condition.
- Set the rear and front to -1 if the deque only has one element.
- Set rear to n – 1 if rear = 0 (the rear is at the front).
- Otherwise, subtract 1 from the rear (or, rear = rear -1).
Check empty
The aim of this operation is to determine whether or not the deque is empty. When the front is equal to 1, the deque is empty.
Check full
To determine if the deque is full or not, this process is carried out. The deque is full if front = rear + 1 or if front = 0 and rear = n – 1.
All of the deque’s mentioned operations have an O(1), or constant, temporal complexity.
Applications of deque
- Deque supports both operations, therefore it may be used as a stack and a queue.
- Deque may be used as a palindrome checker, which signifies that the string would be the same if it were read from both ends.
Implementation of deque
Below is the code implementation of deque:
#include <stdio.h>
#define size 5
int deque[size];
int f = -1, r = -1;
// insert_front function will insert the value from the front
void insert_front(int x)
{
if((f==0 && r==size-1) || (f==r+1))
{
printf("Overflow");
}
else if((f==-1) && (r==-1))
{
f=r=0;
deque[f]=x;
}
else if(f==0)
{
f=size-1;
deque[f]=x;
}
else
{
f=f-1;
deque[f]=x;
}
}
// insert_rear function will insert the value from the rear
void insert_rear(int x)
{
if((f==0 && r==size-1) || (f==r+1))
{
printf("Overflow");
}
else if((f==-1) && (r==-1))
{
r=0;
deque[r]=x;
}
else if(r==size-1)
{
r=0;
deque[r]=x;
}
else
{
r++;
deque[r]=x;
}
}
// display function prints all the value of deque.
void display()
{
int i=f;
printf("\nElements in a deque are: ");
while(i!=r)
{
printf("%d ",deque[i]);
i=(i+1)%size;
}
printf("%d",deque[r]);
}
// getfront function retrieves the first value of the deque.
void getfront()
{
if((f==-1) && (r==-1))
{
printf("Deque is empty");
}
else
{
printf("\nThe value of the element at front is: %d", deque[f]);
}
}
// getrear function retrieves the last value of the deque.
void getrear()
{
if((f==-1) && (r==-1))
{
printf("Deque is empty");
}
else
{
printf("\nThe value of the element at rear is %d", deque[r]);
}
}
// delete_front() function deletes the element from the front
void delete_front()
{
if((f==-1) && (r==-1))
{
printf("Deque is empty");
}
else if(f==r)
{
printf("\nThe deleted element is %d", deque[f]);
f=-1;
r=-1;
}
else if(f==(size-1))
{
printf("\nThe deleted element is %d", deque[f]);
f=0;
}
else
{
printf("\nThe deleted element is %d", deque[f]);
f=f+1;
}
}
// delete_rear() function deletes the element from the rear
void delete_rear()
{
if((f==-1) && (r==-1))
{
printf("Deque is empty");
}
else if(f==r)
{
printf("\nThe deleted element is %d", deque[r]);
f=-1;
r=-1;
}
else if(r==0)
{
printf("\nThe deleted element is %d", deque[r]);
r=size-1;
}
else
{
printf("\nThe deleted element is %d", deque[r]);
r=r-1;
}
}
int main()
{
insert_front(200);
insert_front(100);
insert_rear(300);
insert_rear(500);
insert_rear(800);
display(); // Calling the display function to retrieve the values of deque
getfront(); // Retrieve the value at front-end
getrear(); // Retrieve the value at rear-end
delete_front();
delete_rear();
display(); // calling display function to retrieve values after deletion
return 0;
} Conclusion:
This article taught us what is the queue definition in data structure, double ended queue in data structures, and define queue in data structure, we hope this blog will clarify all your doubts and give you a prior knowledge of queues and double ended queue in data structures.
FAQs related to What is Double-Ended Queue in Data Structure
Below are some of the FAQs related to What is Double ended queue om Data Structure:
1. How does a deque differ from a regular queue?
While both a queue and a deque are linear data structures, a deque supports operations at both ends (front and back) for insertion and deletion, unlike a regular queue which follows the First-In-First-Out (FIFO) order.
2. What are the main operations supported by a deque?
A deque supports several fundamental operations, including insertion from both ends, deletion from both ends, and methods to check if it’s empty or full.
3. Where are double-ended queues useful?
Deques are useful in scenarios where you need to efficiently manipulate data from both ends, such as implementing algorithms involving sliding windows, palindrome checking, and managing data in real-time streaming applications.
4. How is a deque implemented?
Deques can be implemented using arrays or linked lists. Depending on the requirements and constraints, different implementations may be more suitable.
5. Can a deque be empty or full?
Yes, a deque can be both empty and full. It’s important to check these states before performing insertions or deletions to prevent errors.