Queues

First in, first out. Enqueue at the back and dequeue at the front — the shape of fairness, buffers, and breadth-first search.

Level: beginner

What is it?

A queue removes elements in the order they were added (FIFO). Enqueue adds to the back and dequeue removes from the front. A naive array makes dequeue O(n), so real queues use a linked list, a circular buffer, or two indices, giving O(1) at both ends. A deque allows adding and removing at either end.

Why does it matter?

Queues model waiting: requests, print jobs, packets, and tasks. They are the buffer between a producer and a consumer that run at different speeds, and they drive breadth-first search and first-come-first-served scheduling.

Mental model

The line at a coffee shop. People join at the back and are served from the front, in order. Nobody is served twice, and nobody jumps ahead.

How it works

Operations: enqueue, dequeue, peek, is_empty — each O(1) in a proper implementation.
A circular buffer reuses a fixed array by wrapping the head and tail indices.
A bounded queue applies back-pressure: when full, producers block or drop.
A priority queue dequeues by priority, not arrival; it is usually a heap.
OS schedulers use queues (FCFS, round robin), and network routers buffer packets in queues.

Steps

Enqueue at the back
Wait behind earlier items
Dequeue from the front
Process in arrival order
Empty means nothing to serve

Code example: A deque is a real queue

from collections import deque

q = deque()
q.append("job-1")        # enqueue at the back: O(1)
q.append("job-2")
print(q.popleft())       # dequeue from the front: O(1) -> job-1
# list.pop(0) would be O(n): never use a plain list as a queue

Complexity and trade-offs

Time: Enqueue, dequeue, peek O(1) with a deque or circular buffer

Space: O(n)

Trade-offs

Preserves arrival order and decouples producers from consumers
An unbounded queue hides overload until memory runs out

Real-world usage

Task and message queues
Breadth-first search
Buffers in networking, I/O, and streaming pipelines

Common mistakes

Using a list and pop(0), so each dequeue costs O(n).
An unbounded queue with a slow consumer, ending in an out-of-memory failure.
Confusing a queue with a priority queue when order should depend on urgency.

Interview questions

How do you implement a queue with two stacks?

Push onto an input stack. When you need to dequeue and the output stack is empty, pop everything from input onto output, which reverses the order. Each element moves at most twice, so operations are O(1) amortized.

Why use a circular buffer?

It gives a fixed-size queue in one array with O(1) enqueue and dequeue and no shifting, by wrapping the head and tail indices with modulo arithmetic.

Queue versus stack?

A queue is first in, first out; a stack is last in, first out. Use a queue when order of arrival matters (BFS, scheduling) and a stack when you must unwind in reverse (undo, DFS, recursion).