Circular Queue:
If Simple Queue have a single element at its last position i.e (size-1) and if we try to insert a new element than simple queue gives message " Queue is Full " , But almost queue is empty.
For overcoming this drawback we use Circular Queue.
Necessary Conditions for Circular Queue
Condition 1:
if (F=-1 and R==-1)
{
printf ("Queue is empty");
}
Condition 2:
if ( F==R ! =-1)
{
print ("Queue has a single element");
}
Condition 3:
if (R==size-1)
{
if (F==0)
{
printf ("Queue is Full");
}
OR
if (R+1==F)
{
printf ("Queue is Full");
}
}
Insertion:
Suppose we have any circular queue of size 6. Now queue is empty there is no element in queue.This is the pictorial represent of queue.
Now we want to insert elements in queue such as x = 10,20,30,40,50,60,70 size = 7
size-1=6
R=-1 , F=-1
Insert x=10
Now first check the condition if (R==size-1) which is false because R=-1 than control reach the condition if (R==-1) which is true than F=0 & R=0 and queue[R]=x. That mean the first element i.e 10 is inserted into circular queue at 0th location and now R=0 & F=0.
Insert x=20
Again check the condition if (R== size-1) which is false because R=0 than control check the next condition which is if (R==-1) which is false, Now control reaches the next step which is R++ or R=R+1 and queue[R]=x That mean the second element i.e 20 is inserted into circular queue at 1st location and R=1 & F=0
In the same way we insert the remaining elements into the queue.such as:
Procedure for Inserting element in Circular Queue:
void insert_cq(int x)
{
if(R==size-1)
{
if(F==0)
{
printf("Queue Overflow Occur");
}
else
{
R=0;
queue[R]=x;
}
}
else
{
if(R==-1)
{
F=0;
R=0;
queue[R]=x;
}
else
{
if(R+1==F)
{
printf("Queue Overflow Occur");
}
else
{
R++;
queue[R]=x;
}
}
}
}
Deletion:
For perform deletion in circular queue
First we check the condition if (F==-1) which is false because F=0. than check the next condition which is if (F==R) which is false (because F=0 & R=6), than control reach the next step which is x=queue[F] ( Deleting the F=0 i.e 0th element of queue), increment F by 1. Now F point to 1st i.e F=1.
Deleted Element -10
Again check the condition (F==-1) which is false (Because F=1) , than check the next condition which is if (F==R) , which is false ( Because F=1 & R=6), than control reaches the next step which x=queue[F] ( Deleting the F=1 , 1st element in queue),increment F by 1. Now F point to 1st i.e F=2.
Deleted Element -20
Same process is done for remaining element .
Finally one situation come when R=F then just delete element and R=-1 & F=-1
Now the queue become empty.
Procedure for Deleting element from Circular Queue:
int delete_cq()
{
int x=0;
if(F==-1)
{
printf("Queue underflow\n");
}
else
{
if(F==R)
{
x=queue[F];
F=-1;
R=-1;
}
else
{
x=queue[F];
F++;
if(F==size)
{
F=0;
}
}
}
return(x);
}
Complete Program For Insertion & Deletion in Circular Queue:
#include <stdio.h>
#include <conio.h>
#define size 50
int queue[size];
int R=-1,F=-1;
void insert_cq(int x)
{
if(R==size-1)
{
if(F==0)
{
printf("Queue Overflow Occur");
}
else
{
R=0;
queue[R]=x;
}
}
else
{
if(R==-1)
{
F=0;
R=0;
queue[R]=x;
}
else
{
if(R+1==F)
{
printf("Queue Overflow Occur");
}
else
{
R++;
queue[R]=x;
}
}
}
}
void display()
{
if(R==-1 && F==-1)
{
printf("Now Queue is empty!\n");
}
else
{
printf("Elements of queue are:");
for(int i=F;i<=R;i++)
{
printf("|%d|",queue[i]);
}
}
}
int delete_cq()
{
int x=0;
if(F==-1)
{
printf("Queue underflow\n");
}
else
{
if(F==R)
{
x=queue[F];
F=-1;
R=-1;
}
else
{
x=queue[F];
F++;
if(F==size)
{
F=0;
}
}
}
return(x);
}
void main()
{
int x,ch=1;
do{
if(ch==1)
{
printf("Enter Element of Queue:");
scanf("%d",&x);
insert_cq(x);
display();
printf("\n");
}
printf("Do you want to insert element in Circular Queue:0-Exit, 1-Insert, 2-Delete:");
scanf("%d",&ch);
if(ch==2)
{
int d=delete_cq();
printf("%d is deleted element\n",d);
display();
printf("\n");
}
}while(ch!=0);
getch();
}
Out Put:
No comments:
Post a Comment