What Is a Circular Queue and How Is It Implemented Using an Array?
A Circular Queue is a linear data structure that follows the FIFO (First In, First Out) principle. Unlike a simple queue, a circular queue connects the last position of an array back to its first position, forming a logical circle.
This arrangement allows the queue to reuse empty spaces created after deleting elements. Therefore, it avoids the memory wastage that can occur in a linear queue implemented using an array.
A circular queue is commonly used in CPU scheduling, memory management, buffering, and operating systems.
What Is a Circular Queue?
A circular queue is a special type of queue in which the last position is logically connected to the first position.
It uses two pointers:
- Front: Points to the first element in the queue.
- Rear: Points to the last element in the queue.
When the rear pointer reaches the last array position, it moves back to index 0 if an empty position is available.
Similarly, when the front pointer reaches the last position during deletion, it moves back to the beginning.
This movement is called circular movement or wrap-around.
Example of Circular Queue
Consider a circular queue of size 5.
Initially, the queue is empty. After inserting five elements, the array looks like this:
| Index | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| Element | 10 | 20 | 30 | 40 | 50 |
Now, suppose we delete two elements (10 and 20).
The queue contains:
| Index | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| Element | Empty | Empty | 30 | 40 | 50 |
When we insert new elements, the circular queue reuses index 0 and index 1 instead of wasting those positions.
This is the main advantage of a circular queue.
How Does a Circular Queue Work?
A circular queue works using two pointers, front and rear, and follows the FIFO principle.
The main operations are:
- Enqueue – Insert an element into the queue.
- Dequeue – Remove an element from the queue.
- Display – Display all elements present in the queue.
1. Enqueue Operation
Enqueue is the process of inserting a new element at the rear of the circular queue.
Steps:
- Check whether the queue is full.
- If the queue is full, display Queue Overflow.
- If the queue is empty, initialize front and rear to 0.
- Otherwise, update rear using the circular increment formula.
- Insert the new element at the rear position.
The formula for updating rear is:
Here, n represents the maximum size of the queue.
2. Dequeue Operation
Dequeue is the process of deleting an element from the front of the circular queue.
Steps:
- Check whether the queue is empty.
- If the queue is empty, display Queue Underflow.
- Otherwise, remove the element at the front position.
- If front and rear are equal, reset both to -1.
- Otherwise, update front using the circular increment formula.
The formula is:
3. Display Operation
The display operation prints all elements currently stored in the circular queue.
Steps:
- Check whether the queue is empty.
- Start from the front position.
- Print the current element.
- Move to the next index using circular increment.
- Continue until the rear position is reached.
How Is a Circular Queue Represented Using an Array?
A circular queue can be implemented using a one-dimensional array and two integer variables named front and rear.
Consider the following declaration in C:
#define SIZE 5
int queue[SIZE];
int front = -1;
int rear = -1;
Here:
queue[SIZE]stores the queue elements.frontstores the index of the first element.rearstores the index of the last element.front = -1andrear = -1indicate an empty queue.
The array is treated as circular using the modulo operator.
Algorithm for Circular Queue Operations
Algorithm for Enqueue in Circular Queue
Input: An element to be inserted.
Output: Element inserted successfully or Queue Overflow.
ENQUEUE(queue, value)
1. If (rear + 1) % SIZE == front
Print "Queue Overflow"
Return
2. If front == -1
front = 0
rear = 0
Else
rear = (rear + 1) % SIZE
3. queue[rear] = value
4. Stop
Algorithm for Dequeue in Circular Queue
Input: Circular queue.
Output: Deleted element or Queue Underflow.
DEQUEUE(queue)
1. If front == -1
Print "Queue Underflow"
Return
2. value = queue[front]
3. If front == rear
front = -1
rear = -1
Else
front = (front + 1) % SIZE
4. Print deleted value
5. Stop
Algorithm for Display in Circular Queue
DISPLAY(queue)
1. If front == -1
Print "Queue is Empty"
Return
2. i = front
3. Repeat
Print queue[i]
If i == rear
Break
i = (i + 1) % SIZE
4. Stop
C Program to Implement Circular Queue Using Array
The following C program implements a circular queue using an array. It supports three important operations: enqueue, dequeue and display.
#include <stdio.h>
#include <stdlib.h>
#define SIZE 5
int queue[SIZE];
int front = -1;
int rear = -1;
// Insert an element into the circular queue
void enqueue(int value) {
if ((rear + 1) % SIZE == front) {
printf("Queue Overflow\n");
return;
}
if (front == -1) {
front = 0;
}
rear = (rear + 1) % SIZE;
queue[rear] = value;
printf("%d inserted successfully\n", value);
}
// Delete an element from the circular queue
void dequeue() {
if (front == -1) {
printf("Queue Underflow\n");
return;
}
printf("Deleted element: %d\n", queue[front]);
if (front == rear) {
front = -1;
rear = -1;
} else {
front = (front + 1) % SIZE;
}
}
// Display all queue elements
void display() {
if (front == -1) {
printf("Queue is Empty\n");
return;
}
int i = front;
printf("Queue elements: ");
while (1) {
printf("%d ", queue[i]);
if (i == rear) {
break;
}
i = (i + 1) % SIZE;
}
printf("\n");
}
// Main function
int main() {
int choice, value;
while (1) {
printf("\n1. Enqueue");
printf("\n2. Dequeue");
printf("\n3. Display");
printf("\n4. Exit");
printf("\nEnter your choice: ");
scanf("%d", &choice);
switch (choice) {
case 1:
printf("Enter value: ");
scanf("%d", &value);
enqueue(value);
break;
case 2:
dequeue();
break;
case 3:
display();
break;
case 4:
exit(0);
default:
printf("Invalid choice\n");
}
}
return 0;
}
Output of Circular Queue Program in C
- Enqueue
- Dequeue
- Display
- Exit
Enter your choice: 1
Enter value: 10
10 inserted successfully
Enter your choice: 1
Enter value: 20
20 inserted successfully
Enter your choice: 1
Enter value: 30
30 inserted successfully
Enter your choice: 3
Queue elements: 10 20 30
Enter your choice: 2
Deleted element: 10
Enter your choice: 3
Queue elements: 20 30
Enter your choice: 1
Enter value: 40
40 inserted successfully
Enter your choice: 3
Queue elements: 20 30 40
Dry Run of a Circular Queue
Consider a circular queue with a maximum capacity of 5.
Perform the following operations:
- Enqueue(10)
- Enqueue(20)
- Enqueue(30)
- Dequeue()
- Enqueue(40)
- Enqueue(50)
- Enqueue(60)
The queue changes as follows:
| Operation | Front | Rear | Queue elements |
|---|---|---|---|
| Initial | -1 | -1 | Empty |
| Enqueue(10) | 0 | 0 | 10 |
| Enqueue(20) | 0 | 1 | 10, 20 |
| Enqueue(30) | 0 | 2 | 10, 20, 30 |
| Dequeue() | 1 | 2 | 20, 30 |
| Enqueue(40) | 1 | 3 | 20, 30, 40 |
| Enqueue(50) | 1 | 4 | 20, 30, 40, 50 |
| Enqueue(60) | 1 | 0 | 20, 30, 40, 50, 60 |
Notice that after inserting 60, the rear pointer moves from index 4 to index 0.
This demonstrates how a circular queue reuses the empty position created by the dequeue operation.
Time and Space Complexity of a Circular Queue
The circular queue implementation using an array has efficient insertion and deletion operations.
| Operation | Time Complexity | Explanation |
|---|---|---|
| Enqueue | O(1) | Inserts an element at the rear |
| Dequeue | O(1) | Removes an element from the front |
| Peek/Front | O(1) | Accesses the front element |
| Display | O(n) | Traverses all queue elements |
Space Complexity: O(n)
The queue uses an array of size n, so the total space required is proportional to the capacity of the queue.