AlgoMaster Logo

Design Circular Queue

mediumFrequencyUpdated September 21, 2026

Understanding the Problem

We need to build a circular queue from scratch using an array (no built-in queue allowed). A regular array-based queue wastes space over time: after enough enqueue/dequeue operations, the front pointer moves forward and the slots at the beginning of the array sit abandoned. Even if the array has empty slots at the front, we can't use them because the tail has reached the end.

A circular queue solves this by wrapping around. When the tail reaches the end of the array, it loops back to the beginning (using modulo arithmetic). This way, every slot in the array can be reused as long as the queue isn't full.

The design comes down to tracking three things: where the front of the queue is, where the rear of the queue is, and how many elements are currently stored. With those three pieces of information, all six operations are O(1) lookups or updates.

Key Constraints:

  • 1 <= k <= 1000 -> The capacity is small, so a fixed array of size k works. No dynamic resizing is needed.
  • 0 <= value <= 1000 -> Stored values are non-negative, so the -1 that Front and Rear return for an empty queue can never collide with a real element.
  • At most 3000 calls total -> Performance is not the difficulty here; every operation runs in O(1). The challenge is getting the wraparound and the empty/full distinction right.

Approach 1: Array with Separate Count Variable

Intuition

Store the elements in a fixed-size array and track two pointers: front (the index we dequeue from) and rear (the next index to write). Modulo arithmetic handles the wrapping: advancing a pointer with (pointer + 1) % capacity sends it back to index 0 after it passes the last slot.

One ambiguity remains. Start with an empty queue, where front == rear == 0, then enqueue k elements: rear advances k times and wraps all the way back around to front. Both the empty state and the full state leave front == rear, so pointer positions alone cannot distinguish them. A separate count variable resolves this: empty means count == 0, full means count == capacity.

Algorithm

  1. Initialize a fixed-size array of length k, a front pointer at 0, a rear pointer at 0, a count at 0, and store the capacity as k.
  2. enQueue(value): If the queue is full, return false. Otherwise, place value at data[rear], advance rear = (rear + 1) % capacity, increment count, and return true.
  3. deQueue(): If the queue is empty, return false. Otherwise, advance front = (front + 1) % capacity, decrement count, and return true.
  4. Front(): If empty, return -1. Otherwise, return data[front].
  5. Rear(): If empty, return -1. Otherwise, return data[(rear - 1 + capacity) % capacity]. The + capacity before the modulo handles the case where rear is 0.
  6. isEmpty(): Return count == 0.
  7. isFull(): Return count == capacity.

Example Walkthrough

1Initial: data=[_, _, _], front=0, rear=0, count=0 (EMPTY)
0
front
_
rear
1
_
2
_
1/9

Code

Approach 1 carries count as auxiliary state that every mutation has to keep in sync with the pointers. The next approach removes it and derives emptiness and fullness from the pointer positions alone.

Approach 2: Array with Extra Slot (No Count Variable)

Intuition

Allocate an array of size k + 1 instead of k, but never store more than k elements. The deliberately unused slot removes the ambiguity from Approach 1: empty means front == rear, and full means (rear + 1) % (k + 1) == front. A full queue always leaves exactly one gap between rear and front, so the full condition can never look like the empty condition. The cost is one wasted array slot in exchange for dropping the count field.

Ring buffer implementations in operating system kernels and network drivers often use this "waste one slot" design because it eliminates the count variable, and with it the need to update that count atomically in lock-free concurrent code.

Algorithm

  1. Initialize an array of length k + 1, front at 0, rear at 0. The usable capacity is k.
  2. enQueue(value): If (rear + 1) % (k + 1) == front, the queue is full, return false. Otherwise, place value at data[rear], advance rear = (rear + 1) % (k + 1), return true.
  3. deQueue(): If front == rear, the queue is empty, return false. Otherwise, advance front = (front + 1) % (k + 1), return true.
  4. Front(): If empty, return -1. Return data[front].
  5. Rear(): If empty, return -1. Return data[(rear - 1 + k + 1) % (k + 1)].
  6. isEmpty(): Return front == rear.
  7. isFull(): Return (rear + 1) % (k + 1) == front.

Example Walkthrough

1Initial: data=[_, _, _, _], front=0, rear=0 (EMPTY: front==rear)
0
front
_
rear
1
_
2
_
3
_
1/9

Code