Implement Queue using Arrays
Build a queue — enqueue, dequeue, front, size — on a fixed array.
02
Intuition
Two pointers, front and rear, both only move forward — so wrap them around with modulo and the array becomes a ring. No element ever shifts; the circle just rotates under the indices.
03
Approach
1
Naive front-removal is O(n)
Dequeuing from a[0] and shifting everything left wastes the whole array walk. The fix: move the pointer, not the data.
2
Circular indexing
rear = (rear + 1) % cap on enqueue, front = (front + 1) % cap on dequeue. A separate count distinguishes full from empty (both have front == rear otherwise).
3
All O(1)
Every operation is one read/write plus modular arithmetic.
04
Solution & live demo
python
▶1class Queue:
▶2 def __init__(self, cap):
▶3 self.a = [0] * cap
▶4 self.front = 0
▶5 self.count = 0
▶6
▶7 def enqueue(self, x):
▶8 if self.count == len(self.a): raise OverflowError
▶9 rear = (self.front + self.count) % len(self.a)
▶10 self.a[rear] = x
▶11 self.count += 1
▶12
▶13 def dequeue(self):
▶14 if self.count == 0: raise IndexError("empty")
▶15 v = self.a[self.front]
▶16 self.front = (self.front + 1) % len(self.a)
▶17 self.count -= 1
▶18 return v
05
Edge cases
Wrap-around
After cap enqueues the rear index re-enters at 0 — modulo handles it silently.
full vs empty ambiguity
Track count; front==rear alone can't tell the two apart.
06
Complexity
Time
O(1) per op
Space
O(cap)
Ring buffer — no shifting.