Circular Queue
What Is a Circular Queue?
A circular queue is a fixed-size queue that treats its underlying array as a ring — when the rear pointer reaches the end of the array, it wraps back to index 0 instead of stopping. Elements never shift; only the front and rear pointers move.
LINEAR ARRAY QUEUE — the wasted space problem:
Initial: [_, _, _, _, _] front=0, rear=0
0 1 2 3 4
After 3 enqueues:
[A, B, C, _, _] front=0, rear=3
After 2 dequeues:
[_, _, C, _, _] front=2, rear=3
↑ WASTED SPACE
Enqueue D: [_, _, C, D, _] rear=4
Enqueue E: [_, _, C, D, E] rear=5 — OVERFLOW even though 2 slots are free!
The wasted slots at indices 0–1 can never be reused without shifting.
A queue of capacity 5 can hold only 3 elements after 2 dequeues.
CIRCULAR QUEUE — the solution:
rear = (rear + 1) % capacity ← modulo wraps around
After same operations:
[_, _, C, D, E] front=2, rear=0 (rear wrapped!)
0 1 2 3 4
Enqueue F: data[rear=0] = F, rear=(0+1)%5=1
[F, _, C, D, E] front=2, rear=1
All 5 slots in use — no wasted space!
The Core Mechanics: Modulo Arithmetic
Every circular queue operation uses modulo to wrap indices:
Enqueue: data[rear] = value rear = (rear + 1) % capacity Dequeue: value = data[front] front = (front + 1) % capacity Index of the i-th element (from front): data[(front + i) % capacity] How modulo creates the ring: capacity = 5 (0 + 1) % 5 = 1 → slot 1 (1 + 1) % 5 = 2 → slot 2 (2 + 1) % 5 = 3 → slot 3 (3 + 1) % 5 = 4 → slot 4 (4 + 1) % 5 = 0 → slot 0 ← WRAP-AROUND (0 + 1) % 5 = 1 → slot 1 ← and so on
The Empty vs Full Disambiguation Problem
This is the most subtle aspect of circular queue design. When using only front and rear pointers, two states look identical:
Empty queue: front == rear (both at 0) [_, _, _, _, _] front=0, rear=0 Full queue after 5 enqueues and wrap: [A, B, C, D, E] front=0, rear=0 ← front == rear again! How do you distinguish them? Three standard approaches:
Approach 1: Size Counter (Recommended)
Track the number of elements explicitly. isEmpty: size == 0 isFull: size == capacity Pros: Unambiguous, simple, O(1) Cons: One extra field
Approach 2: Sacrifice One Slot
Declare the queue full when (rear + 1) % capacity == front. This intentionally wastes one slot — actual capacity = array_size - 1. isEmpty: front == rear isFull: (rear + 1) % capacity == front Pros: No extra field needed Cons: Wastes one slot; array of size n holds only n-1 elements
Approach 3: Boolean Full Flag
Track a boolean `isFull` that is set on enqueue and cleared on dequeue. isEmpty: front == rear && !isFull isFull: the `isFull` flag itself Pros: No wasted slot, no size counter Cons: Extra boolean, slightly more complex logic
This page uses Approach 1 (size counter) — the clearest for implementation and interviews.
Complete Implementation
1public class CircularQueue<T> {
2
3 private final Object[] data; // Fixed-size underlying array
4 private int front; // Index of the front element
5 private int rear; // Index where next element will be placed
6 private int size; // Number of current elements
7 private final int capacity;
8
9 public CircularQueue(int capacity) {
10 if (capacity <= 0) throw new IllegalArgumentException("Capacity must be > 0");
11 this.capacity = capacity;
12 this.data = new Object[capacity];
13 this.front = 0;
14 this.rear = 0;
15 this.size = 0;
16 }
17
18 // ENQUEUE — add to back — O(1)
19 public boolean enqueue(T value) {
20 if (isFull()) return false; // Return false instead of throwing
21 data[rear] = value;
22 rear = (rear + 1) % capacity; // Wrap with modulo
23 size++;
24 return true;
25 }
26
27 // DEQUEUE — remove from front — O(1)
28 @SuppressWarnings("unchecked")
29 public T dequeue() {
30 if (isEmpty()) return null; // Return null instead of throwing
31 T value = (T) data[front];
32 data[front] = null; // Help GC — clear the slot
33 front = (front + 1) % capacity; // Wrap with modulo
34 size--;
35 return value;
36 }
37
38 // PEEK FRONT — O(1)
39 @SuppressWarnings("unchecked")
40 public T peekFront() {
41 if (isEmpty()) return null;
42 return (T) data[front];
43 }
44
45 // PEEK REAR — O(1)
46 @SuppressWarnings("unchecked")
47 public T peekRear() {
48 if (isEmpty()) return null;
49 int rearIdx = (rear - 1 + capacity) % capacity; // One step behind rear
50 return (T) data[rearIdx];
51 }
52
53 // STATE QUERIES — O(1)
54 public boolean isEmpty() { return size == 0; }
55 public boolean isFull() { return size == capacity; }
56 public int size() { return size; }
57 public int capacity() { return capacity; }
58
59 // ELEMENT AT LOGICAL INDEX i (0 = front) — O(1)
60 @SuppressWarnings("unchecked")
61 public T elementAt(int i) {
62 if (i < 0 || i >= size) throw new IndexOutOfBoundsException("Index: " + i);
63 return (T) data[(front + i) % capacity];
64 }
65
66 // CLEAR — O(n) to null out slots for GC
67 public void clear() {
68 for (int i = 0; i < size; i++) {
69 data[(front + i) % capacity] = null;
70 }
71 front = 0;
72 rear = 0;
73 size = 0;
74 }
75
76 @Override
77 public String toString() {
78 if (isEmpty()) return "CircularQueue: [] (empty)";
79 StringBuilder sb = new StringBuilder("CircularQueue (front→back): [");
80 for (int i = 0; i < size; i++) {
81 sb.append(data[(front + i) % capacity]);
82 if (i < size - 1) sb.append(", ");
83 }
84 return sb.append("] | front=").append(front)
85 .append(", rear=").append(rear)
86 .append(", size=").append(size)
87 .append("/").append(capacity).toString();
88 }
89
90 public static void main(String[] args) {
91 CircularQueue<Integer> cq = new CircularQueue<>(5);
92
93 // Fill the queue
94 for (int i = 1; i <= 5; i++) cq.enqueue(i * 10);
95 System.out.println(cq);
96
97 System.out.println("isFull: " + cq.isFull()); // true
98 System.out.println("peekFront: " + cq.peekFront()); // 10
99 System.out.println("peekRear: " + cq.peekRear()); // 50
100 System.out.println("elementAt(2): " + cq.elementAt(2)); // 30
101
102 // Dequeue two, enqueue two — demonstrate wrap-around
103 System.out.println("\nDequeue: " + cq.dequeue()); // 10
104 System.out.println("Dequeue: " + cq.dequeue()); // 20
105 System.out.println(cq);
106
107 cq.enqueue(60);
108 cq.enqueue(70);
109 System.out.println(cq); // Rear has wrapped around
110
111 // Attempt to enqueue when full
112 boolean added = cq.enqueue(99);
113 System.out.println("Enqueue when full: " + added); // false
114 }
115}Output:
CircularQueue (front→back): [10, 20, 30, 40, 50] | front=0, rear=0, size=5/5
isFull: true
peekFront: 10
peekRear: 50
elementAt(2): 30
Dequeue: 10
Dequeue: 20
CircularQueue (front→back): [30, 40, 50] | front=2, rear=0, size=3/5
CircularQueue (front→back): [30, 40, 50, 60, 70] | front=2, rear=2, size=5/5
Enqueue when full: false
Dry Run: Full Wrap-Around Sequence
Tracing all three index variables through a complete cycle:
CircularQueue, capacity=4
Initial: data=[_,_,_,_], front=0, rear=0, size=0
enqueue(A):
data[0]=A, rear=(0+1)%4=1, size=1
data=[A,_,_,_] front=0, rear=1
enqueue(B):
data[1]=B, rear=2, size=2
data=[A,B,_,_] front=0, rear=2
enqueue(C):
data[2]=C, rear=3, size=3
data=[A,B,C,_] front=0, rear=3
enqueue(D):
data[3]=D, rear=(3+1)%4=0, size=4 ← rear WRAPS to 0
data=[A,B,C,D] front=0, rear=0, size=4
isFull: size==capacity → true
dequeue():
value=data[0]=A, data[0]=null, front=(0+1)%4=1, size=3
data=[_,B,C,D] front=1, rear=0
dequeue():
value=data[1]=B, front=2, size=2
data=[_,_,C,D] front=2, rear=0
enqueue(E):
data[0]=E (rear=0 — slot 0 is now free!), rear=1, size=3
data=[E,_,C,D] front=2, rear=1 ← E REUSES index 0
enqueue(F):
data[1]=F, rear=2, size=4
data=[E,F,C,D] front=2, rear=2, size=4
isFull: true
Logical order (front→back): data[2]=C, data[3]=D, data[0]=E, data[1]=F
→ [C, D, E, F] using (front + i) % capacity for i=0..3
peekRear():
rearIdx = (rear - 1 + capacity) % capacity
= (2 - 1 + 4) % 4 = 5 % 4 = 1 → data[1] = F ✓
This confirms: a queue of capacity 4 can hold all 4 elements
at any time, regardless of how many wrap-arounds have occurred.
The peekRear Formula
Reading the last element requires going one step behind rear. Because rear might be 0 (just wrapped), naively doing rear - 1 gives -1. The correct formula:
rearIndex = (rear - 1 + capacity) % capacity
Why not just (rear - 1) % capacity?
If rear=0: (0 - 1) % 5 = -1 in Python (correct! Python % always positive)
(0 - 1) % 5 = -1 in Java/C++ (WRONG — Java/C++ % can be negative)
(rear - 1 + capacity) % capacity:
If rear=0: (0 - 1 + 5) % 5 = 4 % 5 = 4 ✓
If rear=3: (3 - 1 + 5) % 5 = 7 % 5 = 2 ✓
Always gives a valid non-negative index.
Rule: whenever subtracting from an index that could go negative,
always add capacity before applying modulo.
Comparing the Three Full/Empty Disambiguation Approaches
All three approaches produce a correct circular queue. The choice affects one slot and one extra field.
1// Approach 2: Sacrifice one slot — no size counter
2public class CircularQueueNoCounter<T> {
3
4 private final Object[] data;
5 private int front;
6 private int rear;
7 private final int capacity; // Array size = capacity + 1 (one slot sacrificed)
8
9 public CircularQueueNoCounter(int logicalCapacity) {
10 this.capacity = logicalCapacity + 1; // Allocate one extra
11 this.data = new Object[this.capacity];
12 this.front = 0;
13 this.rear = 0;
14 }
15
16 public boolean enqueue(Object value) {
17 if (isFull()) return false;
18 data[rear] = value;
19 rear = (rear + 1) % capacity;
20 return true;
21 }
22
23 @SuppressWarnings("unchecked")
24 public T dequeue() {
25 if (isEmpty()) return null;
26 T value = (T) data[front];
27 front = (front + 1) % capacity;
28 return value;
29 }
30
31 // isEmpty: front == rear (unambiguous because full never reaches this state)
32 public boolean isEmpty() { return front == rear; }
33
34 // isFull: next rear slot would be front
35 public boolean isFull() { return (rear + 1) % capacity == front; }
36
37 // Size = logical distance between front and rear
38 public int size() {
39 return (rear - front + capacity) % capacity;
40 }
41
42 public static void main(String[] args) {
43 // Logical capacity 4 — array size 5 (one slot sacrificed)
44 CircularQueueNoCounter<Integer> q = new CircularQueueNoCounter<>(4);
45
46 q.enqueue(1); q.enqueue(2); q.enqueue(3); q.enqueue(4);
47 System.out.println("isFull: " + q.isFull()); // true
48 System.out.println("size: " + q.size()); // 4
49 System.out.println("Dequeue: " + q.dequeue()); // 1
50 System.out.println("isEmpty: " + q.isEmpty()); // false
51 }
52}LeetCode: Design Circular Queue
This is the direct interview problem for circular queues. The interface matches exactly what we have built.
Design your implementation of the circular queue. The circular queue is a linear data structure in which the operations are performed based on FIFO principle, and the last position is connected back to the first position to make a circle. Operations: MyCircularQueue(k) — Constructor, set size to k enQueue(value) — Insert, return true if successful deQueue() — Delete from front, return true if successful Front() — Get front item, return -1 if empty Rear() — Get last item, return -1 if empty isEmpty() — Checks if empty isFull() — Checks if full
The implementation above satisfies all requirements. Key mapping:
enQueue(value) → enqueue(value) — returns bool deQueue() → dequeue() returns non-null → true, null → false Front() → peekFront() ?? -1 Rear() → peekRear() ?? -1 isEmpty() → isEmpty() isFull() → isFull()
Real-World Applications
1. Audio/Video Streaming Buffer
Media players pre-buffer frames in a circular queue.
Producer (decoder) writes frames to the rear.
Consumer (renderer) reads frames from the front.
Fixed size prevents unbounded memory growth.
When full: decoder pauses (backpressure).
When empty: player stalls ("buffering...").
2. CPU Round-Robin Scheduling
Processes are stored in a circular queue.
CPU dequeues a process, gives it a time slice.
If not finished, re-enqueues it at the rear.
Every process gets equal CPU time in rotation.
The queue never empties during normal execution.
3. Network Packet Buffers
Network interface cards use circular ring buffers.
Packets arrive at the rear; the network stack reads from the front.
Fixed size means no dynamic allocation in the hot path.
Overflow (dropped packets) is preferable to unbounded memory.
4. Producer-Consumer Decoupling
Producer writes data at its own rate to the circular buffer.
Consumer reads data at its own rate.
If producer is faster: buffer fills → producer waits.
If consumer is faster: buffer empties → consumer waits.
The fixed size creates natural rate-matching backpressure.
5. Keyboard Input Buffer
OS stores keystrokes in a fixed circular buffer (~256 bytes).
Keyboard interrupt handler writes to the rear (ISR context).
Application reads from the front (process context).
If the buffer fills: key events are dropped (rare, fast typist).
6. Sliding Window Algorithms (Monotonic Deque)
Sliding window maximum uses a circular deque.
Elements expire from the front (outside window).
New elements enter from the rear.
Fixed-size circular structure gives O(1) both ends.
Operation Complexity Summary
| Operation | Time | Space | Notes |
|---|---|---|---|
enqueue(value) | O(1) | O(1) | Direct array write + modulo |
dequeue() | O(1) | O(1) | Direct array read + modulo |
peekFront() | O(1) | O(1) | data[front] |
peekRear() | O(1) | O(1) | data[(rear-1+cap)%cap] |
isEmpty() | O(1) | O(1) | size == 0 |
isFull() | O(1) | O(1) | size == capacity |
elementAt(i) | O(1) | O(1) | data[(front+i)%cap] |
clear() | O(n) | O(1) | Must null slots for GC |
| Build from n elements | O(n) | O(capacity) | n enqueues |
| Space (entire queue) | — | O(capacity) | Fixed pre-allocated array |
Common Mistakes
Using front == rear to check both empty and full. This is the classic bug — both states produce front == rear. Always use a size counter, a sacrificed slot, or an explicit full boolean. The front == rear ambiguity is the #1 circular queue mistake in interviews.
Subtracting without adding capacity before modulo. (rear - 1) % capacity gives -1 in Java and C++ when rear == 0. Always write (rear - 1 + capacity) % capacity when computing the previous index. Python's modulo is always non-negative so -1 % 5 == 4 works — but the portable habit is to always add capacity.
Forgetting to null out dequeued slots in Java. The array slot still holds the object reference after the pointer advances. The object cannot be garbage collected. In long-running systems this causes a memory leak proportional to the queue's capacity. Always set data[front] = null before advancing front.
Off-by-one in the isFull check for the sacrificed-slot approach. The condition is (rear + 1) % capacity == front — not rear == front. The queue is full when the NEXT rear position would equal front, not when they are currently equal (that is the empty check).
Initializing capacity to the user's value instead of capacity + 1 in the sacrificed-slot approach. The array must have one extra slot to distinguish full from empty. If you allocate exactly logicalCapacity elements, your "full" state matches your "empty" state — the sacrificed slot is missing.
Interview Questions
Q: Why is a circular queue better than a linear array queue?
A linear array queue suffers from wasted space — as elements are dequeued, the front index advances but those slots can never be reused without an O(n) element shift. After n dequeues, the remaining elements occupy the last n positions; the first n positions are empty but inaccessible. A circular queue reuses those front positions by wrapping the rear pointer back to 0 using modulo. The total usable capacity always equals the array size, regardless of how many wrap-arounds have occurred.
Q: How do you distinguish an empty circular queue from a full one when using only front and rear pointers?
You cannot — both states produce front == rear when using only two index pointers. The standard solutions are: (1) maintain a size counter — clearest and most common; (2) sacrifice one slot — declare full when (rear + 1) % capacity == front, costing one unused slot but needing no extra field; (3) use a boolean full flag — set on enqueue to capacity, cleared on any dequeue.
Q: What is the time complexity of accessing the i-th element from the front in a circular queue?
O(1). The i-th element from the front is at physical index (front + i) % capacity — a single arithmetic operation and one array access. This is the key advantage of array-backed circular queues over linked-list queues: the linked-list equivalent requires O(i) pointer hops.
Q: How does the peekRear operation avoid a negative index?
The most recently enqueued element is at rear - 1. When rear == 0, this is -1 — an invalid index. The correct formula is (rear - 1 + capacity) % capacity. Adding capacity before the modulo guarantees a non-negative result in all languages. In Python, (-1) % 5 == 4 works correctly, but the + capacity form is language-agnostic.
FAQs
Can a circular queue resize automatically?
A fixed circular queue cannot resize — it has a pre-allocated array and no mechanism to grow. If you need automatic resizing, a dynamic circular queue (as implemented in the implementation page) doubles the capacity and re-linearizes elements during resize. The standard collections.deque in Python and ArrayDeque in Java are dynamic — they grow automatically and are backed by circular-array-like structures internally.
What is the difference between a circular queue and a circular buffer?
They are the same concept with different emphases. "Circular queue" emphasises the FIFO data structure and its operations. "Circular buffer" or "ring buffer" emphasises the fixed-size memory management aspect — often used in hardware and systems programming contexts (network drivers, audio buffers). The implementation is identical; only the context differs.
Why do circular queues appear in hardware and embedded systems?
Hardware DMA (Direct Memory Access) controllers and network interface cards use ring buffers because they have no dynamic memory allocation — the buffer is allocated at startup with a fixed size. The producer (hardware) and consumer (driver software) share the same memory area without locks in many designs by using carefully separated indices. The circular structure gives O(1) reads and writes with zero allocation overhead — critical for real-time and interrupt-driven contexts.
Is the circular queue the same as the circular linked list?
No. A circular queue is array-backed — it uses modulo arithmetic to wrap a linear array into a logical ring. A circular linked list is pointer-based — the tail's next points to the head. Both model cyclic structures, but a circular queue has O(1) random access (by logical index) while a circular linked list has O(n) access. Circular queues use contiguous memory; circular linked lists use scattered heap nodes.
Quick Quiz
Question 1: A circular queue has capacity=4, front=3, rear=3, size=0. You enqueue one element. What are the new values?
- ›A)
front=3,rear=3,size=1 - ›B)
front=3,rear=0,size=1 - ›C)
front=0,rear=1,size=1 - ›D)
front=3,rear=4,size=1
Answer: B) front=3, rear=0, size=1. Enqueue stores the value at data[rear=3], then sets rear = (3+1)%4 = 0. The front does not change on enqueue. size increments to 1. rear wraps to 0 — the circular behaviour.
Question 2: For a circular queue with capacity=5, front=1, rear=3, size=2, what is peekRear()?
- ›A)
data[3] - ›B)
data[2] - ›C)
data[(3-1+5)%5] = data[2] - ›D)
data[(3+1)%5] = data[4]
Answer: C) data[2]. The last enqueued element is at the index one before rear. The formula is (rear - 1 + capacity) % capacity = (3 - 1 + 5) % 5 = 7 % 5 = 2. So peekRear() returns data[2].
Question 3: In the "sacrifice one slot" approach, a circular queue with a logical capacity of 4 allocates how many array slots?
- ›A) 3 — one fewer to save memory
- ›B) 4 — exactly the logical capacity
- ›C) 5 — one extra to enable unambiguous isEmpty/isFull
- ›D) 8 — double for safety
Answer: C) 5 — one extra slot. The queue is declared full when (rear + 1) % arraySize == front. This condition can never be true when arraySize == logicalCapacity because at max fill, rear would equal front — the empty state. Adding one extra slot allows a distinct "full" state where (rear + 1) % 5 == front without conflicting with the empty rear == front condition.
Question 4: What is the correct index of the 3rd logical element (i=2) from the front in a circular queue with front=3, capacity=5?
- ›A)
data[2] - ›B)
data[(3+2)%5] = data[0] - ›C)
data[3+2] = data[5]— array out of bounds - ›D)
data[(3+2+5)%5] = data[0]
Answer: B) data[(3+2)%5] = data[0]. The formula for the i-th logical element is data[(front + i) % capacity] = data[(3 + 2) % 5] = data[5 % 5] = data[0]. This is correct — the element at logical index 2 is physically at array index 0 due to wrap-around.
Summary
A circular queue solves the wasted-space problem of linear array queues by treating the fixed array as a ring — when rear reaches the end, it wraps to index 0 using modulo arithmetic. Front positions freed by dequeuing are reused immediately.
The three index variables: front (next to dequeue), rear (next empty slot), size (current count).
Core mechanics:
- ›Enqueue:
data[rear] = value; rear = (rear + 1) % capacity; size++ - ›Dequeue:
value = data[front]; front = (front + 1) % capacity; size-- - ›peekRear:
data[(rear - 1 + capacity) % capacity] - ›elementAt(i):
data[(front + i) % capacity]
Empty/full disambiguation — three approaches:
- ›Size counter (recommended):
isEmpty: size==0,isFull: size==capacity - ›Sacrifice one slot:
isEmpty: front==rear,isFull: (rear+1)%cap==front; array size = logical capacity + 1 - ›Boolean flag:
isEmpty: !full && front==rear,isFull: full
Critical formula rule: when subtracting from an index, always add capacity before modulo to prevent negative indices — (rear - 1 + capacity) % capacity, not (rear - 1) % capacity.
Real-world uses: streaming media buffers, round-robin CPU scheduling, network packet buffers, keyboard input ISR buffers, sliding window monotonic deque.
In the next topic, you will explore the Deque (double-ended queue) — extending the circular queue to support O(1) insertion and removal at both ends, and its critical role in sliding window maximum problems.