Queues, Deques & Circular Buffers — Data Structures Course

What you'll learn

A queue is the mirror image of a stack: add at the rear, remove from the front. That's FIFO — first in, first out, just like a line at a checkout. Its cousins — the circular buffer and the deque — power schedulers, streaming, and more.

By the end you'll be able to:

Use enqueue and dequeue and explain FIFO order
Understand how a circular buffer reuses space with modulo arithmetic
Describe a deque and when each variant is the right tool

FIFO: enqueue & dequeue

Items leave in the same order they arrived. Add to the rear with enqueue, remove from the front with dequeue — both O(1):

Queue operations

enqueue A, B, C · dequeue · dequeue

empty

1/6An empty queue. We add at the rear and remove from the front.

First in, first out — A arrived first, so A leaves first.

Watch out

Building a queue on a plain array is tempting but slow: dequeuing from the front would shift every element (O(n)). The fix is either a linked list or a circular buffer.

Circular buffers (ring buffers)

A circular buffer is a fixed-size array with two indices — front and rear — that wrap around using modulo (index = (index + 1) % capacity). Freed slots at the front get reused, so the queue never shifts and never needs to grow. Watch the indices wrap:

A circular buffer wrapping around

enqueue / dequeue with wrap-around

front▼

rear▼

1/5A circular buffer of capacity 5, holding 3 items. front = 0, rear = 3 (the next free slot).

front and rear chase each other around the ring; the live items are the slots between them.

Deques (double-ended queues)

A deque ("deck") lets you add and remove at both ends in O(1). It generalizes both the stack and the queue — use one end for LIFO, both ends for a sliding window, or treat it as a plain queue. It's usually built on a doubly linked list or a circular buffer.

In code

Language

queue.py

from collections import deque

q = deque()
q.append("A")        # enqueue at the rear
q.append("B")
front = q[0]         # peek front -> "A"
q.popleft()          # dequeue from the front -> "A"
print(front, list(q))

Complexity & uses

Structure	Add / remove	Used for
`Queue (FIFO)`	O(1) ends	Task scheduling, BFS (Module 24), print spooling
`Circular buffer`	O(1), fixed size	Streaming audio/video, keyboard buffers, logging
`Deque`	O(1) both ends	Sliding-window algorithms, work-stealing, undo+redo
`Priority queue`	O(log n)	Scheduling by priority — that's the heap, Module 20

Recap & quick check

Key takeaways

A queue is FIFO: enqueue at the rear, dequeue from the front — both O(1).
Don't back a queue with a plain array's front removal (O(n) shifting).
A circular buffer wraps front/rear with modulo, reusing freed slots in fixed space.
A deque allows O(1) insertion and removal at both ends.
Queues drive BFS, scheduling, and streaming; the priority queue is really a heap.

Quick check

1. What order does a queue release items in?

2. How does a circular buffer avoid shifting elements?

3. A deque lets you:

4. Which algorithm naturally uses a queue?

That completes the linear structures. Next we put them to work — starting with how to find things fast. Next up: Module 9 — Searching: Linear & Binary Search.