How do you implement a queue, and what data structure backs it?

beginner

← All Linked Lists, Stacks & Queues questions

Re-explain

A queue needs two access points, one end to add and another to remove. You back it with either a linked list holding head and tail pointers, or a ring buffer over a fixed array.

With a linked list, you enqueue at the tail and dequeue at the head, both O(1). The tail pointer is what keeps enqueue cheap. Without it, you would walk the whole list.

A ring buffer uses two indices that chase each other and wrap around the array. That gives O(1) operations with far better cache behavior and no per-node allocation. The catch is fixed capacity, so you either grow the array or reject when full.

Pick the ring buffer when throughput matters, like network packet handling, and the linked list when the queue must grow without bound.

Rewriting in plainer words…

This answer doesn't lend itself to a diagram - it reads best . No credits were charged.

Why there's no diagram: “”

The interactive diagram is below the answer - jump to diagram ↓ · Below it, the related concept . Jump to it ↓

The diagram below the answer is the concept . Jump to it ↓

Tailored explanation · switch back to · ·

What should the new diagram focus on?

Guided practice for Linked Lists, Stacks & Queues One question at a time. Answer out loud, get graded, see what you missed.

How well did you know this?

AI:

Saved in this browser - sign in to keep your review list.

How should your speech become text?

Listening… your words appear above as you speak - tap Stop when you're done.

Recording · cr - tap Stop & transcribe when you're done.

Transcribing with AI…

Voice:

Keep going - a few more words and AI can grade it.

Interview lens How interviewers actually use this question

Likely follow-ups

In a ring buffer, head equals tail both when empty and when full. How do you tell them apart? Keep a count, leave one slot always empty, or let the indices grow unbounded and mask them. Name what each one costs.
When the ring buffer is full and you choose to grow it, how do you keep FIFO order intact? Allocate a bigger array and copy from head to tail in queue order, unwrapping it. Doubling keeps enqueue O(1) amortized.
In your linked-list queue, what has to happen when you dequeue the last element? Head goes null and tail must be cleared too, or it keeps pointing at the removed node. Enqueue on an empty queue sets both.
Could you build a queue from two stacks instead? What does each operation cost? Push to an inbox stack, pop from an outbox, refilling it only when empty. Each element moves once, so O(1) amortized, O(n) worst case.
How would you make this queue safe for several producers and consumers? Start with one lock and condition variables for not-empty and not-full, then say where contention hurts before mentioning lock-free.

What you can say

A queue needs two ends, one to add at and one to remove from, and I'd back it with either a linked list or a ring buffer over an array.
With a linked list I keep head and tail pointers, enqueue at the tail and dequeue at the head, and both are O(1).
The tail pointer matters most, because without it every enqueue would walk the whole list.
A ring buffer uses two indices that chase each other around a fixed array and wrap at the end, so operations are still O(1).
It has much better cache behavior and no per-node allocation, but capacity is fixed, so when it fills you either grow the array or reject.
So I'd pick the ring buffer when throughput matters, like network packet handling, and the linked list when the queue has to grow without bound.

Weak answers to avoid

Dequeues by shifting a plain array Shifting every element on each dequeue makes it O(n). Say you use a ring buffer, where head and tail indices wrap instead of data moving.
Linked list with only a head pointer Enqueue then walks the whole list, which is O(n). Keep a tail pointer so adding at the tail is O(1).
Enqueues at the head, dequeues at the tail In a singly linked list, removing the tail needs its predecessor, so dequeue becomes O(n). Add at the tail and remove at the head.
Names one structure and stops The question asks what backs it, and there are two good answers. Compare them on cache behavior, allocation and fixed capacity, then say when you'd pick each.

Interview lens

Likely follow-ups, what you can say, and the weak answers to avoid.

Want a quick review of the fundamentals? See the Linked Lists, Stacks & Queues cheatsheet.

← Back to all Linked Lists, Stacks & Queues questions

Pro · $10/mo

67 of 78 Linked Lists, Stacks & Queues answers are in Pro.

Full answers, code samples, and AI explanations that go simpler or deeper. Cancel anytime.

Full answers + code
AI explanations, simpler or deeper
1,000 AI credits / month
Cancel anytime

Get Pro → See plans & pricing →