A circular queue is an advanced type of queue that efficiently uses memory by connecting the end of the queue back to the beginning. Unlike a linear queue, it avoids wasted space after multiple enqueue and dequeue operations. Circular queues are widely used in buffering, task scheduling, and operating systems. This article demonstrates array-based and linked-list-based implementations of circular queues in C, including ways to get the front and rear elements.
Understanding the Problem
In a circular queue, elements are added at the rear and removed from the front, following the FIFO (First In, First Out) principle. The rear pointer wraps around to the beginning when it reaches the end of the array or linked list. The key challenge is managing front and rear pointers correctly to avoid overflow, underflow, or invalid memory access, while maintaining the proper order of elements.
Program 1: Circular Queue Using Arrays
This implementation uses a fixed-size array and modulo arithmetic to handle the circular nature of the queue. The rear pointer wraps around to the start of the array when it reaches the end, allowing efficient space utilization. Overflow and underflow are checked to prevent invalid operations. Functions are included to get the front and rear elements.
#include <stdio.h>
#define MAX 5
int queue[MAX];
int front = -1, rear = -1;
int isFull() {
return (front == 0 && rear == MAX - 1) || (rear + 1) % MAX == front;
}
int isEmpty() {
return front == -1;
}
void enqueue(int value) {
if (isFull()) {
printf("Queue Overflow! Cannot insert %d\n", value);
return;
}
if (isEmpty()) front = rear = 0;
else rear = (rear + 1) % MAX;
queue[rear] = value;
printf("%d enqueued to the queue.\n", value);
}
void dequeue() {
if (isEmpty()) {
printf("Queue Underflow! Nothing to dequeue.\n");
return;
}
printf("%d dequeued from the queue.\n", queue[front]);
if (front == rear) front = rear = -1;
else front = (front + 1) % MAX;
}
int getFront() {
if (isEmpty()) {
printf("Queue is empty.\n");
return -1;
}
return queue[front];
}
int getRear() {
if (isEmpty()) {
printf("Queue is empty.\n");
return -1;
}
return queue[rear];
}
void display() {
if (isEmpty()) {
printf("Queue is empty.\n");
return;
}
printf("Queue elements: ");
int i = front;
while (1) {
printf("%d ", queue[i]);
if (i == rear) break;
i = (i + 1) % MAX;
}
printf("\n");
}
int main() {
enqueue(10);
enqueue(20);
enqueue(30);
enqueue(40);
enqueue(50); // Queue full
display();
printf("Front element: %d\n", getFront());
printf("Rear element: %d\n", getRear());
dequeue();
dequeue();
display();
enqueue(60);
enqueue(70); // Wrap around
display();
printf("Front element: %d\n", getFront());
printf("Rear element: %d\n", getRear());
return 0;
}In this array-based circular queue, the rear and front pointers are updated using modulo arithmetic to handle wrap-around. Overflow and underflow are checked before enqueueing or dequeueing. The getFront() and getRear() functions allow accessing the first and last elements without removing them. This implementation efficiently reuses empty spaces created after dequeuing.
Program 2: Circular Queue Using Linked List
For queues with unknown or growing numbers of elements, a linked-list-based circular queue is more flexible. Each node points to the next element, and the last node points back to the first node, forming a circle. Functions to get the front and rear elements are included.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *next;
} Node;
Node *rear = NULL;
void enqueue(int value) {
Node *newNode = (Node*)malloc(sizeof(Node));
newNode->data = value;
if (!rear) {
newNode->next = newNode;
rear = newNode;
} else {
newNode->next = rear->next;
rear->next = newNode;
rear = newNode;
}
printf("%d enqueued to the queue.\n", value);
}
void dequeue() {
if (!rear) {
printf("Queue Underflow! Nothing to dequeue.\n");
return;
}
Node *front = rear->next;
if (rear == front) {
printf("%d dequeued from the queue.\n", front->data);
free(front);
rear = NULL;
} else {
printf("%d dequeued from the queue.\n", front->data);
rear->next = front->next;
free(front);
}
}
int getFront() {
if (!rear) {
printf("Queue is empty.\n");
return -1;
}
return rear->next->data;
}
int getRear() {
if (!rear) {
printf("Queue is empty.\n");
return -1;
}
return rear->data;
}
void display() {
if (!rear) {
printf("Queue is empty.\n");
return;
}
Node *temp = rear->next;
printf("Queue elements: ");
do {
printf("%d ", temp->data);
temp = temp->next;
} while (temp != rear->next);
printf("\n");
}
int main() {
enqueue(10);
enqueue(20);
enqueue(30);
display();
printf("Front element: %d\n", getFront());
printf("Rear element: %d\n", getRear());
dequeue();
display();
enqueue(40);
enqueue(50);
display();
printf("Front element: %d\n", getFront());
printf("Rear element: %d\n", getRear());
return 0;
}In this linked-list implementation, each node is dynamically allocated, and the last node (rear) points back to the first node. The enqueue() function adds a new node at the rear, and dequeue() removes the node at the front. The getFront() and getRear() functions allow access to elements without removal. This implementation supports unlimited growth and avoids the fixed-size limitations of arrays.
FAQs
Q1: What is the advantage of a circular queue over a linear queue?
A circular queue reuses spaces freed by dequeued elements, making better use of memory.
Q2: Can a circular queue be implemented using a linked list?
Yes, a circular linked list allows dynamic resizing and avoids fixed-size limitations of arrays.
Q3: What is the time complexity of enqueue and dequeue?
Both enqueue and dequeue operations in a circular queue, whether array-based or linked-list-based, have O(1) time complexity.
Q4: How do you detect overflow in a circular queue?
In arrays, overflow occurs when the next rear position would collide with front. In linked lists, overflow is limited only by system memory.
Conclusion
Circular queues improve upon linear queues by reusing memory and handling continuous enqueue/dequeue operations efficiently. Array-based circular queues are suitable for fixed-size queues, while linked-list implementations allow dynamic growth and flexibility. Proper pointer management and memory handling ensure reliable and efficient circular queue operations.
References & Additional Resources
A curated collection of textbooks and tutorials for learning circular queues and their implementations in C.
- Kernighan, B. W., & Ritchie, D. M. (1988). The C Programming Language (2nd Edition). Prentice Hall – Classic reference covering arrays, pointers, and memory management essential for queue implementations.
- Thareja, R. (2011). Data Structures Using C. Oxford University Press – Comprehensive coverage of queues, circular queues, and linked list implementations with practical C examples.
- GeeksforGeeks: Circular Queue Using Arrays – Step-by-step explanation of circular queue implementation using arrays.
- GeeksforGeeks: Circular Queue Using Linked List – Guide to implementing circular queues using linked lists.
- Programiz: Queue Data Structures in C – Practical guide with examples of linear and circular queue implementations in C.
- C Standard Library Documentation – Official reference for standard C functions and libraries useful in queue operations.
