What Is Deque in Data Structure?
Deque is a more generalized version of a linear queue. As you know, the
linear queue has some restrictions while performing the insertion and
deletion of elements. The insertion in a linear queue must happen from
the rear end and deletion from the front end. But, in deque, you can
perform both insertion and deletion operations at both of its ends. That’s
why it is called a Double-Ended Queue (Deque).
The image above represents how different operations take place at both
ends of the deque.
What Is Deque in Data Structure?
Deque is a more generalized version of a linear queue. As you know, the
linear queue has some restrictions while performing the insertion and
deletion of elements. The insertion in a linear queue must happen from
the rear end and deletion from the front end. But, in deque, you can
perform both insertion and deletion operations at both of its ends. That’s
why it is called a Double-Ended Queue (Deque).
The image above represents how different operations take place at both
ends of the deque.
Properties of Deque
Now, you will look into the primary properties of deque in a data structure.
A deque can perform both the insertion and deletion using the LIFO
(Last In First Out) principle.
The insertion and deletion in deque can be limited to one node. When you
do that, the deque becomes a stack. Hence, it follows the Last In First Out
Principle for insertion and deletion.
As shown in the image above, initially, there were four elements inside
this deque. However, after repeating the removal of an element twice,
data elements 2 and 12 get removed from the deque, respectively. You
inserted element 2 at last and removed it at first. This example
demonstrates the LIFO principle.
A Deque can perform insertion and deletion operations using the FIFO
(First In First Out) principle.
As deque can operate on both ends, you can extract queue properties by
limiting insertion at the front node and removal at the rear node. Doing
this will allow deque to act as a linear queue.
As shown in the image above, the element which enters at first will also
leave the queue first. This is how deque can use the FIFO principle to
perform insertion and deletion.
Types of Deque in Data Structure
There are two types of deque which are created by restricting certain
operations. Let’s clearly understand them.
Input-Restricted Deque: It is a deque with some limitations while
performing insertion operations. In the Input-Restricted Deque, it will
perform the deletion at both ends, whereas it performs the insertion at
only one end. The image below shows how input restricted deque limits
insertion at one end.
Output-Restricted Deque: It is a deque with some limitations while
performing deletion operations. In the Output-Restricted Deque, it will
perform the insertion at both ends, whereas it performs the deletion of
elements at only one end. The image below shows how output
restricted deque limits removal at one end.
Operations on Deque
Four basic operations are performed on deque, they are as follows:
Insertion at Rear
Insertion at Front
Deletion at Front
Deletion at Rear
Along with these primary operations, you can also perform isEmpty(),
isFull() and Peek() operations. These operations are called supportive
queue operations. But, in this tutorial, you will only implement primary
queue operations. The time required to implement all these functions
must be constant, i.e., time-complexity = O(1).
Implementation of Deque
As mentioned previously, you will implement four main primary deque
operations as listed below:
front_Enqueue(int z): Inserts element using front node in a deque
rear_Enqueue(int z): Inserts element using rear node in a deque
front_Dequeue(): Removes element using front node in a deque
rear_Dequeue(): Removes element using rear node in a deque
You will use the C programming language to implement deque in data
structure using a circular array (Queue).
#include<stdio.h>
#include<iostream>
//Global scope
#define size 5
int dq[100];
int front = -1, rear =-1;
//Insertion from front
void front_Enqueue(int z)
{
if((front==0 && rear==size-1) || (front==rear+1))
{
printf("deque is full, Insertion is not possible");
}
else if((front==-1) && (rear==-1))
{
front=rear=0;
dq[front]=z;
}
else if(front==0)
{
front=size-1;
dq[front]=z;
}
else
{
front=front-1;
dq[front]=z;
}
}
// insertion from rear end
void rear_Enqueue(int z)
{
if((front==0 && rear==size-1) || (front==rear+1))
{
printf("deque is full");
}
else if((front==-1) && (rear==-1))
{
rear=0;
dq[rear]=z;
}
else if(rear==size-1)
{
rear=0;
dq[rear]=z;
}
else
{
rear++;
dq[rear]=z;
}
}
//function to analyze state of queue.
void display()
{
int i=front;
printf("\n Elements inside the double ended queue are : ");
while(i!=rear)
{
printf("%d ",dq[i]);
i=(i+1)%size;
}
printf("%d",dq[rear]);
}
void front_Dequeue()
{
if((front==-1) && (rear==-1))
{
printf("There is no element to delete inside a deque");
}
else if(front==rear)
{
printf("\nThe deleted element from the front is %d", dq[front]);
front=-1;
rear=-1;
}
else if(front==(size-1))
{
printf("\nThe deleted element from the front is %d", dq[front]);
front=0;
}
else
{
printf("\nThe deleted element from the front is %d", dq[front]);
front=front+1;
}
}
// dequeue_rear() function deletes the element from the rear
void rear_Dequeue()
{
if((front==-1) && (rear==-1))
{
printf("Deque is empty");
}
else if(front==rear)
{
printf("\nThe deleted element from rear is %d", dq[rear]);
front=-1;
rear=-1;
}
else if(rear==0)
{
printf("\nThe deleted element from the rear node is %d", dq[rear]);
rear=size-1;
}
else
{
printf("\nThe deleted element from rear node is %d", dq[rear]);
rear = rear-1;
}
}
int main()
{
front_Enqueue(-5);
front_Enqueue(23);
rear_Enqueue(17);
rear_Enqueue(12);
rear_Enqueue(47);
display();
front_Dequeue();
rear_Dequeue();
display();
return 0;
}
The display() function implemented in this program is an additional
function that you have to implement to visualize the state of a deque. The
image given below is the output that you will receive after running this
code in a compiler.