Back to: Data Structures and Algorithms Tutorials

How to Implement Circular Queue in C Language:

In this article, I will discuss how to Implement a Circular Queue in C Language with Examples. Please read our previous article about the Drawbacks of Queues using an Array. Now, we will discuss the concept of a circular queue with an example.

Problem with Linear Queue:

The problem with a linear queue is that we move the front pointer instead of shifting the elements. If you remember the example discussed in the previous article, some people are standing in a queue.

When a person leaves the queue, instead of shifting all the people forward, we move the counter. This way, only one step is taken, and the deletion of an element is done in constant time.

In this method, we get lots of free spaces on the left side, but there is no space on the right side, so a new person cannot enter the queue. The idea behind a circular queue is to use the vacant spaces of the queue and allow adding new elements in a circular manner. So, in the above example, if there is no space on the right side, a new person can come and stand on the left side.

That’s the backside of the counter. How does it work? Suppose all the people on the right side leave the queue after their work.

Now, no one is left on the right side of the queue, so the counter will start again from the left side.

We will use this space circularly, allowing people to form a queue from the left side as well. That’s the idea of a circular queue. If the person serving (handling the counter) can come back again to the 0th index of the array, then it will form a circular queue. Let’s implement this idea in our queue.

Implementation of Circular Queue using Array in C Language:

We have to move the front and rear pointers circularly.

Once the front and rear reach the 6th index, they will continue from the 0th index of the array.

Initially, the front and rear will be at 0. We will not start from -1. You’ll understand why we are starting from zero. We will insert elements using the front, and we will delete elements using the rear. So, let’s insert some elements.

Here, the rear is incremented by one, and we inserted ‘1’ at index 1. What about the 0th index? That should be left empty. We will not use that location. Wherever the front is pointing, that location must be left empty. Let us fill the queue.

Circular Insertion with Rear Pointer:

Now, the queue is full. The rear is pointing at the 6th index (size – 1), and the front is still at the 0th index. Let us delete a few elements.

Here, the front is incremented, and then we remove that element. Let’s delete two more elements.

Now, we have some free space. Can we insert more elements? Yes. We’ll bring the rear to the 0th index and insert the element there.

Here, a new element is inserted at the backside of the front pointer. You can see that when the rear was at 6, it became 0. If we insert one more element, then the rear will be incremented by one.

Let’s insert one more.

Now, can we insert any element? No. There is a free space where the front is pointing, but don’t use that space. Wherever the front is pointing, that location must be left empty. What happens if we use that space?

Why must the location where the front is pointing be empty?

If we bring the rear to the front’s index, then the front and rear are both equal. When the rear and front both point at the same index, it means the queue is empty. Let us show you.

Now, the front and rear are equal. Is the queue full or empty? Actually, the queue is full, but rear == front is the queue empty condition. So, that is the reason we won’t use the place where the front is pointing. If the array’s size is 7, then how many elements can we store here? We can store 6 elements, but we cannot use all 7 places.

If we are deleting elements using the front, we will first delete all the elements on the right side, and when we reach the last location, we will start deletion from the left side of the array. So, we will implement a circular queue over an array by moving the front and rear circularly. The array is not circular; the front and rear are moving circularly.

Representation of Circular Queue:

Let us show you a diagram of how we usually represent a circular queue.

This is how we represent a circular queue. We show the array as circular, but the array is not circular. The front and rear will move circularly. So, how do we move the rear and front circularly? We want a mechanism such that they automatically move circularly. Let us show you what we mean.

Here, the front is on 3. If we say next, then it should go from 3 to 4, and so on. But when the front is on 6, the next should come to 0. So, the circular behavior, or starting from 0 after the last index, can be obtained using the mod operation. Let us see how we can use the mod operation.

Circular Mechanism using Mod Operation:

Let’s see how the mod operation is used to obtain circular values. We will explain it using the rear pointer, but the same principle will also apply to the front pointer.

Initially, the rear is 0. So,

New Rear = (Rear + 1) % Size

New Rear = (0 + 1) % 7 = 1

Here, the rear is 1.

New Rear = (1 + 1) % 7 = 2

We have calculated all the values until the rear is equal to 5.

Now, the rear is 6. So,

New Rear = (6 + 1) % 7 = 0

So, the “(Rear + 1) % Size” formula will give us a circular value. We started the rear from 0, and it reached 0 again. So, by using the mod operator, we’ll be moving the front and rear pointers circularly.

Now, we will modify the enqueue and dequeue operations and the movement of the front and rear pointers. The circular queue always reuses the vacant spaces, which is the best method for implementing a queue using an array. Let’s see the enqueue and dequeue functions.

Enqueue Function in Circular Queue:

void enqueue (struct Queue *q, int x) {
    if(q->rear + 1) % q->size == q->front){
        printf("Queue is Full");
    }
    else {
        q->rear = (q->rear + 1) % q->size;
        q->Q[q->rear] = x;
    }
}

This is the modified enqueue function for a circular queue. It takes an object of Queue as a pointer (q) and a value (x) that has to be inserted in the queue. Before the insertion, we have to check whether the queue has space or not. So, we have checked for the queue full condition: ((q->rear + 1) % q->size == q->front).

What is Queue Full Condition?

To explain queue the full condition, we’ve taken an example.

Here, you can see that the queue is full. The place where the front is pointing is left empty, and all the other places are filled. So, if the rear is just behind the front pointer, or we can say the front is pointing to the rear’s next location, then the queue is full. Here also, what’s the next location of the rear? It’s 0. We have discussed this above. The rear will become 0 after the 6th index. So, if the next place of the rear is the front, the queue is full.

((q->rear + 1) % q->size == q->front)

In this condition, we’re checking the same thing. If the rear + 1 mod q’s size is equal to q’s front, then it means the queue is full. Otherwise, move the rear.

q->rear = (q->rear + 1) % q->size;

We will move the rear pointer with this statement.

q->Q[q->rear] = x;

This statement will store the new element at the rear location. This is the enqueue operation for a circular queue using an array. Now, let’s see the dequeue function.

Dequeue Function in Circular Queue:

int dequeue (struct Queue *q){
    int x = -1;
    if(q->front == q->rear) {
        printf("Queue is Empty");
    }
    else {
        q->front = (q->front + 1) % q->size;
        x = q->Q[q->front];
    }
    return x;
}

This function takes an object of Queue as a pointer. Then, we initialize a variable x with -1. This will store the deleted value. For deletion, we have to check the queue empty condition. So, what is the queue empty condition? When the front and rear become equal. Initially, the front and rear are both at zero, so the queue will be empty. So, whenever the front and rear are equal, we print a message “Queue is Empty.” If it is not empty, we will use the front pointer to delete the elements.

q->front = (q->front + 1) % q->size;

This statement will move the front pointer circularly.

x = q->Q[q->front];

Here, we store the deleted element in x and return its value at the end of the function. Enqueue and Dequeue have simple statements (without any loops), so the time taken by both functions will be constant. That’s all about the circular queue. In a circular queue, we can reuse the spaces, making it the best method to implement a queue using an array. Now, let us show you the complete C program for a circular queue.

Program to Implement Circular Queue using an Array in C Language:

#include <stdio.h>
#include <stdlib.h>

struct Queue {
  int size;
  int front;
  int rear;
  int * Q;
};

void create(struct Queue * q, int size) {
  q -> size = size;
  q -> front = q -> rear = 0;
  q -> Q = (int * ) malloc(q -> size * sizeof(int));
}

void enqueue(struct Queue * q, int x) {
  if ((q -> rear + 1) % q -> size == q -> front) {
  printf("Queue is Full");
}
else {
  q -> rear = (q -> rear + 1) % q -> size;
  q -> Q[q -> rear] = x;
}
}

int dequeue(struct Queue * q) {
  int x = -1;

  if (q -> front == q -> rear) {
    printf("Queue is Empty");
  } else {
    q -> front = (q -> front + 1) % q -> size;
    x = q -> Q[q -> front];
  }
  return x;

}

void Display(struct Queue q) {
  int i = q.front + 1;

  do {
    printf("%d ", q.Q[i]);
    i = (i + 1) % q.size;
  } while (i != (q.rear + 1) % q.size);
  
  printf("\n\n");
}

int main() {
  struct Queue q;
  int x = 0, size, elements;

  printf("Enter the size of the queue: ");
  scanf("%d", &size);

  create( & q, size);

  printf("Enter the no. of elements: ");
  scanf("%d", &elements);

  printf("Enter the elements:\n");
  for (int i = 0; i < elements; i++) {
    scanf("%d", & x);
    enqueue( & q, x);
  }
  printf("\n");

  enqueue( & q, 12);
  printf("Enqueue Operation has been performed: \n");
  Display(q);

  x = dequeue( & q);
  printf("Dequeue Operation has been performed: %d\n", x);
  Display(q);

  return 0;
}

Output:

In the next article, I will discuss How to Implement a Queue using a Linked List in C Language with Examples. In this article, I explain How to Implement a Circular Queue in C Language with Examples. I hope you enjoy this Circular Queue in C Language article.