15% off all plans & roadmaps Use code
See plansOpening your learning path
Progress is saved as you study.
A circular queue is a fixed-capacity array queue whose indices wrap from the last position back to index 0. Enqueue writes at rear and dequeue reads at front, and each index advances with (index + 1) mod capacity. Nothing shifts, so both operations are O(1), and a size field tells full from empty.
| Advance an index | (index + 1) mod capacity |
|---|---|
| enqueue and dequeue | O(1) each, no shifting |
| Empty | size == 0 |
| Full | size == capacity |
| Queue order | start at front, visit size cells, wrap with mod |
| Storage | O(C) for capacity C |
Assume ordinary queue operations:
A fixed-capacity circular queue stores values in an array. After a dequeue, it does not shift elements. Its indices wrap from the last array position back to index 0.
We will store four fields:
cells: an array with fixed capacity.front: the physical index of the next value to dequeue.rear: the physical index of the next free position for enqueue.size: the number of values currently in the queue.The queue is:
size == 0size == capacityTo move an index forward, use:
1(index + 1) mod capacityFor a capacity of 4, advancing from index 3 gives:
1(3 + 1) mod 4 = 0Use a circular queue with capacity 4.
Perform these operations in order:
1enqueue(4), enqueue(7), enqueue(2), dequeue(), dequeue(), enqueue(9), enqueue(5)Start with four empty cells.
| Physical index | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| Cell value | _ | _ | _ | _ |
1front = 0
2rear = 0
3size = 0At the start, front and rear both equal 0. The queue is empty because size is 0.
The queue first fills positions from left to right. Dequeues move front forward. Later enqueues reuse earlier physical positions.
| Index | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| Cells | _ | _ | _ | _ |
1front = 0
2rear = 0
3size = 0Logical queue order:
1[]enqueue(4)rear names the next free insertion position. It is 0, so write 4 at index 0.
Then advance rear:
1(0 + 1) mod 4 = 1Increase size.
| Index | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| Cells | 4 | _ | _ | _ |
1front = 0
2rear = 1
3size = 1Logical queue order:
1[4]enqueue(7)Write at rear = 1. Then advance rear to 2.
| Index | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| Cells | 4 | 7 | _ | _ |
1front = 0
2rear = 2
3size = 2Logical queue order:
1[4, 7]enqueue(2)Write at rear = 2. Then advance rear to 3.
| Index | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| Cells | 4 | 7 | 2 | _ |
1front = 0
2rear = 3
3size = 3Logical queue order:
1[4, 7, 2]dequeue()front = 0, so the old logical front is 4.
Read and return 4. Clear the displayed cell. Then advance front:
1(0 + 1) mod 4 = 1Decrease size.
| Index | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| Cells | _ | 7 | 2 | _ |
1return 4
2front = 1
3rear = 3
4size = 2Logical queue order:
1[7, 2]dequeue()front = 1, so return 7.
Advance front to 2 and decrease size.
| Index | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| Cells | _ | _ | 2 | _ |
1return 7
2front = 2
3rear = 3
4size = 1Logical queue order:
1[2]enqueue(9)rear = 3, so write 9 at index 3.
Now advance rear:
1(3 + 1) mod 4 = 0rear wraps from index 3 to index 0.
| Index | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| Cells | _ | _ | 2 | 9 |
1front = 2
2rear = 0
3size = 2Logical queue order:
1[2, 9]enqueue(5)rear = 0, which is free because the earlier dequeues moved front past it.
Write 5 at index 0. Advance rear to 1.
| Index | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| Cells | 5 | _ | 2 | 9 |
1front = 2
2rear = 1
3size = 3Physical index order from 0 through 3 differs from FIFO order.
The logical order begins at front = 2 and visits exactly size = 3 positions:
Front and rear only ever advance by (index + 1) mod 4, so the queue wraps around the same 4 cells. After the sequence, front = 2, rear = 1, size = 3, and reading from front gives [2, 9, 5].
So the logical queue order is:
1[2, 9, 5]Final state:
1cells = [5, _, 2, 9]
2front = 2
3rear = 1
4size = 3Read the queue from front, moving forward one index at a time and wrapping when needed.
At every valid state, these facts remain true:
size values.cells[front] when size > 0.front and advancing size times modulo capacity visits the queue in FIFO order.rear is the next free insertion position.size == 0 means empty.size == capacity means full.These facts form the queue invariant:
The logical queue consists of exactly
sizeelements beginning atfrontand advancing by one modulo capacity;rearalways names the next free insertion position, andsizedistinguishes empty from full.
size distinguishes states with matching front and rear indices. In an empty queue, front can equal rear. After enough operations, a full queue can also have matching index values. Index comparison alone cannot distinguish those states under this convention.
For enqueue(value), check whether space is available.
1size == capacityIf the condition is true, reject the operation. No free insertion position exists.
Otherwise, rear identifies the correct cell:
value at cells[rear].rear with modular arithmetic.size.Write before advancing. rear means “next free position.”
For dequeue(), check whether any value exists:
1size == 0If the condition is true, reject the operation.
Otherwise:
cells[front].front with modular arithmetic.size.Neither operation shifts stored elements. Each successful operation changes one array position and a constant number of fields.
1record CircularQueue
2 cells // fixed array of capacity positions
3 capacity // integer, capacity >= 1
4 front // index of next dequeue position
5 rear // index of next free insertion position
6 size // number of logical queue values11 function CreateCircularQueue(capacity) -> CircularQueue
22 require capacity >= 1
33
44 queue = new CircularQueue
55 queue.cells = new array of length capacity, filled with EMPTY
66 queue.capacity = capacity
77 queue.front = 0
88 queue.rear = 0
99 queue.size = 0
1010 return queueMutation behavior: Creates and returns a new queue. It does not modify an existing queue.
11 function NextIndex(index, capacity) -> integer
22 require 0 <= index < capacity
33 require capacity >= 1
44 return (index + 1) mod capacityHelper contract: Returns the physical index immediately after index, wrapping from capacity - 1 to 0.
11 function Enqueue(queue, value) -> success or FULL
22 if queue.size == queue.capacity
33 return FULL
44
55 queue.cells[queue.rear] = value
66 queue.rear = NextIndex(queue.rear, queue.capacity)
77 queue.size = queue.size + 1
88 return successInputs: A valid circular queue and a value.
Return value: success if insertion occurs; FULL if the queue already contains capacity values.
Mutation behavior: On success, writes one cell and changes rear and size. On FULL, changes nothing.
11 function Dequeue(queue) -> value or EMPTY_QUEUE
22 if queue.size == 0
33 return EMPTY_QUEUE
44
55 value = queue.cells[queue.front]
66 queue.cells[queue.front] = EMPTY
77 queue.front = NextIndex(queue.front, queue.capacity)
88 queue.size = queue.size - 1
99 return valueInputs: A valid circular queue.
Return value: The old logical front value, or EMPTY_QUEUE when no value exists.
Mutation behavior: On success, clears one displayed cell and changes front and size. On EMPTY_QUEUE, changes nothing.
11 function FrontValue(queue) -> value or EMPTY_QUEUE
22 if queue.size == 0
33 return EMPTY_QUEUE
44 return queue.cells[queue.front]11 function QueueSize(queue) -> integer
22 return queue.sizeNeither operation mutates the queue.
Create the queue with capacity 4. Lines 5 through 9 of CreateCircularQueue produce:
1cells = [_, _, _, _]
2front = 0
3rear = 0
4size = 0Enqueue(queue, 4)0 == 4. This is false.4 at cells[rear], which is cells[0].rear = NextIndex(0, 4).
NextIndex returns (0 + 1) mod 4 = 1.size from 0 to 1.success.1cells = [4, _, _, _]
2front = 0
3rear = 1
4size = 1Enqueue(queue, 7)1 == 4. False.7 at cells[1].rear = NextIndex(1, 4) = 2.size from 1 to 2.success.1cells = [4, 7, _, _]
2front = 0
3rear = 2
4size = 2Enqueue(queue, 2)2 == 4. False.2 at cells[2].rear = NextIndex(2, 4) = 3.size from 2 to 3.success.1cells = [4, 7, 2, _]
2front = 0
3rear = 3
4size = 3Dequeue(queue)size == 0. 3 == 0 is false.cells[front], which is cells[0] = 4.cells[0].front = NextIndex(0, 4) = 1.size from 3 to 2.4.1cells = [_, 7, 2, _]
2front = 1
3rear = 3
4size = 2Dequeue(queue)2 == 0. False.cells[1] = 7.cells[1].front = NextIndex(1, 4) = 2.size from 2 to 1.7.1cells = [_, _, 2, _]
2front = 2
3rear = 3
4size = 1Enqueue(queue, 9)1 == 4. False.9 at cells[rear], which is cells[3].rear = NextIndex(3, 4).
NextIndex returns (3 + 1) mod 4 = 0.size from 1 to 2.success.1cells = [_, _, 2, 9]
2front = 2
3rear = 0
4size = 2Enqueue(queue, 5)2 == 4. False.5 at cells[rear], which is cells[0].rear = NextIndex(0, 4) = 1.size from 2 to 3.success.1cells = [5, _, 2, 9]
2front = 2
3rear = 1
4size = 3Starting at front = 2 and visiting three positions gives:
1cells[2] = 2
2cells[3] = 9
3cells[0] = 5So the queue order is:
1[2, 9, 5]Enqueue and Dequeue contain no traversal loop. Each operation changes a fixed number of fields. Correctness follows from establishing the queue invariant at initialization and preserving it during each successful operation.
CreateCircularQueue creates:
1front = 0
2rear = 0
3size = 0Because size is zero, the logical queue contains zero elements. rear = 0 names the first free position. The invariant holds for a new queue.
Assume the invariant holds before Enqueue, and size < capacity.
Because the queue is not full, rear names a free insertion position. Line 5 writes the new value there. The old logical queue remains unchanged, and the new value is appended after all old logical values.
Line 6 advances rear by one modulo capacity, so it again names the next free insertion position. Line 7 increases size by one, matching the one newly stored logical value.
After enqueue:
rear still names the next free position.The invariant holds after enqueue.
If size == capacity, the operation returns FULL before changing anything. The invariant remains true.
Assume the invariant holds before Dequeue, and size > 0.
Because the queue is not empty, front identifies the old logical front. Line 5 saves that value, so the returned value is the oldest stored logical value.
Line 6 clears that displayed position. Line 7 advances front by one modulo capacity, making it point to the value that was second in logical order, if one exists. Line 8 decreases size by one.
The remaining logical values keep their previous relative order. Only the old front has been removed. FIFO order remains correct, and the invariant holds after dequeue.
If size == 0, the operation returns EMPTY_QUEUE before changing anything. The invariant remains true.
The invariant holds after creation, and every successful enqueue or dequeue preserves it:
size == capacity,size == 0,front and moves modulo capacity.Consider Enqueue.
It performs:
That is a constant number of operations, regardless of the queue capacity or current size.
1Enqueue time: O(1)Consider Dequeue.
It performs:
That is also a constant number of operations.
1Dequeue time: O(1)FrontValue reads the stored front index and one array position. QueueSize reads one stored field.
1FrontValue time: O(1)
2QueueSize time: O(1)The queue owns an array with capacity C, plus the constant-sized fields capacity, front, rear, and size.
1Queue storage: O(C)
2Auxiliary temporary space per operation: O(1)No operation shifts elements through the array.
Incorrect update:
1rear = rear + 1Smallest exposing situation:
1capacity = 4
2rear = 3
3enqueue(9)Wrong result:
1rear = 4Index 4 is outside a capacity-four array.
Correction:
1rear = (rear + 1) mod capacityThe correction changes rear from 3 to 0.
front == rear as full without extra stateIncorrect full test:
1if front == rear
2 return FULLSmallest exposing input:
1new queue with capacity 4
2front = 0
3rear = 0
4size = 0Wrong result: the newly initialized queue is falsely reported as full.
The same index relationship can occur in more than one logical state. Under this implementation convention, front and rear alone are not enough.
Correction:
1full when size == capacity
2empty when size == 0Incorrect assumption:
1queue order is cells[0] through cells[capacity - 1]Exposing state from the worked example:
1cells = [5, _, 2, 9]
2front = 2
3rear = 1
4size = 3Wrong logical output:
1[5, 2, 9]That reads cells by physical position, not FIFO order.
Correction: start at front and visit exactly size positions modulo capacity:
1index 2 -> 2
2index 3 -> 9
3index 0 -> 5Correct order:
1[2, 9, 5]rear before writingIncorrect enqueue order:
1rear = NextIndex(rear, capacity)
2cells[rear] = valueSmallest exposing input:
1empty queue with capacity 4
2enqueue(4)Starting state:
1front = 0
2rear = 0
3size = 0Wrong result:
1cells = [_, 4, _, _]
2front = 0
3rear = 1The value was written at index 1, while front still says the next dequeue should read index 0.
Correction: under the next-free rear convention, write first and advance second.
1cells[rear] = value
2rear = NextIndex(rear, capacity)| Case | Input | Required result |
|---|---|---|
| Capacity one | enqueue(8), dequeue() | Returns 8; both front and rear wrap to 0. |
| Full queue | Capacity 3: enqueue(1), enqueue(2), enqueue(3), enqueue(4) | The fourth enqueue returns FULL. |
| Empty after wraparound | enqueue(1), dequeue(), enqueue(2), dequeue() | size ends at 0 regardless of index values. |
| Rear wraps | Capacity 4, rear = 3, then enqueue | rear becomes 0. |
| Front wraps | Capacity 4, front = 3, then dequeue | front becomes 0. |
Implement a capacity-limited circular queue with front, rear, and size fields that passes tests for:
Your implementation contract should match this lesson:
rear is the next free insertion position.front is the next dequeue position.rear, then advances rear modulo capacity.front, then advances front modulo capacity.size == 0 identifies an empty queue.size == capacity identifies a full queue.Source packet for topic scope and implementation framing:
1EMPTY = -1 # marks a free cell; stored values are nonnegative
2
3class CircularQueue:
4 def __init__(self, capacity):
5 self.cells = [EMPTY] * capacity
6 self.capacity = capacity
7 self.front = 0 # next value to dequeue
8 self.rear = 0 # next free cell
9 self.size = 0
10
11 def next_index(self, index):
12 return (index + 1) % self.capacity
13
14 def enqueue(self, value):
15 if self.size == self.capacity:
16 return False # FULL
17 self.cells[self.rear] = value # write first, then advance
18 self.rear = self.next_index(self.rear)
19 self.size += 1
20 return True
21
22 def dequeue(self):
23 if self.size == 0:
24 return EMPTY # EMPTY_QUEUE
25 value = self.cells[self.front]
26 self.cells[self.front] = EMPTY
27 self.front = self.next_index(self.front)
28 self.size -= 1
29 return value
30
31 def order(self):
32 return [self.cells[(self.front + k) % self.capacity] for k in range(self.size)]
33
34q = CircularQueue(4)
35for v in (4, 7, 2):
36 q.enqueue(v)
37a = q.dequeue()
38b = q.dequeue()
39print("dequeue:", a, b)
40q.enqueue(9)
41q.enqueue(5)
42print("cells: [" + ", ".join("_" if c == EMPTY else str(c) for c in q.cells) + "]")
43print(f"front={q.front} rear={q.rear} size={q.size}")
44print("order:", q.order())
45print("enqueue(6):", "success" if q.enqueue(6) else "FULL")
46print("enqueue(8):", "success" if q.enqueue(8) else "FULL")1import java.util.ArrayList;
2import java.util.Arrays;
3import java.util.List;
4
5public class Main {
6 static final int EMPTY = -1; // marks a free cell; stored values are nonnegative
7
8 static class CircularQueue {
9 int[] cells;
10 int capacity;
11 int front = 0; // next value to dequeue
12 int rear = 0; // next free cell
13 int size = 0;
14
15 CircularQueue(int capacity) {
16 this.capacity = capacity;
17 cells = new int[capacity];
18 Arrays.fill(cells, EMPTY);
19 }
20
21 int nextIndex(int index) {
22 return (index + 1) % capacity;
23 }
24
25 boolean enqueue(int value) {
26 if (size == capacity) return false; // FULL
27 cells[rear] = value; // write first, then advance
28 rear = nextIndex(rear);
29 size++;
30 return true;
31 }
32
33 int dequeue() {
34 if (size == 0) return EMPTY; // EMPTY_QUEUE
35 int value = cells[front];
36 cells[front] = EMPTY;
37 front = nextIndex(front);
38 size--;
39 return value;
40 }
41
42 List<Integer> order() {
43 List<Integer> out = new ArrayList<>();
44 for (int k = 0; k < size; k++) out.add(cells[(front + k) % capacity]);
45 return out;
46 }
47 }
48
49 public static void main(String[] args) {
50 CircularQueue q = new CircularQueue(4);
51 for (int v : new int[]{4, 7, 2}) q.enqueue(v);
52 int a = q.dequeue();
53 int b = q.dequeue();
54 System.out.println("dequeue: " + a + " " + b);
55 q.enqueue(9);
56 q.enqueue(5);
57 StringBuilder sb = new StringBuilder("cells: [");
58 for (int i = 0; i < q.capacity; i++) {
59 if (i > 0) sb.append(", ");
60 sb.append(q.cells[i] == EMPTY ? "_" : String.valueOf(q.cells[i]));
61 }
62 System.out.println(sb.append("]"));
63 System.out.println("front=" + q.front + " rear=" + q.rear + " size=" + q.size);
64 System.out.println("order: " + q.order());
65 System.out.println("enqueue(6): " + (q.enqueue(6) ? "success" : "FULL"));
66 System.out.println("enqueue(8): " + (q.enqueue(8) ? "success" : "FULL"));
67 }
68}1#include <iostream>
2#include <vector>
3using namespace std;
4
5const int EMPTY = -1; // marks a free cell; stored values are nonnegative
6
7struct CircularQueue {
8 vector<int> cells;
9 int capacity;
10 int front = 0; // next value to dequeue
11 int rear = 0; // next free cell
12 int size = 0;
13
14 CircularQueue(int c) : cells(c, EMPTY), capacity(c) {}
15
16 int nextIndex(int index) { return (index + 1) % capacity; }
17
18 bool enqueue(int value) {
19 if (size == capacity) return false; // FULL
20 cells[rear] = value; // write first, then advance
21 rear = nextIndex(rear);
22 size++;
23 return true;
24 }
25
26 int dequeue() {
27 if (size == 0) return EMPTY; // EMPTY_QUEUE
28 int value = cells[front];
29 cells[front] = EMPTY;
30 front = nextIndex(front);
31 size--;
32 return value;
33 }
34
35 vector<int> order() {
36 vector<int> out;
37 for (int k = 0; k < size; k++) out.push_back(cells[(front + k) % capacity]);
38 return out;
39 }
40};
41
42int main() {
43 CircularQueue q(4);
44 for (int v : {4, 7, 2}) q.enqueue(v);
45 int a = q.dequeue();
46 int b = q.dequeue();
47 cout << "dequeue: " << a << " " << b << endl;
48 q.enqueue(9);
49 q.enqueue(5);
50 cout << "cells: [";
51 for (int i = 0; i < q.capacity; i++) {
52 if (i > 0) cout << ", ";
53 if (q.cells[i] == EMPTY) cout << "_"; else cout << q.cells[i];
54 }
55 cout << "]" << endl;
56 cout << "front=" << q.front << " rear=" << q.rear << " size=" << q.size << endl;
57 vector<int> o = q.order();
58 cout << "order: [";
59 for (size_t i = 0; i < o.size(); i++) cout << (i ? ", " : "") << o[i];
60 cout << "]" << endl;
61 cout << "enqueue(6): " << (q.enqueue(6) ? "success" : "FULL") << endl;
62 cout << "enqueue(8): " << (q.enqueue(8) ? "success" : "FULL") << endl;
63}1const EMPTY = -1; // marks a free cell; stored values are nonnegative
2
3class CircularQueue {
4 constructor(capacity) {
5 this.cells = new Array(capacity).fill(EMPTY);
6 this.capacity = capacity;
7 this.front = 0; // next value to dequeue
8 this.rear = 0; // next free cell
9 this.size = 0;
10 }
11
12 nextIndex(index) {
13 return (index + 1) % this.capacity;
14 }
15
16 enqueue(value) {
17 if (this.size === this.capacity) return false; // FULL
18 this.cells[this.rear] = value; // write first, then advance
19 this.rear = this.nextIndex(this.rear);
20 this.size++;
21 return true;
22 }
23
24 dequeue() {
25 if (this.size === 0) return EMPTY; // EMPTY_QUEUE
26 const value = this.cells[this.front];
27 this.cells[this.front] = EMPTY;
28 this.front = this.nextIndex(this.front);
29 this.size--;
30 return value;
31 }
32
33 order() {
34 const out = [];
35 for (let k = 0; k < this.size; k++) out.push(this.cells[(this.front + k) % this.capacity]);
36 return out;
37 }
38}
39
40const q = new CircularQueue(4);
41for (const v of [4, 7, 2]) q.enqueue(v);
42const a = q.dequeue();
43const b = q.dequeue();
44console.log(`dequeue: ${a} ${b}`);
45q.enqueue(9);
46q.enqueue(5);
47console.log(`cells: [${q.cells.map((c) => (c === EMPTY ? '_' : c)).join(', ')}]`);
48console.log(`front=${q.front} rear=${q.rear} size=${q.size}`);
49console.log(`order: [${q.order().join(', ')}]`);
50console.log(`enqueue(6): ${q.enqueue(6) ? 'success' : 'FULL'}`);
51console.log(`enqueue(8): ${q.enqueue(8) ? 'success' : 'FULL'}`);It is also called a ring buffer or circular buffer. The array is treated as a ring, so the cell after the last one is cell 0.
A simple array queue either shifts every value left on dequeue, which costs O(n), or strands the freed cells at the front. A circular queue moves front forward and reuses those cells, so dequeue is O(1).
A new queue has front == rear == 0 and holds nothing. After capacity enqueues, rear wraps back to the same index as front and the queue is full. Index comparison cannot tell them apart, so keep a size field.
Fixed-size buffers are the usual one: audio, keyboard and network buffers keep the newest bytes in a ring. Round-robin scheduling also cycles through a fixed set of tasks.