Coding Interview PatternsDesign Circular Queue
MediumCustom Data Structures

Design Circular Queue

Explanation & Solution

Practice Problem

Description

Design a circular queue (ring buffer) — a linear data structure where the last element connects back to the first, forming a circle.

Implement a function that processes an array of operations and an array of arguments:

  • "MyCircularQueue" — Initializes the queue with a capacity of k.
  • "enQueue" — Inserts value into the circular queue. Returns true if successful, false if the queue is full.
  • "deQueue" — Deletes an element from the front. Returns true if successful, false if the queue is empty.
  • "Front" — Returns the front element, or -1 if empty.
  • "Rear" — Returns the last element, or -1 if empty.
  • "isEmpty" — Returns true if the queue is empty.
  • "isFull" — Returns true if the queue is full.
Input:operations = ["MyCircularQueue","enQueue","enQueue","enQueue","enQueue","Rear","isFull","deQueue","enQueue","Rear"], args = [[3],[1],[2],[3],[4],[],[],[],[4],[]]
0
MyCircularQueue
1
enQueue
2
enQueue
3
enQueue
4
enQueue
5
Rear
6
isFull
7
deQueue
8
enQueue
9
Rear
Output:[null,true,true,true,false,3,true,true,true,4]
0
null
1
true
2
true
3
true
4
false
5
3
6
true
7
true
8
true
9
4

Explanation: Queue capacity is 3. After enqueueing 1, 2, 3 the queue is full. enQueue(4) fails. Rear is 3. deQueue removes 1. enQueue(4) succeeds. Rear is now 4.

Constraints

  • 1 <= k <= 1000
  • 0 <= value <= 1000
  • At most 3000 calls will be made to the operations

Approach

Custom Data Structures pattern

1. Use a Fixed-Size Array with Head Pointer

  • Allocate an array of size k
  • Track the head index (front of queue) and current size
  • The tail index is derived as (head + size - 1) % capacity

2. Implement EnQueue

  • If full (size === capacity), return false
  • Insert at position (head + size) % capacity — this wraps around
  • Increment size

3. Implement DeQueue

  • If empty (size === 0), return false
  • Advance head by 1 with wrap-around: head = (head + 1) % capacity
  • Decrement size

4. Front and Rear

  • Front: return q[head]
  • Rear: return q[(head + size - 1) % capacity]
  • Both return -1 if the queue is empty

5. The Circular Wrap

  • The modulo operator % capacity makes the array behave like a ring
  • When head or the tail index reaches capacity, it wraps back to 0
  • This avoids shifting elements on dequeue — O(1) for all operations

Key Insight

  • A circular buffer reuses space without shifting — much more efficient than a naive array queue
  • Only two variables (head and size) are needed to track the full state
Time
O(1) for all operations
Space
O(k)

Solution Code

Previous
Design HashMap
Next
LRU Cache