Circular Queue Implementation in C. When it comes to a data structure in programming Queues play a significant role, especially in scenarios where operations are performed in a First in, First Out(FIFO) manner. However, the linear queue has its limitations, particularly in terms of space utilization. This is where the concept of a circular queue becomes invaluable. This article will provide a detailed guide on circular queues and how we can implement circular queues in C.
Table of Contents
Understanding Circular Queues
A circular queue is an advanced form of a queue that eliminates the drawback of a linear Queue – Space inefficiency. In a linear Queue, once the rear pointer reaches the end of the Array, it can’t be reused even if there is space available at the beginning of the Array. A circular queue overcomes this issue by connecting the end of the array to the beginning, forming a circular structure.
This means that when it reaches the last position, it wraps around the first, allowing for efficient space utilization. However, care must be taken to avoid the front and the rear colliding with each other unless the queue is either full or empty.
Implementing a Circular Queue in C
Define the Circular Queue in C
First, we need to define the structure of our circular queue. This includes the array itself, the maximum capacity of the queue, and two pointers: front and rear.
#include <stdio.h>
#include <stdlib.h>
#define SIZE 6 // defining the max capacity of queue
typedef struct
{
int items[SIZE];
int front, rear;
} circularqueue;The front pointer is used to track the first element in the queue, while the rear pointer tracks the last element. Initially, both front and rear are set to -1, indicating that the queue is empty.
Queue Initialization
Now we need a function to initialize the queue to its default value.
void initQueue(circularqueue *q)
{
q->front = -1;
q->rear = -1;
}Here for initialization, we are setting front and rear to -1,
Checking if the Queue is Full or Empty
Before adding or removing elements in the circular Queue, we should check whether the queue is full or empty to avoid overflow or underflow.
int isFull(circularqueue *q)
{
if ((q->front == q->rear + 1) || (q->front == 0 || q->rear == SIZE - 1))
{
return 1;
}
return 0;
}
int isEmpty(circularqueue *q)
{
if (q->front == -1)
{
return 1;
}
return 0;
}Insert Elements in the Queue
To add a new element to the queue, We have to increment the rear pointer and insert the new element. If the queue is empty then we have to set front it to 0. Adding elements to a Queue is known as an enqueue.
void enqueue(circularqueue *q, int element)
{
if (isFull(q))
{
printf("Queue is Full\n");
}
else
{
if (q->front == 0)
{
q->front = 1;
}
q->rear = (q->rear + 1) % SIZE;
q->items[q->rear] = element;
printf("Inserted -> %d\n", element);
}
}
Remove Elements from the Queue
When we have to remove an element, We return the value pointed by the front and then increment the front pointer. If the queue becomes empty, we reset both pointers to -1. Removing elements from a Queue is known as dequeue.
int dequeue(circularqueue *q)
{
int element;
if (isEmpty(q))
{
printf("Queue is Emnpty\n");
return (-1);
}
else
{
element = q->items[q->front];
if (q->front == q->rear)
{ // there is only one element in the queue
initQueue(q);
}
else
{
q->front = (q->front + 1) % SIZE;
}
printf("Removed Element : %d\n", element);
return element;
}
}Display the Queue
Finally, we should have a function to Display the elements of the queue.
void display(circularqueue *q)
{
int i;
if (isEmpty(q))
{
printf("Queue is Empty\n");
}
else
{
printf("Queue Elements :\n");
for (i = q->front; i != q->rear; i = (i + 1) % SIZE)
{
printf("%d ", q->items[i]);
}
printf("%d ", q->items[i]);
printf("\n");
}
}
Complete C Program for Circular Queue
To see the circular queue in action, we have to write a main function that uses the above method to create and manipulate a circular queue instance.
Complete C Program
#include <stdio.h>
#include <stdlib.h>
#define SIZE 6 // defining the max capacity of queue
typedef struct
{
int items[SIZE];
int front, rear;
} circularqueue;
void initQueue(circularqueue *q)
{
q->front = -1;
q->rear = -1;
}
int isFull(circularqueue *q)
{
if ((q->front == q->rear + 1) || (q->front == 0 || q->rear == SIZE - 1))
{
return 1;
}
return 0;
}
int isEmpty(circularqueue *q)
{
if (q->front == -1)
{
return 1;
}
return 0;
}
void enqueue(circularqueue *q, int element)
{
if (isFull(q))
{
printf("Queue is Full\n");
}
else
{
if (q->front == 0)
{
q->front = 1;
}
q->rear = (q->rear + 1) % SIZE;
q->items[q->rear] = element;
printf("Inserted -> %d\n", element);
}
}
int dequeue(circularqueue *q)
{
int element;
if (isEmpty(q))
{
printf("Queue is Emnpty\n");
return (-1);
}
else
{
element = q->items[q->front];
if (q->front == q->rear)
{ // there is only one element in the queue
initQueue(q);
}
else
{
q->front = (q->front + 1) % SIZE;
}
printf("Removed Element : %d\n", element);
return element;
}
}
void display(circularqueue *q)
{
int i;
if (isEmpty(q))
{
printf("Queue is Empty\n");
}
else
{
printf("Queue Elements :\n");
for (i = q->front; i != q->rear; i = (i + 1) % SIZE)
{
printf("%d ", q->items[i]);
}
printf("%d ", q->items[i]);
printf("\n");
}
}
void main()
{
circularqueue q;
initQueue(&q);
enqueue(&q, 233);
enqueue(&q, 2);
enqueue(&q, 3);
enqueue(&q, 53);
enqueue(&q, 89);
enqueue(&q, 10);
// trying to add element while queue is already full
enqueue(&q, 26);
display(&q);
int element = dequeue(&q);
if (element != -1)
{
printf("Dequeued : %d", element);
}
display(&q);
enqueue(&q, 5);
display(&q);
}
Circular Queues are a pivotal data structure, especially for buffering data in hardware and software applications. Implementing a circular queue in C is a great exercise for understanding dynamic data structures and pointers. By efficiently utilizing the available space, circular queues can significantly improve the performance of queue-based systems. The code provided in this article offers a solid foundation for understanding and implementing circular queues in C. Experiment with the code, tweak it, and use it as a stepping stone for more complex data structure implementations.
Happy Coding & Learning
2 thoughts on “Circular Queue Implementation in C”