What Is a Circular Queue?
A circular queue is a queue implementation in which the last position of the underlying storage connects back to the first position. Instead of allowing the rear to move only toward the end of an array, a circular queue can wrap around and reuse positions that became available after dequeue operations.
Like a regular queue, a circular queue follows the FIFO (First In, First Out) principle. The difference is mainly in how the available storage is managed.
Circular Queue
┌─────────────────────────────┐
↓ │
[10] [20] [30] [40] [50] │
↑ │
└─────────────────────────────┘
Front → first active element
Rear → position where the next element can be added
The circular structure allows the queue to use the beginning of the array again after the rear reaches the final position. This makes circular queues especially useful for fixed-size buffers, scheduling systems, streaming data, and other applications where storage should be reused.
Why Do We Need a Circular Queue?
Consider a fixed-size array with five positions:
[10] [20] [30] [40] [50] ↑ ↑ Front Rear
If the first two elements are removed, there are now two free positions at the beginning:
[ ] [ ] [30] [40] [50]
↑ ↑
free space Rear
A simple linear queue may reach the end of the array and appear full even though unused positions exist at the beginning. A circular queue solves this problem by allowing the rear to wrap around to those available positions.
[60] [70] [30] [40] [50] ↑ ↑ wrapped positions
Circular Queue Representation
A circular queue is commonly implemented using a fixed-size array and a small amount of additional state. The implementation typically tracks:
- Front: The index of the first active element.
- Rear: The index where the next element will be inserted, depending on the chosen implementation convention.
- Size: The number of elements currently stored.
- Capacity: The maximum number of elements the queue can hold.
Maintaining the current size is particularly useful because it makes the distinction between an empty queue and a full queue explicit.
How Wrap-Around Works
The key idea behind a circular queue is wrap-around indexing. When an index reaches the capacity of the array, it returns to zero.
This can be expressed using the modulo operator:
nextIndex = (currentIndex + 1) % capacity
For a queue with a capacity of five, the index sequence becomes:
0 → 1 → 2 → 3 → 4 → 0 → 1 → 2 → ...
This is what allows the queue to reuse positions at the beginning of the array.
Circular Queue Operations
The main operations are similar to a standard queue, but the index movement is circular.
| Operation | Purpose | Typical Complexity |
|---|---|---|
| Enqueue | Adds an element at the rear | O(1) |
| Dequeue | Removes the front element | O(1) |
| Peek | Reads the front element | O(1) |
| IsEmpty | Checks whether the queue is empty | O(1) |
| IsFull | Checks whether the queue is full | O(1) |
Enqueue in a Circular Queue
Enqueue adds a new element at the current rear position. After inserting the element, the rear moves to the next position using circular indexing.
rear = (rear + 1) % capacity
Before inserting, the implementation must ensure that the queue is not full.
Capacity = 5
Index: 0 1 2 3 4
↓ ↓ ↓ ↓ ↓
Queue: [10] [20] [30] [ ] [ ]
↑
rear
Enqueue(40)
Queue: [10] [20] [30] [40] [ ]
↑
rear
Dequeue in a Circular Queue
Dequeue removes the element at the front. After removal, the front moves to the next circular position.
front = (front + 1) % capacity
No other elements need to be shifted.
Before:
[10] [20] [30] [40] [ ]
↑
front
Dequeue()
After:
[ ] [20] [30] [40] [ ]
↑
front
Detecting an Empty Queue
There are several ways to distinguish an empty circular queue. One straightforward approach is to maintain
a size variable.
isEmpty() {
return this.size === 0;
}
When the queue has no elements, size is zero regardless of the current front or rear positions.
Detecting a Full Queue
A circular queue is full when the number of stored elements reaches its capacity.
isFull() {
return this.size === this.capacity;
}
Using an explicit size counter makes full and empty states easy to distinguish. Another implementation strategy is to reserve one array position and use front and rear relationships, but maintaining size is often easier to understand when first learning circular queues.
Circular Queue Implementation in JavaScript
The following implementation uses a fixed-size array, front index, rear index, and size counter.
Here, rear represents the next position where a new element will be inserted.
class CircularQueue {
constructor(capacity) {
this.items = new Array(capacity);
this.capacity = capacity;
this.front = 0;
this.rear = 0;
this.size = 0;
}
enqueue(value) {
if (this.isFull()) {
return false;
}
this.items[this.rear] = value;
this.rear = (this.rear + 1) % this.capacity;
this.size++;
return true;
}
dequeue() {
if (this.isEmpty()) {
return null;
}
const value = this.items[this.front];
this.items[this.front] = undefined;
this.front = (this.front + 1) % this.capacity;
this.size--;
return value;
}
peek() {
return this.isEmpty()
? null
: this.items[this.front];
}
isEmpty() {
return this.size === 0;
}
isFull() {
return this.size === this.capacity;
}
getSize() {
return this.size;
}
}
Using the Circular Queue
A queue with a capacity of three can be used as follows:
const queue = new CircularQueue(3);
queue.enqueue("A");
queue.enqueue("B");
queue.enqueue("C");
console.log(queue.isFull()); // true
console.log(queue.dequeue()); // A
console.log(queue.dequeue()); // B
queue.enqueue("D");
queue.enqueue("E");
console.log(queue.peek()); // C
Notice that after removing A and B, the queue can insert D and E
into the positions that were freed at the beginning of the array.
Step-by-Step Wrap-Around Example
Consider a circular queue with capacity four.
Capacity = 4
Index: 0 1 2 3
[ ] [ ] [ ] [ ]
Insert four elements:
enqueue(10) enqueue(20) enqueue(30) enqueue(40) [10] [20] [30] [40] ↑ front rear → 0
The queue is now full. Remove two elements:
dequeue() → 10
dequeue() → 20
[ ] [ ] [30] [40]
↑
front
The rear is already at the beginning because it wrapped around after reaching the end. New values can therefore reuse indexes zero and one:
enqueue(50)
enqueue(60)
[50] [60] [30] [40]
↑
rear
The logical queue order is still:
Front → 30 → 40 → 50 → 60 → Rear
The physical positions in the array are no longer in simple left-to-right queue order, but the front and rear indexes preserve the logical order.
Logical Order vs Physical Order
This distinction is one of the most important concepts in a circular queue. The queue's logical order may cross the end of the underlying array.
Physical array:
Index: 0 1 2 3 4
[50] [60] [30] [40] [ ]
↑ ↑
rear front
Logical queue:
30 → 40 → 50 → 60
The data structure is therefore circular even though the underlying storage is a normal linear array. The modulo operation provides the connection between the final and first positions.
Why Modulo Is Used
Modulo provides a simple way to wrap an index back to zero when it reaches the array capacity.
const capacity = 5; console.log((0 + 1) % capacity); // 1 console.log((1 + 1) % capacity); // 2 console.log((2 + 1) % capacity); // 3 console.log((3 + 1) % capacity); // 4 console.log((4 + 1) % capacity); // 0
The final calculation is the important one: (4 + 1) % 5 produces 0.
This creates the wrap-around behavior required by the circular queue.
Circular Queue vs Linear Queue
A linear array queue and a circular queue can both implement FIFO behavior, but they manage available storage differently.
| Feature | Linear Array Queue | Circular Queue |
|---|---|---|
| Storage movement | Moves toward the end | Wraps around |
| Space reuse | May require compaction or shifting | Naturally reuses freed positions |
| Capacity | Can use dynamic storage | Commonly fixed |
| Index management | Usually simpler | Requires wrap-around logic |
| Typical use | General dynamic queues | Fixed buffers and reusable storage |
Circular Queue vs Linked-List Queue
A circular queue is commonly implemented with a fixed-size array, while a linked-list queue grows dynamically by creating nodes. Both can provide constant-time enqueue and dequeue operations when properly implemented.
| Characteristic | Circular Queue | Linked-List Queue |
|---|---|---|
| Storage | Fixed-size array is common | Individual nodes |
| Growth | Limited by capacity | Dynamic |
| Enqueue | O(1) | O(1) |
| Dequeue | O(1) | O(1) |
| Memory reuse | Reuses array positions | Allocates nodes as needed |
Applications of Circular Queues
Circular queues are useful when data arrives continuously and a fixed amount of storage should be reused. Common applications include:
- CPU scheduling: Processes can receive turns in a repeating scheduling cycle.
- Network buffers: Incoming or outgoing data can be stored in a reusable fixed-size buffer.
- Streaming systems: Recent data can occupy a fixed-size circular buffer.
- Keyboard or device buffers: Events can be stored until they are consumed.
- Producer-consumer systems: Producers and consumers can share a bounded buffer.
- Logging systems: A fixed amount of recent information can be retained while older entries are overwritten or removed according to application rules.
Circular Queue and Round-Robin Scheduling
A common conceptual application of circular queues is round-robin scheduling. Tasks are processed one after another, and after reaching the final task, processing returns to the first task.
Tasks: A → B → C → D → A → B → C → ... The scheduler cycles through the tasks instead of permanently moving in one direction.
The circular structure naturally represents this repeated progression. Actual operating-system scheduling policies can be more complex, but the circular queue provides a useful model for understanding the rotation of work.
Common Mistakes
- Forgetting to use modulo when advancing front or rear.
- Confusing a full queue with an empty queue when front and rear positions overlap.
- Allowing enqueue when the queue has reached its capacity.
- Failing to update the size after enqueue or dequeue.
- Forgetting that the logical order may cross the physical end of the array.
- Reading the wrong index after the rear wraps around.
- Using a fixed-capacity queue without clearly defining what should happen when it becomes full.
Full and Empty States
A circular queue needs an unambiguous way to identify its state. Using a size counter is one straightforward approach.
Empty: size = 0 Partially filled: 0 < size < capacity Full: size = capacity
This avoids relying only on the relationship between front and rear, because wrap-around can cause those indexes to take values that are otherwise ambiguous.
Handling a Full Queue
What happens when a circular queue is full depends on the application's requirements. An implementation may reject the new element, return a failure value, throw an exception, or use another defined policy.
enqueue(value) {
if (this.isFull()) {
return false;
}
// Insert value...
return true;
}
In some bounded-buffer systems, the oldest value may instead be overwritten when new data arrives. That is a different policy and should be explicitly implemented rather than assumed to be standard queue behavior.
Complexity Analysis
Circular queues are designed to perform their core operations without shifting elements. Index updates and modulo calculations take constant time.
| Operation | Time | Space |
|---|---|---|
| Enqueue | O(1) | O(1) auxiliary operation |
| Dequeue | O(1) | O(1) auxiliary operation |
| Peek | O(1) | O(1) |
| IsEmpty | O(1) | O(1) |
| IsFull | O(1) | O(1) |
The queue itself requires O(n) storage for a capacity of n.
The operations above do not require additional storage proportional to the number of elements.
Practical Example: Fixed-Size Data Buffer
A circular queue can represent a fixed-size buffer where new values continuously arrive and previously consumed positions are reused.
const buffer = new CircularQueue(3);
buffer.enqueue("Data 1");
buffer.enqueue("Data 2");
buffer.enqueue("Data 3");
console.log(buffer.dequeue()); // Data 1
buffer.enqueue("Data 4");
console.log(buffer.dequeue()); // Data 2
console.log(buffer.dequeue()); // Data 3
console.log(buffer.dequeue()); // Data 4
The position previously occupied by Data 1 is reused for Data 4.
This is the main storage-reuse advantage of a circular queue.
Key Takeaways
- A circular queue follows FIFO ordering while allowing the underlying storage to wrap around.
- It is commonly implemented using a fixed-size array.
- Front identifies the next element to remove, while rear identifies the next insertion position in the implementation shown here.
- The modulo operator allows indexes to wrap from the last position back to zero.
- Maintaining a size counter makes full and empty states easy to distinguish.
- Enqueue, dequeue, peek, isEmpty, and isFull can all run in O(1) time.
- Circular queues reuse positions freed by dequeue operations.
- They are useful for fixed-size buffers, streaming systems, scheduling, and producer-consumer workflows.