Introduction to Circular Queue
Why we need circular queue?
When we discussed queues, we decided to have two index variables f and r, which would maintain the two ends of the queue. If we follow the illustration below, we would see that our queue gets full when element 8 is pushed in the queue.
In other words, we can only enqueue in a queue until the queue isn't full.
Figure 1: Using two integer variables to maintain the ends of a queue
Now, by dequeuing first three elements we will observe that our queue is still full as the rear end i at the array's threshold. But it has space of three elements that we just removed.
- Drawback: space is not efficiently utilized by the array in the heap.
- Space from dequeuing elements is unused.
When we talk about utilizing these spaces rather than letting them go unused, we introduce circular queues.
How we will modify to eliminate these drawbacks.
- 1. By reseting f and r to -1 whenever the queue becomes empty. This makes all the space in the array reusable. Here, the queue was full since r equals the size-1 of the array. But resetting both the index
variable to -1 empties the queue.
Resetting the index variable to -1 ↑
again a drawback. So, can't implement this. - 2. Therefore we need a more optimized solution. This is when circluar queues come to the rescue.
Circular Queues:
In circular queues, we mainly focus on the point that we don't increment our indices linearly. Linearly increasing indicies cause the case of overflow when our index reaches the limit, which is size-1.
In linear increment, i becomes i+1.
But in circular increment : i becomes (i+1)%size. This gives an upper cap to the maximum value making the index repeat itself.
And this makes us start from the beginning once we reach the threshold of the array. Refer to the illustration below to visualize the movement of the cursor.
Conversion of a linear queue to a circular queue ↑
And this is the circular implementation of the same array we used to implement linearly. This allows the leftover spaces to be used again.
This wheel type array is called the circular queue.
Operations on Circular Queue
struct circularQueue
{
int size;
int f;
int r;
int* arr;
};
In main, we had declared a struct circularQueue q, and initialized its instances. Here is a subtle change, we don’t initialize circular queues’ f and r with -1, rather 0. Since -1 is unreachable in circular incrementation. Leave everything as it is.
//In main
struct circularQueue q;
q.size = 4;
q.f = q.r = 0;
q.arr = (int*) malloc(q.size*sizeof(int));
isEmpty
if our f equals r, then there is no element in our queue, and this is the case of an empty queue.
int isEmpty(struct circularQueue *q){
if(q->r==q->f){
return 1;
}
return 0;
}
isFull
If our (r+1)%size equals f, then there is not space left in out queue, and this is the case of a full queue.
int isFull(struct circularQueue *q){
if((q->r+1)%q->size == q->f){
return 1;
}
return 0;
}
Enqueue:
- Check if the queue is already not full. ( check if the next index to the rear is whether the front or not.)
- If not full then just circular increment the rear r and insert the new given value.
void enqueue(struct circularQueue *q, int val){
if(isFull(q)){
printf("This Queue is full");
}
else{
q->r = (q->r +1)%q->size;
q->arr[q->r] = val;
printf("Enqued element: %d\n", val);
}
}
Dequeue:
- Dequeue → removing first element.
- Check if queue is already empty. ( If front f equals the rear r, it is the case of queue underflow, else just increment f by 1 )
- As the front f holds the index of first element, we can just circular increment it and will be removed.
- we store the element being removed and return it at the end.
int dequeue(struct circularQueue *q){
int a = -1;
if(isEmpty(q)){
printf("This Queue is empty");
}
else{
q->f = (q->f +1)%q->size;
a = q->arr[q->f];
}
return a;
}
#include<stdio.h>
#include<stdlib.h>
struct circularQueue
{
int size;
int f;
int r;
int* arr;
};
int isEmpty(struct circularQueue *q){
if(q->r==q->f){
return 1;
}
return 0;
}
int isFull(struct circularQueue *q){
if((q->r+1)%q->size == q->f){
return 1;
}
return 0;
}
void enqueue(struct circularQueue *q, int val){
if(isFull(q)){
printf("This Queue is full");
}
else{
q->r = (q->r +1)%q->size;
q->arr[q->r] = val;
printf("Enqued element: %d\n", val);
}
}
int dequeue(struct circularQueue *q){
int a = -1;
if(isEmpty(q)){
printf("This Queue is empty");
}
else{
q->f = (q->f +1)%q->size;
a = q->arr[q->f];
}
return a;
}
int main(){
struct circularQueue q;
q.size = 4;
q.f = q.r = 0;
q.arr = (int*) malloc(q.size*sizeof(int));
// Enqueue few elements
enqueue(&q, 12);
enqueue(&q, 15);
enqueue(&q, 1);
printf("Dequeuing element %d\n", dequeue(&q));
printf("Dequeuing element %d\n", dequeue(&q));
printf("Dequeuing element %d\n", dequeue(&q));
enqueue(&q, 45);
enqueue(&q, 45);
enqueue(&q, 45);
if(isEmpty(&q)){
printf("Queue is empty\n");
}
if(isFull(&q)){
printf("Queue is full\n");
}
return 0;
}