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 is a data structure that operates according to the FIFO (First-In-First-Out) principle, which states that whatever comes first will be sent out first. The front end or head of the queue is where deletion occurs, whereas the rear end of the tail is where insertion into the queue is performed.
The line for tickets outside a movie theater is an example of a queue in real life, where the person who enters first in the line receives the ticket first and the person who enters last in the line receives the ticket last.
What is a Deque or double ended queue in data structure
Double Ended Queue in data structures is what the deque stands for. Deque is a linear data structure in which operations such as insertion and deletion are carried out from opposite ends. Deque can be seen as a more inclusive variant of the queue.
A deque can have insertion and deletion operations conducted on both ends, but it does not adhere to the FIFO rule. The following is the depiction 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.