Skip to content

level 4 · Linear structures

Circular Queue

A queue in a fixed array that never shuffles — the pointers go round instead.

9 min 70 XP

what is it

Start here

The Queue lesson ended with a warning: build a queue on a plain array and every dequeue shuffles everything left — quietly turning an O(1) operation into O(n). A circular queue is the fix.

The trick is to stop moving the data and start moving the pointers. Keep a fixed array and two numbers: where the queue starts (head) and how many items it holds (size). To dequeue, don't shift anything — just move head forward one.

Of course head eventually runs off the end of the array. So you wrap it: `head = (head + 1) % capacity`. Now head and tail chase each other round and round the array like hands on a clock, endlessly reusing the slots that have been freed behind them. Nothing is ever copied.

The price is a fixed capacity. When it's full, it's full — a new item is refused rather than the array being grown. That's usually a feature, not a bug: it's exactly what you want for a fixed-size buffer, like the last 100 log lines, an audio stream, or a network packet queue.

real-life analogy

Picture it

A revolving sushi belt

The plates don't move to make room — the belt goes round. New sushi goes into whatever slot has just come free behind the last plate. The belt has a fixed number of slots, so when it's full, the chef waits. Nothing is ever carried across the restaurant.

interactive visualization

Watch it run

Fixed capacity of 6. Watch the tail wrap around into freed slots. −1 means empty.

  1. -1
    0
  2. -1
    1
  3. -1
    2
  4. -1
    3
  5. -1
    4
  6. -1
    5

A fixed array of 6 slots — and it never shifts anything. Instead of moving the data, a circular queue moves the head pointer, and wraps it around the end. −1 means an empty slot.

step 01/11

  • comparing
  • moving
  • in final place
  • ruled out
1class CircularQueue {
2 constructor(capacity) {
3 this.a = new Array(capacity).fill(null);
4 this.cap = capacity;
5 this.head = 0;
6 this.size = 0;
7 }
8 enqueue(v) {
9 if (this.size === this.cap) return false; // full
10 const tail = (this.head + this.size) % this.cap;
11 this.a[tail] = v;
12 this.size++;
13 return true;
14 }
15 dequeue() {
16 if (this.size === 0) return null; // empty
17 const v = this.a[this.head];
18 this.a[this.head] = null;
19 this.head = (this.head + 1) % this.cap; // wrap around
20 this.size--;
21 return v;
22 }
23}

variables right now

capacity
6
size
0
head
0
comparisons 0moves 0

the dry run · every step, in words

11 steps

complexity

What it costs

best case
O(1)
average
O(1)
worst case
O(1)
extra memory
O(capacity)

Both enqueue and dequeue are O(1) forever, because the data never moves — only the head index does, and % capacity wraps it round. The memory is fixed up front, which is exactly why it suits buffers and streams.

  • O(1) · this one
  • O(log n)
  • O(n)
  • O(n log n)
  • O(n²)
input size →work →

common mistakes

Common traps

  • Forgetting the % capacity when advancing head or tail.

    Without the modulo, the pointer runs off the end of the array and crashes. The wrap-around *is* the circular queue.

  • Using head == tail to mean 'empty'.

    It's ambiguous — head equals tail both when the queue is empty and when it's completely full. Track the size separately, or leave one slot deliberately unused.

  • Trying to enqueue into a full queue.

    It has a fixed capacity by design. Check `size == capacity` first and refuse, or you'll silently overwrite an item that hasn't been served yet.

quiz

Check yourself

Three questions. Get them all right to finish the lesson.

+70 XP

01What problem does a circular queue solve?

02How does the tail get back to the start of the array?

03Why is `head == tail` a bad test for 'empty'?

practice

Solve it on LeetCode

You've seen it run — now write it yourself. These are real LeetCode problems that use exactly this idea, from gentlest to toughest.