Queue Using an Array

Bounded Ring Buffer

Build a first-in, first-out queue on top of a fixed-size array so that enqueue, dequeue and peek all run in constant time and no slot is ever wasted.

Overview

A queue takes items at the back and gives them out at the front, in the order they arrived. The question asks you to build one on a plain array of fixed size. It sounds like a warm-up, and it is, but the interviewer is watching for one insight: a queue on a straight array leaks slots, and the fix is to treat the array as a ring.

The design also shows whether you can hide the mechanism behind a small, clean interface. Callers should see enqueue, dequeue, peek, is_empty, is_full and len, and nothing about indexes. A strong answer states the ring idea in the first minute, writes the modulo formula once, and tests the wrap-around case out loud.

Why a straight array leaks

Suppose the front index moves forward on every dequeue and the rear index moves forward on every enqueue. Slots behind the front are dead: nothing will ever be written there again.

1 — enqueue a, b, c — a b c . — 0 — 3 — 1
2 — dequeue twice — . . c . — 2 — 3 — 1
3 — enqueue d — . . c d — 2 — 4 — 0
4 — enqueue e — no room — 2 — 4 — 0, with two empty slots

After step 4 the queue holds two items in an array of four and still reports full. Shifting everything to the front on each dequeue would fix that at O(n) per call, which defeats the point of a queue.

The ring

Treat index capacity - 1 as the neighbor of index 0. Every index move becomes (i + 1) % capacity. The front chases the rear around the ring, and a slot is reused the moment the front has passed it.

The same operations as before, now on the ring. In step 3, d fills slot 3 and then e lands in slot 0 because rear wrapped.

1 — enqueue a, b, c — a b c . — 0 — 3 — 3 — a b c
2 — dequeue twice — . . c . — 2 — 1 — 3 — c
3 — enqueue d, e — e . c d — 2 — 3 — 1 — c d e
4 — enqueue f — e f c d — 2 — 4 — 2 — c d e f
5 — dequeue — e f . d — 3 — 3 — 2 — d e f

The physical order in the array (e f c d) is not the logical order (c d e f). Any method that shows the contents has to walk from front for size steps, wrapping as it goes.

Telling full from empty

If you keep only front and rear, an empty ring and a full ring look the same: both have front == rear. Three ways to break the tie are common; the code below uses the first.

Keep a count — size says how many items there are; rear is derived as (front + size) % capacity — One integer; the simplest code
Leave one slot empty — Full means (rear + 1) % capacity == front; one slot is never used — Capacity is one less than the array
Keep a flag — A boolean set when the last enqueue filled the ring — One boolean; easy to forget on dequeue

The same idea in the standard libraries

You should be able to write the ring by hand and also know what to reach for in real code. The library versions differ in what they do when the queue is full, so name the difference.

Python collections.deque(maxlen=n) — Not one fixed array; O(1) appends and pops at both ends — Adding at one end silently drops an item from the other end
Python queue.Queue(maxsize=n) — Thread-safe queue with locks — put blocks until there is room; put_nowait raises Full
Java ArrayBlockingQueue — A fixed array; capacity cannot change after construction — put blocks; offer returns false

What you will be able to do

Show with a five-row trace why a straight array leaks and how the ring fixes it.
Write enqueue and dequeue with one modulo formula and no shifting.
Explain the full-versus-empty problem and pick a way to solve it.
Grow the queue when it fills, and keep the order right while copying.
Say how the library queues behave when full, and which one to use.

Functional requirements

enqueue(item) adds at the back; on a full queue it raises, and try_enqueue returns False instead
dequeue() removes and returns the front item; on an empty queue it raises, and try_dequeue returns None instead
peek() returns the front item without removing it
is_empty(), is_full() and len() report the state without touching the items
Iterating the queue yields items from front to back, in logical order, whatever the physical layout

Non-functional requirements

Every operation is O(1); nothing is ever shifted
Memory is one array of the given capacity, allocated once
A slot is reused as soon as the item in it has been dequeued, so any number of cycles fits
Indexes and the array are private; callers never see them

Interview questions

Why not shift the items forward on every dequeue and keep a plain array?
The queue is full. How would you let it grow?
Should dequeue on an empty queue raise, or return None?
Several threads share the queue. What changes?
What bugs show up in this problem, and how do you test for them?