Circular queue implementation in C

In my previous posts, we have seen what is queue data structure and how to implement it using linked list and array

Is this queue full?

But we have seen that the array implementation had some problem - it would say "Queue is full" even when the queue was not full.










In the image above, there are 3 slots free in the begining of the array. But as back (rear) is equal to size of array -1, the program will say - queue is full.

One way of overcoming this is to implement a circular queue. That is once end of array is reached, go back to beginning of array and insert elements there. Like this.

Image courtesy:maxtudor.com

 As can be seen in this diagram, once we reach end of array, next element 11 is inserted at the beginning of array. Then we continue from there.

We can say that

index = rear % MAX
array[index] = new_element

Similarly when dequeuing, we can say that

index = front % MAX
temp = array[index]

That way, when front and rear exceed MAX, they continue from 0.

Is the queue full or is it empty?

But the problem arises here. How do we determine whether the queue is full? Or the queue is empty?

In case of earlier implementation, rear=front would have meant that queue is empty.

But in the case of circular queue, front = rear may mean queue is empty or it may mean queue is full.

One way of solving this is to use one extra variable, num_ele - number of elements. Enqueue would increment num_ele and dequeue would decrement num_ele. num_ele is 0 - indicates queue is empty. num_ele is MAX indicates queue is full.

Few changes I have made to this implementation are

1. Store array, rear, front and num_ele in a structure
2. Initialize rear and front to -1 and initialize num_ele to 0
3. When enqueing or adding an element
1. If queue is not full
1. Increment rear
2. Add the new element at array[rear%MAX] (Max is size)
4.  When dequeing or removing an element
1. If queue is not empty
1. save array[front%MAX] in temp
2. Increment front
3. return temp
5. To find if the queue is empty
1. If num_ele is 0 queue is empty
6. To find if the queue is full
1. If num_ele = MAX , queue is full

 Let us write code for enqueue now.

void enqueue(struct queue *qp,int num)
{
  if(is_full(qp))
 {
  printf("The queue is full. Can not add elements...");
 }
 else
 {
  (qp->rear)++;
  int index  = qp->rear % MAX;   
  qp->arr[index] = num;
  
  (qp->num_ele)++;
  if(qp->front==-1)
   qp->front  = 0;
 }
         
}
 

So we increment rear. (qp->rear because we need a pointer to structure queue as we are modifying queue). But if rear exceeds MAX, we need to start from 0. So index = rear%MAX and then we add arr[index] = num.

But what is the last if statement in the function. You remember that front and rear are initialized with -1. So when first element is added, front should point to that element. That is why front is incremented.

Next let us write dequeue function.

int dequeue(struct queue *qp)
{
    int temp = -1;
    if(is_empty(qp))
    {
 printf("Queue is empty");
    }
    else
    {
 int index =  qp->front %MAX;
  temp = qp->arr[index];
 (qp->front)++;
        (qp->num_ele)--;
     }
     return temp;
}

Here we are saving arr[front] in temp and then incrementing front. The function returns the value removed from the queue - temp. To take care of wrapping back, we again use % operator. index = front%MAX.

Next we should write print function which will iterate over all the elements of the queue.

void print_queue(struct queue *qp)
{
    int i;
    printf("Queue is ");
    for(i = qp->front;i<=qp->rear;i++)
 printf("%d---",qp->arr[i%MAX]);
    printf("\n");
}

We start from front element of array and go till rear element. And as i may be more than size of array, we use i%MAX here too.

Here is the complete program.

#include<stdio.h>
#define MAX 5

struct queue 
{
    int arr[MAX];
    int front,rear;
    int num_ele;
};

void init(struct queue *qp)
{
 qp->front = qp->rear = -1;
 qp->num_ele = 0;
}

int is_empty(struct queue *qp)
{
 return qp->num_ele==0;
}

int is_full(struct queue *qp)
{
 return qp->num_ele==MAX;
}
 
void enqueue(struct queue *qp,int num)
{
  if(is_full(qp))
 {
  printf("The queue is full. Can not add elements...");
 }
 else
 {
  (qp->rear)++;
  int index  = qp->rear % MAX;   
  qp->arr[index] = num;
  
  (qp->num_ele)++;
  if(qp->front==-1)
   qp->front  = 0;
 }         
} 

int dequeue(struct queue *qp)
{
    int temp = -1;
    if(is_empty(qp))
    {
 printf("Queue is empty");
    }
    else
    {
 int index =  qp->front %MAX;
  temp = qp->arr[index];
 (qp->front)++;
        (qp->num_ele)--;
     }
     return temp;
}

void print_queue(struct queue *qp)
{
    int i;
    printf("Queue is ");
    for(i = qp->front;i<=qp->rear;i++)
 printf("%d---",qp->arr[i%MAX]);
    printf("\n");
}

 
int main()
{
   struct queue q1;
   init(&q1);
    
   while(1)
   {
       printf("Enter 1 - enqueue 2 - dequeue 3 - exit");
       int opt;
       scanf("%d",&opt);
       if(opt==1)
       {
  int n;
           printf("Enter a number:");
  scanf("%d",&n);
  enqueue(&q1,n);
                print_queue(&q1);
   
 }
 else if(opt==2)
 {
   
  int n;            
  n = dequeue(&q1);
  if (n!=-1){
   printf("Value dequed is %d\n",n);
   print_queue(&q1);
  }
        }  
 else
  break;
    
   }
   return 0;
}

  

You can download the program from here.