5.5 ~40 min medium

Circular Queue

Let front and rear wrap around with the modulo operator, so freed slots are reused. All operations O(1) on a fixed array.

Rule of this site: Don't just watch: implement it yourself, then solve 2–3 problems.

02Mental model

Picture a revolving sushi belt with N plates. The chef places food on the next empty plate; diners take food from the oldest plate. When the chef reaches the end of the belt, they just carry on at the start. Nothing is wasted.

A circular queue is the same fixed array as before, but we treat it as a ring. When an index reaches the last slot, the next step takes it back to 0:

rear  = (rear + 1) % N;   // enqueue
front = (front + 1) % N;  // dequeue

So the slots freed by dequeue are reused by later enqueues. Every operation is still O(1).

Full or empty?

With only front and rear, a full ring and an empty ring can look the same. Two common fixes:

Keep a count (this page): empty when count == 0, full when count == N.
Leave one slot unused: empty when front == rear, full when (rear + 1) % N == front.

Your instructor may use either. Know both.

Printing in order

Start at front and step count times: k = (k + 1) % N. Do not just print q[0..rear].

03Visualize

space play · ←→ step · r reset. The highlighted code line follows each step.

Loading visualizer…

Fill it, dequeue two, then enqueue two more. Watch rear wrap from 4 back to 0.

04C++ code

Compiled and run with g++ -std=c++17; the output below is real. Type it out yourself before you copy it.

circular-queue.cpp42 lines · C++17

Compiler ExplorerRun OnlineGDB

#include <iostream>
using namespace std;

const int N = 5;

class CircularQueue {
    int q[N];
    int front = 0, rear = -1, count = 0;
public:
    bool isFull() const { return count == N; }
    bool isEmpty() const { return count == 0; }
    bool enqueue(int x) {
        if (isFull()) return false;
        rear = (rear + 1) % N;          // wrap around
        q[rear] = x;
        count++;
        return true;
    }
    int dequeue() {
        if (isEmpty()) return -1;
        int x = q[front];
        front = (front + 1) % N;        // wrap around
        count--;
        return x;
    }
    void print() const {
        cout << "[front=" << front << " rear=" << rear << " count=" << count << "] ";
        for (int i = 0, k = front; i < count; i++, k = (k + 1) % N) cout << q[k] << " ";
        cout << "\n";
    }
};

int main() {
    CircularQueue cq;
    for (int i = 1; i <= 5; i++) cq.enqueue(i * 10);
    cq.print();
    cout << "enqueue 60 when full: " << (cq.enqueue(60) ? "ok" : "rejected") << "\n";
    cout << "dequeued " << cq.dequeue() << " and " << cq.dequeue() << "\n";
    cq.enqueue(60);
    cq.enqueue(70);                     // these reuse slots 0 and 1
    cq.print();
}

#include <iostream>
using namespace std;

const int N = 5;

class CircularQueue {
    int q[N];
    int front = 0, rear = -1, count = 0;
public:
    bool isFull() const { return count == N; }
    bool isEmpty() const { return count == 0; }
    bool enqueue(int x) {
        if (isFull()) return false;
        rear = (rear + 1) % N;          // wrap around
        q[rear] = x;
        count++;
        return true;
    }
    int dequeue() {
        if (isEmpty()) return -1;
        int x = q[front];
        front = (front + 1) % N;        // wrap around
        count--;
        return x;
    }
    void print() const {
        cout << "[front=" << front << " rear=" << rear << " count=" << count << "] ";
        for (int i = 0, k = front; i < count; i++, k = (k + 1) % N) cout << q[k] << " ";
        cout << "\n";
    }
};

int main() {
    CircularQueue cq;
    for (int i = 1; i <= 5; i++) cq.enqueue(i * 10);
    cq.print();
    cout << "enqueue 60 when full: " << (cq.enqueue(60) ? "ok" : "rejected") << "\n";
    cout << "dequeued " << cq.dequeue() << " and " << cq.dequeue() << "\n";
    cq.enqueue(60);
    cq.enqueue(70);                     // these reuse slots 0 and 1
    cq.print();
}

Expected output

[front=0 rear=4 count=5] 10 20 30 40 50 
enqueue 60 when full: rejected
dequeued 10 and 20
[front=2 rear=1 count=5] 30 40 50 60 70

05Complexity

enqueue	O(1)
dequeue	O(1)
front / isEmpty / isFull	O(1)
Extra space	O(N), and every slot is usable

The magic line is rear = (rear + 1) % N. When rear is N − 1, the next slot is 0.

06Watch

Array implementation of Queue

mycodeschool · 14:59

Why this one: Walks from the linear array queue to the circular version and derives the modulo formula.

Watched

Introduction to Queues

mycodeschool · 9:18

Why this one: Queue basics refresher.

Watched

Original class slides (Python, by the course's lecture authors):Stacks, Queues and Monotonicity

07Exam lens

Likely questions

What problem of the linear array queue does a circular queue solve?
Write enqueue and dequeue for a circular queue of size N.
N = 5, front = 3, rear = 1. How many items are in the queue? Which indices?
Give two ways to tell a full circular queue from an empty one.

Common mistakes

Writing rear++ instead of rear = (rear + 1) % N.
Testing front == rear for both empty and full. Without a count (or one spare slot) they look the same.
Printing from 0 to rear instead of starting at front and wrapping.

08Quick check

1.N = 6, rear = 5. After one enqueue, rear is…
2.N = 5, front = 3, count = 4. Which indices hold items, in queue order?
3.Why keep a count variable?
4.Which real system is a circular buffer?

09Practice

🟢 Trace by hand

N = 4. Start front 0, rear −1, count 0. Do: enq A, enq B, enq C, deq, deq, enq D, enq E, enq F, enq G. Write front, rear, count after each.

Show answer

enq A → f0 r0 c1 · enq B → f0 r1 c2 · enq C → f0 r2 c3
deq (A) → f1 r2 c2 · deq (B) → f2 r2 c1
enq D → f2 r3 c2 · enq E → f2 r0 c3 · enq F → f2 r1 c4 (full)
enq G → rejected, queue is full

🟡 Implement it

Rewrite the circular queue without a count variable, keeping one slot empty.

Hint

Start with front = rear = 0. Empty: front == rear. Full: (rear + 1) % N == front. Enqueue writes q[rear] then advances rear.

🔴 Solve problems

Design Circular Queue mediumleetcode.com
Hint
This page's class, plus Front() and Rear(). Rear item is at index rear.
Design Circular Deque mediumleetcode.com
Hint
Moving front backwards: front = (front - 1 + k) % k. Add k before taking % so it never goes negative.

10Mastery checklist

Tick these honestly. When every box is ticked, the topic is marked complete.

I can explain why the circular queue exists.
I can write enqueue and dequeue with modulo wrap-around.
I can tell full from empty.
I can trace front and rear as they wrap.

0/4 ticked

My notes

View as Markdown · Chapter cheat sheet