What are Circular Queue ? - data structure tutorial

Prerequisites: You must have basic knowledge of linear queues. If not, then check out my tutorial on Linear queues and then read about What are Circular Queue ? - data structure tutorial.

A Circular Queue is a type of Queue in which operations like insertion and deletion are performed on the basis of First In First Out principle.

What are Circular Queue ? - data structure tutorial

NOTE : In, the memory there is nothing like a circular array, its just visual representation to make the programmers understand the concept easily. In the code also, we will be using linear array only.

Why Circular Queues?

In a linear queue there was a problem that when we delete an element, then front is incremented thus the size of our queue is reduced. But, in case of a circular queue we can reuse the empty slots again.

Basic features of a Circular Queue

1. Initially, the head and the tail points to same starting index indicating that the queue is initially empty. Head pointer always points to beginning of queue and tail pointer points to end of the queue.

2. When a value is inserted, tail pointer is incremented to point to the next available location.

3. When an element is to be deleted then the head pointer is incremented one place. In circular queue, data is not actually removed from the queue. The data between head and tail is considered and the data outside it is not considered.

4. The head and tail are reinitialised to 0 when they reach the end of the queue.

5. It is also possible that head pointer is ahead of tail. This will happen when we have dequeued a lot of elements and tail is reinitialised upon reaching the end of the queue.

Operations performed on a Circular Queue

Enqueue : Inserting a value to the circular queue.
Dequeue : Deleting an element from the circular queue.
Front : Returns the element at head.
Rear : Returns the element at tail.
IsFull : Tells whether the circular queue is full or not.
IsEmpty : Tells whether the circular queue is empty or not.

Code for Circular Queue

In the code below front is head and rear is tail only.

#include <stdio.h>

#define SIZE 5

int items[SIZE];
int front = -1, rear =-1;

int isFull()
{
    if( (front == rear + 1) || (front == 0 && rear == SIZE-1)) return 1;
    return 0;
}

int isEmpty()
{
    if(front == -1) return 1;
    return 0;
}

void enQueue(int element)
{
    if(isFull()) printf("\n Queue is full!! \n");
    else
    {
        if(front == -1) front = 0;
        rear = (rear + 1) % SIZE;
        items[rear] = element;
        printf("\n Inserted -> %d", element);
    }
}


int deQueue()
{
    int element;
    if(isEmpty()) {
        printf("\n Queue is empty !! \n");
        return(-1);
    } else {
        element = items[front];
        if (front == rear){
            front = -1;
            rear = -1;
        } /* Q has only one element, so we reset the queue after dequeing it. ? */
        else {
            front = (front + 1) % SIZE;
            
        }
        printf("\n Deleted element -> %d \n", element);
        return(element);
    }
}




void display()
{
    int i;
    if(isEmpty()) printf(" \n Empty Queue\n");
    else
    {
        printf("\n Front -> %d ",front);
        printf("\n Items -> ");
        for( i = front; i!=rear; i=(i+1)%SIZE) {
            printf("%d ",items[i]);
        }
        printf("%d ",items[i]);
        printf("\n Rear -> %d \n",rear);
    }
}

int main()
{
    // Fails because front = -1
    deQueue();
    
    enQueue(1);
    enQueue(2);
    enQueue(3);
    enQueue(4);
    enQueue(5);
    
    // Fails to enqueue because front == 0 && rear == SIZE - 1
    enQueue(6);
    
    display();
    deQueue();
    
    display();
    
    enQueue(7);
    display();
    
    // Fails to enqueue because front == rear + 1
    enQueue(8);
    
    return 0;
}

OUTPUT:

So, this was all about What are Circular Queue ? - data structure tutorial. In the upcoming posts, we will learn about Stacks.

What are Circular Queue ? - data structure tutorial

Contact Form