C

How to implement a circular queue data structure?

Rohit Kumar

Rohit Kumar

— 2 min read
How to implement a circular queue data structure?
Photo by David Clode / Unsplash

A circular Queue is the optimized solution of a normal queue. In this particular approach, we can make sure all the memory space of the queue is being utilized. Once the rear reaches the last position and the dequeue operation is performed, updating the rear value will allow us to achieve circularity.

Circular Queue - enqueue operation
Circular Queue - dequeue operation
#ifndef __QUEUE_H__
#define __QUEUE_H__

typedef struct _queue{
    int *data;
    unsigned int rear;
    unsigned int front;
    unsigned int size;
    unsigned int emptySpace;
}queue;

queue* createQueue(unsigned int size_of_queue);
void enqueue(queue *q, unsigned int val);
int  dequeue(queue *q);
void destroyQueue(queue *q);
void showQueue(queue *q);
 
#endif

circularQueue.h

#include <stdio.h>
#include <stdlib.h>
#include "queue.h"
    
queue* createQueue(unsigned int size_of_queue)
{
    queue *q = malloc(sizeof(queue));
    q->data = malloc(size_of_queue * sizeof(int));
    if(q->data == NULL){
        free(q);
        return NULL;
    }
    q->front = 0;
    q->rear = 0;
    q->size = size_of_queue;
    q->emptySpace = size_of_queue;
    return q;
}

void enqueue(queue *q, unsigned int val)
{
    printf("rear:%d front:%d\n",q->rear, q->front);
    if(q->emptySpace == 0){
        printf("Queue is full\n");
        return;
    }
    q->data[(q->rear)++] = val;
    if(q->rear == q->size){
        q->rear = 0;
    } 
    (q->emptySpace)--;
}

int dequeue(queue *q)
{
    printf("rear:%d front:%d\n",q->rear, q->front);
    if(q->emptySpace == q->size){
        printf("Queue is empty\n");
        return -1;
    }
    int val = q->data[(q->front)];
    q->data[(q->front)++] = 0;
    
    if(q->front == q->size){
        q->front = 0;
    }
    (q->emptySpace)++;
    return val;
}

void destroyQueue(queue *q)
{
    if(q != NULL){
        if(q->data != NULL)
        {
            free(q->data);
        }
        free(q);
    }
}

void showQueue(queue *q)
{
    int i =0;
    printf("<<|");
    for(i=0; i != q->size; i++){
        printf(" %d | ",q->data[i]);
    }
    printf("\n");
}

circularQueue.c

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

int main()
{
    int size;
    int ch;
    int val;

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

    queue *q1 = createQueue(size);    
    if(q1 == NULL)
    {
        printf("Can not allocated queue.\n");
        printf("Queue Failed !!\n");
        return -1;
    }

    while(1){
        printf("\tEnter 1. for enqueue()\n");
        printf("\tEnter 2. for dequeue()\n");
        printf("\tEnter any other integer for exit()\n");
        printf("Enter your choice :");
        scanf(" %d",&ch);
        switch(ch)
        {
            case 1:
                printf("Enter the value you want to enqueue into queue : ");
                scanf(" %d", &val);
                enqueue(q1, val);
                showQueue(q1);
                break;
            case 2: 
                val = dequeue(q1);
                if(val >= 0){
                    printf("Popped value from the queue is : %d\n",val);
                }
                showQueue(q1);
                break;
            default:
                goto exitQueue;    
        }
    }
    
    exitQueue: 
        destroyQueue(q1);

    return 0;
}

main.c

Read more