Queues and Deques

First-in, first-out — and the double-ended tool that makes it, and a lot more, O(1)

FIFOthe oldest item is always served first
Both ends O(1)deque — append/appendleft, pop/popleft
BFS uses a queuea stack there would give DFS instead
Sliding window maxa monotonic deque, O(n) total, not O(nk)

1.FIFO principle

A queue is First-In-First-Out: the item that has been waiting longest is always the first one served — the exact opposite of a stack's LIFO order.

Key features

enqueue adds to the back; dequeue removes from the front — the two ends are never the same one
Contrast with a stack (LIFO): a queue always serves the OLDEST item first, a stack always serves the NEWEST
collections.deque is the practical Python queue — append() to enqueue, popleft() to dequeue, both O(1)

Command

fifo.pypython

from collections import deque

queue = deque()
queue.append('a')
queue.append('b')
queue.append('c')

print(queue.popleft())   # 'a' — the earliest-enqueued item, out first
print(queue)               # deque(['b', 'c']) — 'c' arrived last and waits behind 'b'

FIFO means the first thing enqueued is the first thing dequeued — picture a line of people, not a stack of plates.

2.Why list.pop(0) is O(n) — never use a plain list as a queue

list.pop(0) and list.insert(0, x) both shift every remaining element over by one — O(n) per operation — so a plain list makes a correct but slow queue.

Key features

The mechanism is the same front-vs-end asymmetry a stack relies on, in reverse — a Python list is only ever fast at the END, never the front
A queue needs the FRONT to be fast (dequeue) — exactly the end a list is slow at, which is why list makes a great stack but a poor queue
collections.deque exists specifically to fix this: O(1) at BOTH ends, not just one

Command

list_as_queue.pypython

queue = []
queue.append('a')
queue.append('b')
queue.append('c')

queue.pop(0)   # O(n) — 'b' and 'c' both shift left by one to fill the gap

A plain list can play queue, but every dequeue costs O(n) — reach for collections.deque the moment front-of-structure removal matters.

3.collections.deque — O(1) append/pop from both ends

deque is a double-ended queue: append/appendleft add to either end, and pop/popleft remove from either end, all in O(1) — unlike a list, which is only fast at one end.

Key features

append(x)/pop() work the right end; appendleft(x)/popleft() work the left end — all four are O(1)
Random access (dq[i]) and searching the middle are still O(n), same as a linked list — a deque trades that away for fast BOTH ends, it does not get everything for free
deque(iterable, maxlen=n) auto-evicts from the opposite end once full — the built-in tool for a fixed-size circular buffer

append/pop work the right end, appendleft/popleft work the left end, all O(1) — using pop() where a queue needs popleft() silently turns FIFO into LIFO.

4.Queue via deque for BFS

Breadth-first search visits everything at the current distance before anything farther away — a plain FIFO queue is exactly what enforces that order: nodes discovered earlier get processed before nodes discovered later.

Key features

Mark a node visited the MOMENT it is enqueued, not when it is dequeued — otherwise the same node can be queued twice before it is ever processed
Swapping the queue for a stack turns the exact same traversal into depth-first order instead — the container, not the loop shape, is what decides BFS vs DFS
This is the same append/popleft shape as any other queue use — BFS just happens to be enqueuing node names, with a `visited` set alongside it

A queue is what makes a traversal breadth-first — enqueue neighbors as you discover them, mark them visited immediately, and popleft() always serves the earliest-discovered one first.

5.Circular queue concept

A circular queue reuses a fixed-size block of memory by wrapping its front and rear indices with modulo arithmetic, instead of ever shifting elements or growing without bound.

Key features

front and rear indices wrap via modulo instead of shifting existing elements — enqueue and dequeue are both O(1) regardless of where in the fixed array they physically land
Capacity is fixed up front — a full circular queue must raise, block, or overwrite by explicit design choice, unlike a Python list or deque, which just keeps growing
collections.deque(maxlen=n) gives the same fixed-capacity, auto-evicting behavior from the standard library — hand-rolling the array-and-modulo version is mostly for understanding the mechanism

A circular queue reuses a fixed block of memory by wrapping indices with modulo, instead of shifting elements or growing without bound — the same result deque(maxlen=n) gives for free.

6.Monotonic deque pattern (sliding window maximum)

Keep a deque of indices whose values are decreasing, front to back. The front is always the current window's maximum — before reading it, evict any front index that has slid outside the window; before pushing a new index, evict any back index whose value it beats.

Key features

The front eviction (`dq[0] <= i - k`) and the back eviction (`nums[dq[-1]] < n`) are two independent checks — dropping either one breaks the algorithm in a different way
The front of the deque is always the current window's maximum, read in O(1) — no rescanning the window on every step
Each index is pushed once and popped at most once from either end, so the whole scan is O(n) total — the same amortized argument as the monotonic stack

A monotonic deque needs BOTH evictions — back for "beaten by a newer value", front for "aged out of the window" — dropping either one produces a stale answer, not a crash.

7.Priority queue as a distinct structure from a plain queue

A priority queue always serves the item with the highest (or lowest) priority next, regardless of insertion order. A plain queue always serves the oldest item, regardless of any priority. They solve different problems, even though both have 'queue' in the name.

Key features

FIFO order and priority order agree only by coincidence — a low-priority item enqueued first still waits behind a high-priority item enqueued later, in a priority queue
A binary heap (see the Heaps and Priority Queues section) is the standard way to implement one, giving O(log n) insert and O(log n) pop-highest-priority instead of a plain queue's O(1)
Python's heapq module is the lower-level, more commonly used tool for this in interview code — queue.PriorityQueue wraps it with thread-safety most solutions do not need

Command

priority_vs_fifo.pypython

tasks = [(3, 'write report'), (1, 'fix outage'), (2, 'reply to email')]

# a priority queue serves the LOWEST number first, not the first inserted —
# 'fix outage' (priority 1) jumps ahead of 'write report', enqueued first
next_task = min(tasks)
print(next_task)

A plain queue answers "what came first?"; a priority queue answers "what matters most?" — different contracts, and a priority queue usually costs O(log n) instead of O(1) to get that ordering.

Spotted a mistake on this page? Tell us.

Read Sheet