GeeksforGeeks Easy

Implement Queue using Arrays

Build a queue — enqueue, dequeue, front, size — on a fixed array.

queuedesign

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.

How to spot this pattern

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.

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

▶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

Common pitfalls

Shifting the array on dequeue

✗ Wrong

v = self.a[0]
self.a = self.a[1:]
return v

✓ Right

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

✗ Wrong

if self.front == self.rear: # empty?

✓ Right

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

✗ Wrong

rear = self.front + self.count

✓ Right

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.

06

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.

07

Complexity

Time

O(1) per op

Space

O(cap)

Ring buffer — no shifting.