Circular Queue Using Array
Filed under Amazon
Free read 1 of 3Maintain 'head' and 'tail' indices and a 'size' counter to track elements.
The question
Implement a circular queue using a fixed-size array. The queue should support Enqueue (add element) and Dequeue (remove element) operations efficiently.
Constraints
- Fixed array size N.
- Enqueue should fail if queue is full.
- Dequeue should fail if queue is empty.
- Operations must be O(1).
Examples
- Input
- size=3, enqueue(1), enqueue(2), dequeue()
- Output
- 1
- Why
- Queue state: [1] -> [1, 2] -> [2]
Approach
Maintain 'head' and 'tail' indices and a 'size' counter to track elements.
Use (index + 1) % capacity to wrap pointers around the array boundaries.
Check if full, insert at tail, update tail, increment size.
Check if empty, return value at head, update head, decrement size.
Solution
O(1) time, O(N) space
class CircularQueue:
def __init__(self, k):
self.q = [None]*k; self.k = k; self.h = self.t = self.s = 0
def enqueue(self, v):
if self.s == self.k: return False
self.q[self.t] = v; self.t = (self.t + 1) % self.k; self.s += 1; return True
def dequeue(self):
if self.s == 0: return None
v = self.q[self.h]; self.h = (self.h + 1) % self.k; self.s -= 1; return v
Tips
- What they are testing: Focus on the wrap-around logic using modulo operator and handling the full vs empty state distinction.
- Common mistake: Failing to correctly distinguish between a full queue and an empty queue when head and tail pointers meet.
Related Amazon questions
Collected from public candidate posts and coding forums. Updated Nov 2026.