Circular queue using array

In a simple queue when the Rear reaches the last position or if Rear is equal to MAX-1 then insertion is not possible.

See the above two images in the first image the queue was full then we deleted 3 elements from the queue.
You may see in the second image there are 3 empty positions (0, 1 and 2) in the array/queue. In case of simple queue we cannot insert elements into those empty positions because in a simple queue when Rear is at the last position in other words when Rear is equal to MAX-1 (Rear==MAX-1) then the queue is full and insertion cannot take place, elements in the queue are always inserted from the rear end.

But in case of circular queue we can insert new elements into those empty positions. So circular queue or array overcomes the limitation of simple queue.
We can think of a circular queue as both the ends of the array above joint together to form a circle.

Insertion and deletion operations in a circular queue can be performed in a manner similar to that of a queue but we need to take care of few things.
When rear is at last position or rear is equal to MAX-1 then then instead of incrementing rear we reset rear to zero and then perform insertion.
In the same way when front is at the last position of the queue (front == MAX-1) then instead of incrementing front we reset the value of front to 0.

The overflow condition in case of circular queue is different, a circular queue will be full only when all the positions are occupied as opposed to Rear equals to MAX-1 in case of a simple queue.

A circular queue will be full in two situations:

Condition 1:
When the value of front is equal to 0 and Rear equals to MAX-1 as shown in the above image.
if(front==0 && rear==MAX-1) 

Condition 2:

In the image above initially the queue was full then 3 elements gets deleted there are three empty positions (0,1 and 2)
First 11 then 15 and finally 20 is inserted into the queue.
In the last instance the value of Rear is 2 and Front is 3 which means front = rear + 1
Hence;
if(front==(rear+1) then circular queue is full

Complete overflow condition of the circular queue.
     if((front==0 && rear==MAX-1) || (front==rear+1))
{
printf(“Queue is fulln”);

    }

To implement circular queue using an array we may create the following three function.
void insert(int) – for insertion
int del() – for deletion
void display() – for displaying elements in the queue.

In the insert function first we should check if the queue is full, if it is then the user should not be allowed to insert elements into the queue.

void insert(int element)
{
     if((front==0 && rear==MAX-1) || (front==rear+1))
     {
              printf("Queue is fulln");
              return;
     }
     if(front==-1)
     {
     front = 0;
     }
     
     if(rear==MAX-1)
     {
     rear=0;
     }
     else
     {
     rear=rear+1;
     }
     
     cqueue[rear]=element;
}

If front is is -1 and the user wants to insert an element into the queue then first front should be made zero.
 if(front==-1)
{
front = 0;
}

If rear is at the last position of the queue and the user wants to insert an element,  if(rear==MAX-1) then rear should be made equal to zero so that the new element can be inserted from 0th position of the queue if it is empty.
 if(rear==MAX-1)
{
rear=0;
}

If not then else condition will be executed which is the same increment statement rear=rear+1 that is used in simple queue to first increment the value of rear and then insert the element at the rear position.
     else
{
rear=rear+1;
}

 The new element into the queue is inserted using the following statement
cqueue[rear]=element;
Here element is the user entered value with the help of scanf function which is be passed as an argument into the  function void insert(int element) from the main function whenever the insert function is called.
So this is the insert function in case of a circular queue.

Now the underflow condition and delete function.
A circular queue will be empty initially when the value of front is equal to -1. Remember the value of Front and Rear are always equal to -1 initially.

In the image above the 3 elements in the queue are deleted, you should know when each time an element is deleted from the queue the value of front is incremented by 1 (front = front + 1)
Finally Front is equal to Rear + 1 and the queue is empty.

In the above fig. all the elements 15, 25, 55,20,90 gets deleted one by one and each time the element from the queue is deleted the value of front is incremented by one (front=front+1) except when Front is at the MAX-1 or the last position of the queue which is 5 in the above example then instead of incrementing the value of front we reset the value of front to zero so finally Front = 0 and Rear = Max-1 and the queue is empty.
But wait; the above two conditions
front=rear+1
and
front=0 and rear=MAX-1
is also true when the circular queue is full so we have to make some changes here to differentiate between and empty queue and full queue.
Leave the insert function and overflow condition as it is and make changes in underflow condition and delete function.

In the delete function we first check if the queue is empty, if it is then queue empty message should be displayed to the user.

 
int del()
{
    int element;
    
    if(front==-1)
    {
                 printf("Queue is Emptyn");
                 return;
    }
    element = cqueue[front];
    
    if(front==rear)
    {
                   front=-1;
                   rear=-1;
    }
    
    else if(front==MAX-1)
    {
    front=0;
    }
    
    else
    {
    front = front + 1;
    }
    printf("%d has been deleted n",element);
    return element;
}

element = cqueue[front]; assigning element the value w will which be deleted so that it can be returned afterwards, the function is of type int. Remember in a queue the element always gets deleted front he front end.

Always remember that there is always one element in the queue when Front is equal to Rear. This always happens as you may see the above fig. when there is one element 30 in the queue front and rear are both equal to 2.
So if front is equal to rear which means one element in the queue and the user calls the delete function to delete an element then what happens ?
The queue becomes empty so inside delete function we can write this code.
if(front==rear)
{
front = -1;
rear = -1;
}

Resetting the value of front and rear to -1. The next time user calls delete function front will be equal to -1 and front = -1 means queue is empty.

else if(front==MAX-1)
{
front=0;
}

If front is at the last position of the queue then reset the value of front to zero.

else
{
front = front + 1;
}

If none of the above conditions are true then usual front = front+1, value of front is incremented and element deleted from the queue.

Display function

   void display()
{
   if(front==-1)
   {
   printf("Queue is Emptyn");
   return;
   }

  int i;
   i=front;
   if(front<=rear)
   {
                  while(i<=rear)
                  printf("%d ",cqueue[i++]);
   }
   
   else {
   
      
       while(i<=MAX-1)
       printf("%d  ",cqueue[i++]);

       i=0;
       while(i<=rear)
       printf("%d   ",cqueue[i++]);
      
       }

}
Previous Post
C program to implement queue using array
Next Post
C Program Circular queue using array

Related Posts

Leave a Reply

Your email address will not be published. Required fields are marked *

Fill out this field
Fill out this field
Please enter a valid email address.

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Menu