Data Structures
Deque (or, Double Ended Queue)
In Deque or Double Ended Queue, insertion and deletion can be done from both ends of the queue
either from the front or rear. It means that we can insert and delete elements from both front and rear
ends of the queue.
The representation of the deque is shown in the below image –
Operations performed on deque
There are the following operations that can be applied on a deque -
o Insertion at front
o Insertion at rear
o Deletion at front
o Deletion at rear
Insertion at the front end
In this operation, the element is inserted from the front end of the queue. Before implementing the
operation, we first have to check whether the queue is full or not. If the queue is not full, then the
element can be inserted from the front end by using the below conditions -
o If the queue is empty, both rear and front are initialized with 0. Now, both will point to the
first element.
o Otherwise, check the position of the front if the front is less than 1 (front < 1), then reinitialize
it by front = n - 1, i.e., the last index of the array.
Insertion at the rear end
In this operation, the element is inserted from the rear end of the queue. Before implementing the
operation, we first have to check again whether the queue is full or not. If the queue is not full, then
the element can be inserted from the rear end by using the below conditions -
o If the queue is empty, both rear and front are initialized with 0. Now, both will point to the
first element.
Page | 1
Data Structures
o Otherwise, increment the rear by 1. If the rear is at last index (or size - 1), then instead of
increasing it by 1, we have to make it equal to 0.
Deletion at the front end
In this operation, the element is deleted from the front end of the queue. Before implementing the
operation, we first have to check whether the queue is empty or not.
If the queue is empty, i.e., front = -1, it is the underflow condition, and we cannot perform the
deletion. If the queue is not full, then the element can be inserted from the front end by using the
below conditions -
If the deque has only one element, set rear = -1 and front = -1.
Else if front is at end (that means front = size - 1), set front = 0.
Else increment the front by 1, (i.e., front = front + 1).
Deletion at the rear end
In this operation, the element is deleted from the rear end of the queue. Before implementing the
operation, we first have to check whether the queue is empty or not.
If the queue is empty, i.e., front = -1, it is the underflow condition, and we cannot perform the
deletion.
If the deque has only one element, set rear = -1 and front = -1.
If rear = 0 (rear is at front), then set rear = n - 1.
Else, decrement the rear by 1 (or, rear = rear -1).
Page | 2
Data Structures
Implementation of deque
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#define size 5
int main()
{
int arr[size],R=-1,F=0,te=0,ch,n,i,x;
while(1)
{
//system("cls"); // for clearing the screen
printf("F=%d R=%d\n\n",F,R);
printf("1. Add Rear\n");
printf("2. Delete Rear\n");
printf("3. Add Front\n");
printf("4. Delete Front\n");
printf("5. Display\n");
printf("6. Exit\n");
printf("Enter Choice: ");
scanf("%d",&ch);
switch(ch)
{
case 1:
if(te==size)
{
printf("Queue is full");
getch(); // pause the loop to see the message
}
else
{
printf("Enter a number ");
scanf("%d",&n);
R=(R+1)%size;
arr[R]=n;
te=te+1;
}
break;
case 2:
if(te==0)
{
printf("Queue is empty");
getch(); // pause the loop to see the message
}
else
Page | 3
Data Structures
{
if(R==-1)
{
R=size-1;
}
printf("Number Deleted From Rear End = %d",arr[R]);
R=R-1;
te=te-1;
getch(); // pause the loop to see the number
}
break;
case 3:
if(te==size)
{
printf("Queue is full");
getch(); // pause the loop to see the message
}
else
{
printf("Enter a number ");
scanf("%d",&n);
if(F==0)
{
F=size-1;
}
else
{
F=F-1;
}
arr[F]=n;
te=te+1;
}
break;
case 4:
if(te==0)
{
printf("Queue is empty");
getch(); // pause the loop to see the message
}
else
{
printf("Number Deleted From Front End = %d",arr[F]);
F=(F+1)%size;
te=te-1;
getch(); // pause the loop to see the number
}
break;
case 5:
if(te==0)
{
printf("Queue is empty");
getch(); // pause the loop to see the message
}
else
{
x=F;
Page | 4
Data Structures
for(i=1; i<=te; i++)
{
printf("%d ",arr[x]);
x=(x+1)%size;
}
getch(); // pause the loop to see the numbers
}
break;
case 6:
exit(0);
break;
default:
printf("Wrong Choice");
getch(); // pause the loop to see the message
}
}
return 0;
}
Output
Page | 5
Data Structures
Page | 6