Stack/QueueData structureaka ring buffer, circular buffer, cyclic queue

Circular Queue

A fixed-capacity queue over an array whose head and tail indices wrap around using modular arithmetic.

▶ Visualize Pattern: Breadth-First Search

Progress

Definition

A circular queue stores elements in a fixed-size array and tracks head (index of the front) and a count (or tail). When an index reaches the end of the array it wraps to 0 via (i + 1) % capacity, so the slots freed by dequeues at the front are reused by enqueues at the back.

This removes the two flaws of a plain array queue: no O(n) shifting on dequeue and no unbounded growth of a "dead" prefix. It is the standard implementation of bounded buffers in operating systems, audio pipelines, and network drivers.

FIFOfixed capacityring bufferO(1)modular arithmetic

Intuition

A mental model before the formal terms.

Imagine seats around a round table numbered 0..k−1. Guests sit at the next free seat clockwise and leave from the oldest occupied seat. After seat k−1 comes seat 0 again — the table never "runs out of edge" the way a straight bench does.

A clock face: after 11 comes 0, not 12. Indices behave the same way under % capacity.

How it works

Allocate buf of size k; set head = 0, size = 0. The back index is derived: tail = (head + size) % k.
enqueue(x): if size == k the queue is full — reject. Else buf[(head + size) % k] = x, size++.
dequeue(): if size == 0 — reject. Else read buf[head], head = (head + 1) % k, size--.
front() is buf[head]; rear() is buf[(head + size - 1) % k].
Tracking size explicitly avoids the classic ambiguity where head == tail could mean either empty or full.

Why it works

Elements are always stored in size consecutive slots (mod k) starting at head, so FIFO order is preserved: the oldest element is at head, the newest at head + size - 1.

Modular arithmetic makes every index computation O(1) and guarantees indices stay in [0, k).

Operations

Operation	Description	Cost
enqueue(x)	Insert at the back if not full.	O(1)
dequeue()	Remove from the front if not empty.	O(1)
front()	Peek the oldest element.	O(1)
rear()	Peek the newest element.	O(1)
isFull() / isEmpty()	Capacity checks.	O(1)

Recognition

How to tell a problem wants this.

A bounded buffer with a known maximum size is required (embedded systems, producer/consumer).
The problem literally says "design a circular queue" or "ring buffer".
You want a queue with array cache locality and no allocation per operation.
A sliding window of the last k events where old ones are overwritten.

“minimum steps” → Breadth-First Search

Interactive demo

Play, step, change the input. ← → and space work too.

Showing the closely related Queue visualization.

Commands — Comma separated: enqueue N, dequeue, peek

1/12A queue is first-in, first-out: elements enter at the back and leave from the front, so the order of arrival is preserved.

Just enqueuedFrontBeing dequeued

PseudocodeLearn Queue →

1enqueue(x): items.append(x)      # at the back
2dequeue(): return items.pop_front()  # from the front
3peek(): return items[front]

Variables

size0

Complexity

access O(n)

search O(n)

insert O(1)

delete O(1)

Speed

Pseudocode

1class CircularQueue(k):
2  buf = array of size k; head = 0; size = 0
3  enqueue(x): if size == k: return false; buf[(head + size) % k] = x; size++; return true
4  dequeue(): if size == 0: return false; head = (head + 1) % k; size--; return true
5  front(): return buf[head]
6  rear(): return buf[(head + size - 1) % k]

Implementation

1from typing import Generic, Optional, TypeVar
2 
3T = TypeVar("T")
4 
5 
6class CircularQueue(Generic[T]):
71 · Fixed buffer, head index, and count
8    def __init__(self, k: int) -> None:
9        self._buf: list[Optional[T]] = [None] * k
10        self._cap = k
11        self._head = 0  # index of the front
12        self._n = 0     # number of stored elements
13        # back slot is derived: (head + n) % cap
14 
152 · Enqueue into the derived back slot
16    def enqueue(self, x: T) -> bool:
17        if self.is_full():
18            return False
19        self._buf[(self._head + self._n) % self._cap] = x
20        self._n += 1
21        return True
22 
233 · Dequeue by advancing head modulo capacity
24    def dequeue(self) -> bool:
25        if self.is_empty():
26            return False
27        self._buf[self._head] = None  # release the reference
28        self._head = (self._head + 1) % self._cap
29        self._n -= 1
30        return True
31 
324 · Peek front and rear
33    def front(self) -> Optional[T]:
34        return None if self.is_empty() else self._buf[self._head]
35 
36    def rear(self) -> Optional[T]:
37        if self.is_empty():
38            return None
39        return self._buf[(self._head + self._n - 1) % self._cap]
40 
415 · Emptiness and fullness from the count
42    def is_empty(self) -> bool:
43        return self._n == 0
44 
45    def is_full(self) -> bool:
46        return self._n == self._cap

Walkthrough

The buffer is [None] * k; Optional[T] in the type says empty slots are None.
enqueue writes to (head + n) % cap and increments the count; a full buffer returns False.
dequeue clears the slot (dropping the reference), advances head with %, and decrements the count.
front/rear return None when empty — mirrored from the buffer's own empty-slot convention.
is_empty/is_full read only the count.

Complexity (this implementation)

time O(1) all operations · space O(k)

Python % always returns a non-negative result for a positive modulus, so even head - 1 style arithmetic would be safe here — unlike C++/JS.

Language notes

Python's % is floored: -1 % 5 == 4. The wraparound bug class that plagues C++/JS/Java rings simply does not exist here.
collections.deque(maxlen=k) is a bounded ring with *overwrite* semantics: appending to a full deque silently evicts the oldest — different from the reject semantics implemented here.
For numeric rings, array.array or NumPy arrays avoid per-element object overhead.

Common mistakes in this language

Reaching for deque(maxlen=k) when the task requires rejecting on full — it evicts instead.
Storing None as a payload value and then misreading front() is None as "empty".
Recomputing tail in several places instead of deriving it once from head + n.

Language differences that matter here

Modulo of negatives: Python % is always non-negative; C++/JS keep the dividend's sign — decrementing indices needs + cap before % there.
Empty-peek reporting: C++ uses std::optional, TS types it as T | undefined, Python returns None, JS returns undefined — all four make emptiness a value, not an exception.
Built-ins: Python deque(maxlen=k) gives a bounded ring with overwrite-oldest semantics; C++/JS/TS have no bounded-queue primitive in the standard library.
The C++ vector default-constructs all k elements at once; JS/TS/Python allocate k references and fill lazily.

Complexity

Operation	Average	Worst	Note
Access	O(1)	O(1)	Front/rear; arbitrary index via (head+i)%k.
Search	O(n)	O(n)
Insert	O(1)	O(1)	Fails when full.
Delete	O(1)	O(1)	Front only.
Update	—	—
Enqueue	O(1)	O(1)
Dequeue	O(1)	O(1)
Front / Rear	O(1)	O(1)
Space	O(k)		k is the fixed capacity, allocated up front.

Advantages & disadvantages

Advantages

All operations O(1) with zero allocations after construction.
Contiguous memory, cache-friendly, predictable footprint — ideal for real-time and embedded code.
Naturally provides back-pressure (full buffer) or overwrite semantics (oldest evicted).

Disadvantages

Fixed capacity: must be sized up front or resized with an O(n) copy that un-wraps the elements.
Index bookkeeping is error-prone (empty vs. full ambiguity, off-by-one in wraparound).
No random access or search better than O(n).

Use cases

Keyboard, serial, and audio I/O buffers in operating systems and drivers.
Bounded producer/consumer channels between threads.
Keeping the most recent k samples for moving averages or log rings.
CPU round-robin scheduling queues.

Use it when

The maximum number of buffered items is known and bounded.
You need a queue without per-operation allocation (real-time, embedded, lock-free rings).
You want to keep only the most recent k items and overwrite the oldest.

Avoid it when

Capacity is unknown or highly variable — use a linked Queue or a growable Deque.
You need insertion/removal at both ends — use a Deque (which is itself often a growable ring buffer).

Alternatives

Queue Deque Dynamic Array

Common mistakes

Using head == tail to mean both "empty" and "full" — track size or leave one slot unused.
Writing tail = tail + 1 without % capacity, running off the end of the array.
Computing rear as tail - 1 without adding capacity before the modulo, producing a negative index in languages where % can be negative (Java, C++, Go, JS).
Resizing by copying buf verbatim instead of un-wrapping from head, which scrambles element order.

Interview patterns

Design Circular Queue (LeetCode 622) — implement with head + size.
Moving average from a data stream: ring of the last k values plus a running sum.
Design Hit Counter: ring of timestamps indexed by t % 300.

Interview questions on this

Choosing between BFS, DFS, Dijkstra and DPAdvanced
Stack versus queueBeginner
Choosing a shortest-path algorithmAdvanced
Union-Find or DFS for connectivity?Advanced

Mock interviews

Course ScheduleIntermediate
Network Delay TimeAdvanced
Number of IslandsIntermediate

Interview problems

No linked problems yet.

Definition

Intuition

How it works

Why it works

Operations

Recognition

Interactive demo

Pseudocode

Implementation

Complexity

Advantages & disadvantages

Use cases

Alternatives

Common mistakes

Interview patterns

Interview problems

Related