# 5.5 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.

Chapter: Stacks & Queues · ~40 min · medium
URL: https://dsa.fetehadin.com/learn/circular-queue

## Mental 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**:

```cpp
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:

1. **Keep a `count`** (this page): empty when `count == 0`, full when `count == N`.
2. **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]`.

## C++ code: circular-queue.cpp

```cpp
#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:

```text
[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
```

## Complexity

| Case | Cost |
| --- | --- |
| enqueue | O(1) |
| dequeue | O(1) |
| front / isEmpty / isFull | O(1) |

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.

## Videos

- [Array implementation of Queue](https://youtu.be/okr-XE8yTO8) (mycodeschool): Walks from the linear array queue to the circular version and derives the modulo formula.
- [Introduction to Queues](https://youtu.be/XuCbpw6Bj1U) (mycodeschool): Queue basics refresher.

## Exam 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.

## Quick check

1. N = 6, rear = 5. After one enqueue, rear is…
   A. 6
   B. 0
   C. 5
   D. -1
   Answer: B. (5 + 1) % 6 = 0. The rear wraps to the start.

2. N = 5, front = 3, count = 4. Which indices hold items, in queue order?
   A. 3, 4, 5, 6
   B. 3, 4, 0, 1
   C. 0, 1, 2, 3
   D. 1, 2, 3, 4
   Answer: B. Start at 3 and wrap. 3, 4, then 0, 1.

3. Why keep a `count` variable?
   A. To make enqueue faster
   B. To tell full from empty, since front and rear alone can look identical
   C. It is required by C++
   D. To sort the queue
   Answer: B. Another option is to leave one slot always empty, so full means `(rear + 1) % N == front`.

4. Which real system is a circular buffer?
   A. A keyboard input buffer
   B. An undo history
   C. A binary search tree
   D. A hash map
   Answer: A. Keystrokes are written into a fixed ring and read in the same order.

## Practice

**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.

Solution:

- 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.

**Problems:**

- [Design Circular Queue](https://leetcode.com/problems/design-circular-queue/) (medium). Hint: This page's class, plus Front() and Rear(). Rear item is at index `rear`.
- [Design Circular Deque](https://leetcode.com/problems/design-circular-deque/) (medium). Hint: Moving front backwards: `front = (front - 1 + k) % k`. Add k before taking % so it never goes negative.

## Mastery checklist

- [ ] 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.