Updated March 13, 2023
Introduction to Deque in Data structure
Deque is one of the data structures, which is also called a double-ended queue in which insertion and deletion operations can be performed from both the front of the end and rear ends. Usually, when we talk about the queue, the front end is the one where all the delete operations are carried on while all the insertion operations take place from the rear end. But double-ended queues can perform delete and insert from both ends; that’s why it has got this name. Therefore, Deque is actually considered as the general version of the data structure named queue and is one of the linear data structures. In this article, we will study the working of the Deque and its implementation.
Working of Deque in Data structure
Deque has the special functionality that it can execute like a stack and queue as there is no restriction as to which end should be considered to perform insert and delete tasks. When both of these tasks are performed from the same end, it leads to the behavior of the LIFO rule, which is last in first out as followed by the stack data structure. Hence, we can implement the functionality of the stack using Deque. The following diagram shows the correct representation of stack behavior of Deque –
When we perform insertion from one end and deletion from the other, then the behavior of that data structure is that the item which is inserted first is also the one which will be deleted the first, which is the same as that of the FIFO rule that is first in first out. Hence, while executing this kind of functionality by Deque, it behaves like a queue data structure, proving that we can implement queues using Deque. For example, the following figure depicts the behavior of the queue using Deque.
There are two types of queues that can be implemented when using a double-ended queue, i.e. Deque. These are input restricted queues and output restricted queues.
input restricted queue
Input restricted queue is the one in which we can perform delete operation from the front as well as the rear end of Deque. However, the insertion operation can be performed from only one of its ends. The following figure depicts the input restricted queue behavior–
output restricted queue
The other type of queue, which is output restricted queue, is the one in which insertion can be done from any of the ends, but deletion can be done only from one of the ends, as shown in the below figure.
Operations on Double-ended queue (Deque) –
We can perform the following list of operations on the given Deque data structure –
- Insertion from front end
- Insertion from the rear end
- Deletion from front end
- Deletion from the rear end
There are many other than inset and delete functions like
- peek, which help us to get the element pointed currently by front, and the element pointed currently by the rear end in Deque.
- isFull() function is useful for determining that the particular size is the Deque completely occupied by all the elements for the given Deque. If Deque is completely occupied, it returns true else returns false.
- isEmpty() function works just the opposite of the isFull() function and determines whether the given stack of the Deque is completely empty or not. If it is empty, the function returns true; else false if there are any of the one characters in it.
Implementation of Deque
We can implement the double-ended queue data structure in two ways, either by using a doubly-linked list or by using the circular array data structures.
1. doubly linked list
The doubly linked list stores two things in each element it holds. It contains the value of the element and the address of the next element to which it points out as well as the address of the element prior to that element. Hence, the name doubly linked list. The below figure shows the sample of the doubly linked list –
2. Circular Array
On the other end, the circular array is just like the normal array in which the last element is connected and linked to the first element it holds. Hence, whenever we try to insert an element in the array when already the array is full, the element gets inserted in the first position if the first place is empty. This will not result in the overflow error condition as in the case of a normal array. The following figure generally represents how the circular array works internally for an array with 5 as the length –
Applications of Deque
The following are the most common scenarios where we make the use of Deque data structure –
- It is used in multiprocessor scheduling for implementing the steal algorithm.
- We can implement a stack as well as a queue by using Deque, which helps in using the same for undo and redo operations.
- It is used to implement a palindrome checker where we have to check whether the string is the same starting from both ends.
Implementation of Deque
When a Deque is created at that time, both the front and the rear point out to -1. The process of adding the new element in Deque is called an enqueue, while that of removing is called Deque.
1. Enqueue operation
Suppose that there is a single element that we have inserted in Deque. Hence, the front (f) will be pointing to 0, and the rear (r) will point to 0, as shown in the figure below.
Now, if we want to insert the element from the rear, then the value of the rear will change to 1 while the value of the front will still be 0 as shown –
In case if you want to add the value from the front, then the front will be decreased by 1 that is front = front -1, and as the front is already 0 in our case hence, it will become -1, which is not possible and thus lead to pointing to the last element of Deque where element gets added as shown –
2. Deque operation
The delete operation from the front involves incrementing the value of the front that is front = front + 1 as shown. If the front is already having the maximum length size of the array, then it points to zero deleting the last element as shown –
The Deque from rear involves decrementing rear by 1 that is rear = rear -1, and the result would be as shown below –
3. Practical Implementation
The below code implements the dequeue where we have created different functions for performing different operations on dequeue and called them from the main function. The names of the function are self-explanatory for the operation which they carry out –
#define size 5
#include <stdio.h>
int sampleDeque[size];
int f=-1, r=-1;
void insertFromFrontEnd(int x)
{
if((f==0 && r==size-1) || (f==r+1))
{
printf("Double Ended Queue is completely occupied ");
}
else if((f==-1) && (r==-1))
{
f=r=0;
sampleDeque[f]=x;
}
else if(f==0)
{
f=size-1;
sampleDeque[f]=x;
}
else
{
f=f-1;
sampleDeque[f]=x;
}
}
void insertFromReartEnd(int x)
{
if((f==0 && r==size-1) || (f==r+1))
{
printf("Double Ended Queue is completely occupied");
}
else if((f==-1) && (r==-1))
{
r=0;
sampleDeque[r]=x;
}
else if(r==size-1)
{
r=0;
sampleDeque[r]=x;
}
else
{
r++;
sampleDeque[r]=x;
}
}
void show()
{
int i=f;
printf("\nAll the elements in a double ended queue i.e. Deque: ");
while(i!=r)
{
printf("%d ",sampleDeque[i]);
i=(i+1)%size;
}
printf("%d",sampleDeque[r]);
}
void retrieveFrontValue()
{
if((f==-1) && (r==-1))
{
printf("Deque is empty");
}
else
{
printf("\nThe value of element pointed by front end is: %d", sampleDeque[f]);
}
}
void retrieveRearValue()
{
if((f==-1) && (r==-1))
{
printf("Deque is empty");
}
else
{
printf("\nThe value of the element pointed by rear end is: %d", sampleDeque[r]);
}
}
void deleteFromFrontEnd()
{
if((f==-1) && (r==-1))
{
printf("Deque is empty");
}
else if(f==r)
{
printf("\nThe deleted item is %d", sampleDeque[f]);
f=-1;
r=-1;
}
else if(f==(size-1))
{
printf("\nThe deleted item is %d", sampleDeque[f]);
f=0;
}
else
{
printf("\nThe deleted item is %d", sampleDeque[f]);
f=f+1;
}
}
void deleteFromRearEnd()
{
if((f==-1) && (r==-1))
{
printf("\nNothing is there in Deque to display");
}
else if(f==r)
{
printf("\nThe removed item is %d", sampleDeque[r]);
f=-1;
r=-1;
}
else if(r==0)
{
printf("\nThe removed item is %d", sampleDeque[r]);
r=size-1;
}
else
{
printf("\nThe removed item is %d", sampleDeque[r]);
r=r-1;
}
}
int main()
{
insertFromFrontEnd(2);
insertFromFrontEnd(1);
insertFromReartEnd(3);
insertFromReartEnd(5);
insertFromReartEnd(8);
show();
retrieveFrontValue();
retrieveRearValue();
deleteFromFrontEnd();
deleteFromRearEnd();
show();
return 0;
}
The output of the above code is as shown below: –
Conclusion – Deque in Data structure
We can make use of the Deque data structure to insert and delete the elements from either end of it, and it can be implemented by using the doubly linked list or circular array.
Recommended Articles
This is a guide to Deque in Data structure. Here we discuss the working of the Deque and its implementation along with the output. You may also have a look at the following articles to learn more –
