DEQUES (Double Ended
Queues)
A Deque is a linear list in where in
insertions and deletions are performed from both the ends i.e., insertions can
be performed from both front and rear ends. Similarly, deletions can also be performed
from both ends i.e., both front and rear.
Front is always one less than the
actual front of the queue and rare always points to rare most element in the
queue. Here Front is denoted as ‘F’, rear is denoted as ‘R’ and maximum no. of
element is ‘n’.
Insertion
from Rear End
If
R=n then we cannot insert the element from the rear end, since rear most
element is occupied. If R !=n then we
can insert the element by incrementing R by 1 and storing the element at Q[R].
Insertion
from Front End
When Deque is empty it doesn’t
matter from which end insertion is performed i.e., when the Deque is empty F=R,
always R is incremented by 1 and then new element is stored at Q[R].
If F=0 then new element cannot be
inserted from front end, since front most element is occupied. Otherwise we
decrement the F by 1 at stores new element at Q[F].
Deletion
from Rear End
If Deque is empty we cannot perform
deletion otherwise we decrement R by 1 to delete rear most element.
Deletion
from Front End
If Deque is empty we cannot perform
deletion otherwise we increment F by 1 to delete front element.
|
|
Front
|
Rear
|
|
Insertion
|
F=F-1
|
R=R+1
|
|
Deletion
|
F=F+1
|
R=R-1
|
Consider
an example
|
F=R=0
|
|
|
|
|
|
|
|
|
|
|
|
DeQueue is empty
|
F=0
|
10
|
|
|
|
|
|
R=1
|
|
|
|
|
Insert 10
|
F=0
|
10
|
20
|
|
|
|
|
|
R=2
|
|
|
|
Insert 20
|
F=0
|
10
|
20
|
30
|
|
|
|
|
|
R=3
|
|
|
Insert 30
|
F=0
|
10
|
20
|
30
|
40
|
|
|
|
|
|
R=4
|
|
Insert 40
|
|
|
20
|
30
|
40
|
|
|
F=0
|
|
|
R=4
|
|
Delete 10
|
|
|
|
30
|
40
|
|
|
|
F=1
|
|
R=4
|
|
Delete 20
|
|
|
50
|
30
|
40
|
|
|
F=0
|
|
|
R=4
|
|
Insert 50 at front
|
F=0
|
60
|
50
|
30
|
40
|
70
|
|
|
|
|
R=4
|
F=5
|
Insert 60 at front
|
F=0
|
60
|
50
|
30
|
40
|
|
|
|
|
|
R=4
|
|
Insert 70 at front
|
|
60
|
50
|
30
|
|
|
|
|
|
R=3
|
|
|
Delete 50 at Rear
InsertRear(int
x)
{
If (r==n-1)
{
printf(“Insertion cannot be performed
from rear end”);
}
else
{
r=r+1;
Q[r]=x;
}
}
InsertFront(int
x)
{
If (f==r)
{
r=r+1;
Q[r]=x;
}
If (f==-1)
{
printf(“insertion cannot be performed
from front end”);
}
else
{
f=f-1;
Q[f]=x;
}
}
int
DeleteRear()
{
int n;
If (f==r)
{
printf(“Deque is empty”);
}
else
{
n= Q[r];
r=r-1;
}
return n;
}
int
DeleteFront()
{
int n;
if (f==r)
{
printf(“Deque is empty”);
}
else
{
f=f+1;
n=Q[f];
}
return n;
}
C
Program which demonstrates Deque using menus
#define max 5
int r=-1,f=-1,Q[max];
void main()
{
int choice,n;
void rearinsert();
void dispDQueue();
int reardelete();
void frontinsert();
int frontdelete();
clrscr();
while(1)
{
clrscr();
printf("DQueue Program
Demonstration\n");
printf("1. Rear Insert\n");
printf("2. Rear Delete\n");
printf("3. Display DQueue\n");
printf("4. Front Insert\n");
printf("5. Front Delete\n");
printf("6. Exit\n");
printf("Enter Choice : ");
scanf("%d",&choice);
switch(choice)
{
case 1:{
rearinsert();
printf("Press any
key to continue");
getch();
break;
}
case 2:{
n=reardelete();
printf("Deleted Element =%d\n",n);
printf("Press any key to continue");
getch();
break;
}
case 3:{
dispDQueue();
printf("Press any key to continue");
getch();
break;
}
case 4:{
frontinsert();
printf("press any key to continue");
getch();
break;
}
case 5:{
n=frontdelete();
printf("Deleted Element =%d\n",n);
printf("press any key to continue");
getch();
break;
}
case 6:{
exit(0);
break;
}
default:{
printf("invalid choice\n");
printf("Press any key to
continue");
getch();
}
}
}
}
void dispDQueue()
{
int i;
if(r>f)
{
for(i=f+1;i<=r;i++)
{
printf("%d ",Q[i]);
}
}
else if(f>r)
{
for(i=r+1;i<=f;i++)
{
printf("%d ",Q[i]);
}
}
}
void rearinsert()
{
int n;
if(r==max-1)
{
printf("DQueue is full.insertion
can not be performed\n");
}
else
{
r=r+1;
printf("enter element to
DQueue\n");
scanf("%d",&n);
Q[r]=n;
}
}
int reardelete()
{
int n;
if(r==f)
{
printf("DQueue is empty. delation
can not be performed\n");
}
else
{
n=Q[r];
r=r-1;
}
return n;
}
void frontinsert()
{
int n;
if (f==r)
{
r=r+1;
printf("enter a element in
Dqueue-1");
scanf("%d",&n);
Q[r]=n;
}
else if(f==-1)
{
printf("insertion cannot be
performed from front end\n");
}
else
{
printf("Enter a element into
DQueue-2\n");
scanf("%d",&n);
Q[f]=n;
f=f-1;
}
}
int frontdelete()
{
int n;
if(f==max-1)
{
printf("DQueue is empty");
}
else if(f==r)
{
printf("DQueue is empty");
}
else
{
f=f+1;
n=Q[f];
}
return n;
}
No comments:
Post a Comment