Circular Queue
The efficient representation of
Queue is Circular Queues. This method is
used to arrange the element in circular fashion. This type of queue is called Circular
Queue. Here the elements will be in the
form of Q[0………n-1] where Q[0] is adjacent to Q[1], Q[1] is adjacent to Q[2] and
so on and Q[n-2] is adjacent to Q[n-1] and Q[n-1] is adjacent to Q[0]. Here ‘n’
is the maximum No. of elements. Circular
Queue is represented as follows:
Role of Front and
Rear
We represent Front by ‘F’ and Rear
by ‘R’. Here ‘F’ always points to one position
counter clockwise from the first element and ‘R’ will point to the last element
that is inserted in the Circular Queue. Further when circular queue is empty
F=R=0.
To insert an element into the
circular queue first we have to check the present value of ‘R’. if R= n-1 then new value of ‘R’ is 0. Otherwise new value of ‘R’ is R=R+1. After incrementing ‘R’ value, if F=R then
Circular Queue is full and hence new element cannot be inserted. If F is not equal to R then insert a new
element at Q[R]. The maximum No. of
element that can be stored in circular queue of size n is n-1. Thus one location is left empty always in
circular queues.
Similarly, to delete an element from
circular queues first we have to check the present value of ‘F’. if F=R then Circular Queue is empty and hence
deletion cannot be performed. Otherwise we
delete the element either by incrementing F or resetting F. if F= n-1 the new value of ‘F’ is 0 otherwise
new value of ‘F’ is F=F+1.
Consider an Example of circular queue
Function
to Store an element in Queue
CQInsert(int
x)
{
If (r==n-1)
{
r=0;
}
else
{
r=r+1;
}
if (r=f)
{
printf(“Circular Queue is Full”);
}
else
{
Q[r]=x;
}
}
Int
CQdelete()
{
int n;
if(f==r)
{
printf(“Circular Queue is Empty”);
}
elseif (f == n-1)
{
f=0;
n=Q[f];
}
else
{
f=f+1;
n=Q[f];
}
return n;
}
C
Program which depicts Circular Queue
int r=0,f=0,max=4;
int Q[4];
void main()
{
int n;
int choice;
void dispCQueue();
void CQinsert();
int CQdelete();
clrscr();
while(1)
{
clrscr();
printf("1 CQinsert\n");
printf("2 CQdelete\n");
printf("3 dispCQueue\n");
printf("4 exit\n");
printf("enter choice: ");
scanf("%d",&choice);
switch(choice)
{
case
1:CQinsert();
printf("press any key to continue");
getch();
break;
case
2:n=CQdelete();
printf("Deleted Element =%d\n",n);
printf("press any key to continue");
getch();
break;
case
3:dispCQueue();
printf("press any key to continue");
getch();
break;
case
4:exit(0);
break;
default:printf("invalid choice\n");
printf("press any key to continue");
getch();
}
}
}
void
dispCQueue()
{
int i;
if(f==max-1)
{
for(i=0;i<=r;i++)
{
printf("%d ", Q[i]);
}
}
else if(f>r)
{
for(i=f+1;i<=max-1;i++)
{
printf("%d ", Q[i]);
}
for(i=0;i<=r;i++)
{
printf("%d ",Q[i]);
}
}
else if(r>f)
{
for(i=f+1;i<=r;i++)
{
printf("%d ", Q[i]);
}
}
}
void CQinsert()
{
int n;
if(r==max-1)
{
r=0;
}
else
{
r=r+1;
}
if(r==f)
{
printf("CQueue is full\n");
r=max-1;
}
else
{
printf("enter element into
CQueue\n");
scanf("%d",&n);
Q[r]=n;
}
}
int CQdelete()
{
int n;
if(f==max-1)
{
f=0;
}
else if(f==r)
{
printf("CQueue is
empty\n");
return 0;
}
else
{
f=f+1;
}
n=Q[f];
return n;
}
|
No comments:
Post a Comment