Implement Queue using Arrays
Implement Queue using Arrays: build a queue — enqueue, dequeue, front, size — on a fixed array.
- 1 <= capacity <= 10⁵
- Operations: enqueue, dequeue, front, size
- Wrap indices with modulo or the array strands space at the front
Intuition
To implement queue using arrays you need FIFO behaviour: elements leave in the order they arrived. The obvious layout — keep the front at index 0 and shift everything left on each dequeue — is correct but quietly terrible. Every dequeue moves every remaining element, so a queue of n items costs O(n) per removal.
The fix is to stop moving data and start moving pointers. Keep two indices, front and rear. Enqueue writes at rear and advances it; dequeue reads at front and advances that. Nothing in the array ever shifts, so both operations become O(1).
That alone creates a new problem: both pointers only ever move forward, so they eventually run off the end of a fixed array even when most of it is empty. The solution is to wrap them with modulo arithmetic, turning the array into a ring:
- The circle rotates under the indices while the data stays put.
One last subtlety comes with the ring. When front == rear, the queue could be completely empty or completely full — the indices alone cannot tell you which. Keeping an explicit count of stored elements resolves it, and doubles as the answer to a size() call.
A circular buffer. The insight is that front and rear should wrap with modulo instead of shifting elements — that's what keeps dequeue O(1). Tracking count rather than comparing the two indices is the detail that removes the classic full-versus-empty ambiguity, since both states otherwise look identical.
Approach
Before reading on: price up what the brute force costs here, then ask what unresolved thing you are holding, and what event finally resolves it. Aim for O(1) per op time and O(cap) space.
Move pointers, never elements
Store front, rear, and a fixed-capacity array. Dequeuing shifts front forward instead of sliding the contents left. This single decision is what turns an O(n) dequeue into an O(1) one, and it is the whole reason the circular design exists.
Wrap both indices with modulo
On enqueue set rear = (rear + 1) % capacity; on dequeue set front = (front + 1) % capacity. When a pointer passes the end it lands back at index 0, reusing the space that earlier dequeues freed.
Track the count to distinguish full from empty
With wrapping, front == rear is ambiguous — it holds both when nothing is stored and when everything is. Maintain count, incrementing on enqueue and decrementing on dequeue. Empty is count == 0, full is count == capacity.
Guard both boundaries
Enqueuing into a full queue is overflow and dequeuing from an empty one is underflow. Check count before touching the array in either operation and raise or return a sentinel — silently overwriting a live element is the bug this check exists to prevent.
Every operation is constant time
Enqueue, dequeue, front and size each do a fixed amount of work: one array access, one modulo, one counter update. O(1) time and O(capacity) space, with no operation ever depending on how many elements are stored.
Solution & live demo
Common pitfalls
Shifting the array on dequeue
v = self.a[0] self.a = self.a[1:] return v
v = self.a[self.front] self.front = (self.front + 1) % len(self.a)
Shifting is O(n) per dequeue and defeats the point of the structure. Moving the front index instead leaves the data where it is — nothing is copied.
Distinguishing full from empty by comparing indices
if self.front == self.rear: # empty?
if self.count == len(self.a): raise OverflowError
if self.count == 0: raise IndexError("empty")In a circular buffer front == rear is true both when it's completely empty and when it's completely full — the indices alone can't tell them apart. An explicit count resolves it without sacrificing a slot.
Computing the rear without wrapping
rear = self.front + self.count
rear = (self.front + self.count) % len(self.a)
Once front has advanced, the write position runs past the end of the array and raises an index error, even though there is free space at the start. The modulo is what makes the buffer circular.
Edge cases
After cap enqueues the rear index re-enters at 0 — modulo handles it silently.
Track count; front==rear alone can't tell the two apart.