A Circular Queue is a data structure that improves memory utilization by connecting the end of the queue back to the front, forming a circle. Unlike a linear queue, it reuses empty spaces left by dequeued elements, making it an efficient option for scenarios with fixed memory size.
Features of Circular Queue
- Circular Connection: The last position is connected to the first position.
- Efficient Memory Utilization: Reuses vacant spaces after dequeue operations.
- Two Pointers:
- Front: Tracks the first element in the queue.
- Rear: Tracks the last element in the queue.
- Full Condition: When (rear + 1) % SIZE == front.
- Empty Condition: When front == -1.
Operations in Circular Queue
- Enqueue: Adds an element at the rear of the queue.
- Dequeue: Removes an element from the front of the queue.
- Peek: Retrieves the element at the front without removing it.
- IsEmpty: Checks if the queue is empty.
- IsFull: Checks if the queue is full.
- Display: Shows all elements in the queue.
Implementation in C
Header and Global Variables
#include <stdio.h>
#define SIZE 5 // Maximum size of the queue
int queue[SIZE];
int front = -1, rear = -1;
1. Enqueue Operation
Adds an element to the rear of the queue. If the queue is full, it prevents insertion.
void enqueue(int element) {
if ((rear + 1) % SIZE == front) { // Full condition
printf(“Queue is full.\n”);
} else {
if (front == -1) front = 0; // Initialize front if it’s the first element
rear = (rear + 1) % SIZE; // Update rear circularly
queue[rear] = element;
printf(“Enqueued: %d\n”, element);
}
}
2. Dequeue Operation
Removes an element from the front of the queue. If the queue is empty, it prevents removal.
void dequeue() {
if (front == -1) { // Empty condition
printf(“Queue is empty.\n”);
} else {
printf(“Dequeued: %d\n”, queue[front]);
if (front == rear) { // Reset the queue when last element is removed
front = -1;
rear = -1;
} else {
front = (front + 1) % SIZE; // Update front circularly
}
}
}
3. Peek Operation
Retrieves the element at the front without removing it.
void peek() {
if (front == -1) {
printf(“Queue is empty.\n”);
} else {
printf(“Front element: %d\n”, queue[front]);
}
}
4. Display Operation
Prints all elements from front to rear.
void display() {
if (front == -1) {
printf(“Queue is empty.\n”);
} else {
printf(“Queue elements: “);
int i = front;
while (1) {
printf(“%d “, queue[i]);
if (i == rear) break; // Stop at rear
i = (i + 1) % SIZE; // Move circularly
}
printf(“\n”);
}
}
5. Main Program
int main() {
enqueue(10);
enqueue(20);
enqueue(30);
enqueue(40);
enqueue(50); // Queue full here
display();
dequeue();
dequeue();
display();
enqueue(60); // Reuses the space
enqueue(70);
display();
peek();
return 0;
}
Output Example
Enqueued: 10
Enqueued: 20
Enqueued: 30
Enqueued: 40
Enqueued: 50
Queue is full.
Queue elements: 10 20 30 40 50
Dequeued: 10
Dequeued: 20
Queue elements: 30 40 50
Enqueued: 60
Enqueued: 70
Queue elements: 30 40 50 60 70
Front element: 30
Key Points
- Full Condition: (rear + 1) % SIZE == front.
- Empty Condition: front == -1.
- Circular queues are more efficient than linear queues for fixed memory allocation as they reuse space.
- Proper handling of front and rear is crucial to avoid logical errors.
This implementation is suitable for use cases like buffering, scheduling tasks, and managing resources in constrained environments.