Circular Queue (implementation with Arrays ) Along With Program Code

Circular Queue

Circular Queue uses memory quite efficiently when compared with Linear Queue because in Linear Queue even if there are empty spaces at the front in the queue, it will display “Queue Full” message if the rear pointer reaches at the end of the queue. Circular queue is assumed to be circular array as shown in Figure 1. Initially, both subscripts rear and front are set to -1.

When first element is added, rear is incremented by 1 (i.e. it is set to 0), and the element is added as the 0th element. According to the property of the circular queue, the front and rear both subscripts points at the first element added as shown in Figure 2.

Now onwards every element is added with the help of rear subscript and deletion is done with the help of front subscript. On adding four more values, the rear index is incremented every time and the value is added at rear index location as shown in Figure 3. Remember, the front subscript is left at its original location i.e. it still points at the first element of the circular queue.

On adding one more element, the circular queue will reach its maximum limit and the rear index will be just behind the front index as shown in Figure 4. If the queue reaches its maximum limit and we  try to add one more element, without deleting any element, the value of subscript rear will become 0. Why?

Because above circular queue is of 6 elements, we apply the formula “rear+1%6” where % is the mod function which returns remainder after dividing by 6. Since at 0th location, already there is subscript front, so the message “Sorry, the Circular queue is full” is displayed.

But, if any element from the circular array is erased, the value is removed from the front subscript and the front subscript is incremented to the next element as shown in Figure 5.

Now, if any new element is to be added, the value of subscript rear is set to 0 (because of rear+1%6), and at the 0th location, there is no subscript front, so the new element can be added at 0th position as shown  in Figure 6.

Note: To, make rear index revolve around the array, its value should become 0 after reaching the maximum length of queue (array). This is done with the help of % (mod) operator. Consider the maximum size of queue is 6 elements, we use the formula (r+1)%6. By this formula, when the rear (r) index reaches, 5 and a new element is to be added, it will become 0 (because (5+1)%6=0).

Circular queues are implemented using arrays because of optimum utilization of memory space.

C Program for implementing Circular Queue Using Arrays

/* Implementing Circular Queue with Arrays */
/* circularqueuearr.c */

# include<stdio.h>
#define max 5
int cqueue[max];

main()
{
int rear,front,n=0,j,value;
rear=front=-1;
while(n!=3)
{
printf(“\n\nCircular Queue\n”);
printf(“1………Add an element into the circular queue\n”);
printf(“2………Delete an element from the circular queue\n”);
printf(“3………Quit\n”);
printf(“Enter your choice 1/2/3: “);
scanf(“%d”,&n);
switch(n)
{
case 1: printf(“Enter the value to add: “);
scanf(“%d”,&value);
addq(&front,&rear,value);
break;
case 2: j=delq(&front,&rear);
if(j!=’#’) printf(“The value deleted from circular queue is %d\n”,j);
break;
}
}
}

addq(int *Front,int *Rear,int Value)
{
int rearValue;
if(*Rear >=max-1)
{
rearValue=*Rear;
*Rear=(*Rear+1)%5;
if(*Rear<*Front)
{
cqueue[*Rear]=Value;
printf(“%d is added in circular queue\n”, Value);
}
else
{
*Rear=rearValue;
printf(“Sorry the circular queue is full\n “);
}
}
else
{
(*Rear)++;
if(*Rear !=*Front)
{
cqueue[*Rear]=Value;
printf(“%d is added in circular queue\n”, Value);
}
else
{
(*Rear)–;
printf(“Sorry, the circular queue is full\n”);
}
}
if(*Front==-1)
*Front=*Rear;
}

int delq(int *Front,int *Rear)
{
int value=0;
if(*Front==-1)
{
printf(“Queue is empty\n”);
return ‘#’;
}
else
{
if(*Front==*Rear)
{
value=cqueue[*Front];
*Front=*Rear=-1;
}
else
{
if(*Front >=max)
{
*Front=*Front%5;
if (*Front<*Rear)
{
value=cqueue[*Front];
(*Front)++;
}

else
{
if(*Front==*Rear)
{
value=cqueue[*Front];
*Front=*Rear=-1;
}
}
}
else
{
value=cqueue[*Front];
(*Front)++;
}
}
}
return(value);
}