Queues and Deques

The mental model: a checkout line with memory

Think of a queue as a tube. Elements go in the right end, come out the left end. The tube has no concept of "skip ahead" or "reach in from the side." It respects arrival time above everything.

This makes a queue the natural opposite of a stack. A stack is LIFO — your most recent call goes on top and comes off first, like a stack of plates. A queue is FIFO — whoever showed up first leaves first. Same basic idea of a restricted interface; opposite semantics; completely different use cases.

flowchart LR
    IN["enqueue →"] --> B["back"]
    subgraph Queue
      direction LR
      B["3 (back)"] --- M["7"] --- F["1 (front)"]
    end
    F --> OUT["→ dequeue"]
    style B fill:#7c5cff,color:#0a0a0f
    style F fill:#22d3ee,color:#0a0a0f

The terms vary by language. Python calls them append / popleft. Java says offer / poll. C++ says push / pop on std::queue. The operation names differ but the contract doesn't: back goes in, front comes out.

Why your first implementation is probably wrong

Here is the obvious thing to try when you need a queue in Python:

queue = []
queue.append(7)      # enqueue — O(1), fine
queue.append(3)
queue.pop(0)         # dequeue from the front — looks right, costs O(n)

list.pop(0) is a trap. When you remove index 0, Python has to slide every remaining element one slot to the left to close the gap — exactly the same shift tax we saw with arrays. If you dequeue 1 million items from a 1-million-element list one at a time, you don't do 1 million operations. You do roughly 500 billion. That is the difference between a script that runs in milliseconds and one that you kill after 20 minutes.

There are three real ways to fix this:

Option 1: Linked list (the conceptual fix)

Instead of shifting elements, maintain a pointer to the head. Dequeue means "advance the head pointer one node forward and return the old head." O(1), no shifting.

flowchart LR
    HEAD["head"] --> N1["3"] --> N2["7"] --> N3["1"] --> NULL["null"]
    style HEAD fill:#7c5cff,color:#0a0a0f
    style N1 fill:#22d3ee,color:#0a0a0f

Dequeue just moves head to N2. Nothing else changes. The tradeoff: you burn extra memory per node (the next-pointer overhead) and lose cache locality — nodes are scattered in the heap, not contiguous. For most queue use cases this is fine. You're not doing random access; you're always touching the front.

Option 2: Circular buffer (the fast fix)

Keep a fixed-size (or resizable) array but track two indices: head and tail. Enqueue increments tail, dequeue increments head. Both are O(1). When tail reaches the end of the array, it wraps back to 0 — hence "circular."

flowchart LR
    subgraph "Backing array (capacity 6)"
      direction LR
      A0["_"] --- A1["3<br/>← head"] --- A2["7"] --- A3["1<br/>← tail"] --- A4["_"] --- A5["_"]
    end
    style A1 fill:#22d3ee,color:#0a0a0f
    style A3 fill:#7c5cff,color:#0a0a0f

This is what most production queue implementations use under the hood. You get contiguous memory (great for cache), no shifting, and O(1) at both ends. The bookkeeping is a few modular arithmetic operations per operation.

Option 3: collections.deque (the practical fix)

In Python, just use this:

from collections import deque

q = deque()
q.append(7)       # enqueue — O(1)
q.append(3)
q.popleft()       # dequeue — O(1), for real this time

collections.deque is a doubly-linked list of fixed-size blocks. It gives you O(1) append and O(1) popleft, and you don't have to write a circular buffer from scratch. This is the right default for queues in Python. Not a list. A deque.

The queue visualizer — go use it

{ "type": "queue", "variant": "queue", "title": "enqueue / dequeue", "data": [10, 20, 30, 40] }

Step through enqueue and dequeue a few times. Notice that 10 was inserted first and it is the first one pulled off. Add several elements, then dequeue them — they come out in exactly the order they went in. That strict ordering is what makes queues so trustworthy for scheduling and traversal: you never accidentally process something out of turn.

Core operations at a glance

Operation	Complexity	Notes
enqueue(x)	O(1)	push to the back
dequeue()	O(1)	pop from the front — only if backed correctly
peek()	O(1)	read front without removing
is_empty()	O(1)	always cheap
size()	O(1)	maintained as a counter

Those are every operation you ever need. Queues are not lookup structures. If you need to search inside a queue, you have picked the wrong data structure. The whole point is to process elements in order, one at a time, from the front.

Where queues actually show up

BFS — the killer app

Breadth-first search is a queue with a graph on top. The algorithm is almost embarrassingly simple once you see it:

1. Push the starting node into the queue.
2. While the queue isn't empty: dequeue the front node, process it, push all its unvisited neighbors.
3. Because you always process the oldest (shallowest) nodes first, you explore level by level.

That level-by-level guarantee is exactly what BFS promises — and it falls out automatically from FIFO ordering. Swap the queue for a stack and you get DFS for free. The BFS patterns article goes deep on this, but every BFS you ever write will be a variation of the same seven lines.

from collections import deque

def bfs(graph, start):
    visited = {start}
    queue = deque([start])

    while queue:
        node = queue.popleft()
        print(node)                         # process
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)      # explore later

Change popleft() to pop() and you have DFS. That is how closely the algorithm's character is tied to the data structure.

Task scheduling

Amazon's SQS, Kafka consumers, Celery workers, OS process schedulers — all of these are queues at their core. Jobs arrive in some order; they need to be processed in that same order; each worker pulls from the front. The FIFO guarantee prevents starvation: no job can be indefinitely skipped in favor of newer arrivals.

Sliding window problems

This is where the deque shines over a plain queue. The "max in sliding window" problem — given an array and a window size k, find the maximum in every window of size k — can be solved in O(n) using a deque as a monotone structure:

• Maintain a deque of indices such that the corresponding values are always decreasing.
• For each new element, pop from the back anything smaller than it (those can never be a future window max).
• Pop from the front whenever the front index falls outside the window.

Both ends need to be cheap. A plain queue can't pop from the back. A deque can. That is the entire reason the deque exists as a distinct type.

from collections import deque

def max_sliding_window(nums, k):
    dq = deque()        # stores indices, values decreasing
    result = []

    for i, val in enumerate(nums):
        # drop indices that are out of the current window
        while dq and dq[0] < i - k + 1:
            dq.popleft()

        # drop indices whose values are smaller than the current — they're useless
        while dq and nums[dq[-1]] < val:
            dq.pop()

        dq.append(i)

        if i >= k - 1:
            result.append(nums[dq[0]])  # front always holds the window max index

    return result

This runs in O(n) — each index is added and removed at most once. With a plain array it's O(n·k). The deque is not a fancy optimization; it is what makes the efficient solution possible.

Network buffers and rate limiting

When packets arrive faster than they can be processed, they sit in a queue. When a service enforces "no more than 100 requests per second," it keeps a queue of request timestamps. These are not interview problems — they are the actual reason CPUs have hardware queues and why every message broker you will ever use has "queue" in its name or description.

The cousins: deque and priority queue

A deque (pronounced "deck") is what you get when you relax the restriction and allow O(1) push/pop at both ends. In Python, collections.deque is always the right queue implementation. In Java it's ArrayDeque. Use it unless you have a specific reason to use a one-ended queue. You lose nothing and gain flexibility.

A priority queue throws out the FIFO rule entirely. Instead of "oldest first," it gives you "highest priority first." Under the hood it's almost always a heap. Python's heapq gives you a min-heap (smallest value has highest priority). Use a priority queue when urgency matters more than order — Dijkstra's algorithm, CPU scheduling with priorities, merge-k-sorted-lists.

import heapq

pq = []
heapq.heappush(pq, (2, "medium task"))
heapq.heappush(pq, (1, "urgent task"))
heapq.heappush(pq, (3, "low task"))

priority, task = heapq.heappop(pq)   # → (1, "urgent task")

The rule of thumb: use a queue when you care about when something arrived. Use a priority queue when you care about how important it is.

A worked example: level-order traversal of a binary tree

This shows up in roughly half of all tree-related interviews. The question: given a binary tree, return its node values level by level ([[3], [9, 20], [15, 7]] for the standard example).

The insight is that a queue processes nodes in exactly the order you want: you push the root, then for each node you pop, you push its children. By the time you get to a node's children, all nodes at the same depth have already been processed.

from collections import deque

def level_order(root):
    if not root:
        return []

    result = []
    queue = deque([root])

    while queue:
        level_size = len(queue)          # snapshot: how many nodes at this depth
        level = []

        for _ in range(level_size):
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

        result.append(level)

    return result

The key move is level_size = len(queue) before the inner loop. That freezes the count of nodes at the current depth, so the inner loop processes exactly one level at a time. The outer loop runs once per level. Total time: O(n), every node visited once. Total space: O(w) where w is the maximum width of the tree — the queue never holds more than one full level at a time.

Pitfalls people actually hit

Using a list and wondering why it's slow. list.pop(0) is O(n). Always. If your queue has 100k elements and you're calling pop(0) in a loop, you've written an O(n²) BFS. Use collections.deque.

Forgetting to mark nodes visited before enqueueing, not after dequeuing. In BFS on a graph, if you mark a node as visited when you dequeue it (rather than when you enqueue it), you'll enqueue the same node multiple times from different neighbors. This turns O(V + E) into O(E) enqueues per node in a dense graph — potentially O(V · E). Always mark visited the moment you push to the queue.

Confusing a queue with a priority queue. A plain queue gives you FIFO. A priority queue gives you the minimum (or maximum). These look similar but behave very differently. heapq.heappop is not the same as deque.popleft. Use the wrong one and your Dijkstra becomes BFS.

Holding references in a BFS queue that prevent garbage collection. In languages with garbage collection, a queue that holds references to large objects — entire graph nodes with fat payloads — keeps them alive until they're dequeued. If your BFS queue gets wide (exponentially branching graphs), you're holding a lot in memory. Sometimes it's worth storing node identifiers and looking up the full object only when needed.

When not to use a queue

• You need O(1) membership testing ("is this item already queued?"): a queue doesn't help. Pair it with a hash set on the side.
• You need random access or search: use an array or hash table. A queue forces linear scan.
• You need the smallest or largest element next: reach for a heap-backed priority queue.
• You need O(1) front and back, plus arbitrary removal from the middle: that's a doubly-linked list with a hash map (the data structure behind Python's OrderedDict and LRU cache).

For BFS-shaped problems, first-in-first-out scheduling, and anything where order-of-arrival is the rule — the queue is exactly right. It's one of those structures where the constraint is the feature.