Queues and Deques in Python: FIFO, Ring Buffers, and collections.deque

A queue is the one data structure you already understand, because you have stood in one. First in, first out: whoever arrived earliest gets served earliest, new arrivals join the back, and nobody reaches into the middle. That is the entire contract.

The interesting part is not the concept, it is the cost. A Python list looks like a perfectly good queue — append at the back, pop(0) at the front — and it is a trap. pop(0) is O(n), because taking the first element out of a contiguous array means copying every surviving element one slot left. Drain a 10,000-item queue that way and you pay 49,995,000 element copies to remove 10,000 things.

So this post builds the fix twice: a ring buffer on a fixed-size list, where two indices and one modulo replace all that shifting, then collections.deque, which is what you should actually reach for. Along the way, the two-stack queue and why its amortised cost is constant even when one dequeue is slow.

The idea

A queue supports two operations. Enqueue puts an item at the back. Dequeue removes and returns the item at the front. Many implementations add peek, which reads the front without removing it. Nothing else is promised — no indexing, no reordering, no searching.

That restriction is the whole point. Because the only entrance is the back and the only exit is the front, the order in which items leave is exactly the order in which they arrived: first in, first out, universally shortened to FIFO.

Compare that with a stack, the other single-exit structure. A stack pushes and pops at the same end, so the newest item leaves first. One method call is the entire difference, and it changes the order in which an algorithm explores the world: breadth-first and depth-first search are the same six lines with popleft swapped for pop, as you will see below.

A deque — pronounced "deck", short for double-ended queue — lets you add and remove at both ends. It is a strict superset: use one end only and it behaves as a stack, use opposite ends and it is a queue.

Why a Python list is the wrong queue

A Python list is a contiguous block of pointers with spare room at the end. append writes into the next free slot and pop() clears the last one, so both are O(1) amortised — that is what dynamic arrays are good at. The front has no such spare room. Removing values[0] leaves a hole at index 0, and a contiguous array cannot have holes, so CPython closes it by sliding everything after it down one place. Here is that slide written out in Python rather than hidden inside a single memmove:

def pop_front(values: list[int]) -> int:
    """Remove and return values[0], sliding every survivor one slot to the left.

    This is what CPython does inside list.pop(0). Writing it out in Python makes
    the copying visible instead of hiding it behind a single memmove call.
    """
    first = values[0]
    for index in range(len(values) - 1):
        values[index] = values[index + 1]  # each survivor slides one slot left
    values.pop()                           # drop the now-duplicated tail slot
    return first


numbers = [10, 20, 30, 40, 50]
print(pop_front(numbers), numbers)
print(pop_front(numbers), numbers)

10 [20, 30, 40, 50]
20 [30, 40, 50]

One removal from a list of 5 copies 4 elements; one from a list of 1,000,000 copies 999,999. The cost is proportional to what is left behind, and over a full drain that adds up in a way worth counting properly:

def moves_to_drain(count: int) -> int:
    """Element copies needed to empty a list of `count` items with front pops."""
    return sum(size - 1 for size in range(count, 0, -1))


for count in (10, 100, 1_000, 10_000, 100_000):
    print(f"{count:>7,} items -> {moves_to_drain(count):>14,} element moves")

     10 items ->             45 element moves
    100 items ->          4,950 element moves
  1,000 items ->        499,500 element moves
 10,000 items ->     49,995,000 element moves
100,000 items ->  4,999,950,000 element moves

The sum is 0 + 1 + 2 + … + (n − 1), which equals n(n − 1) / 2. Removing n items therefore costs O(n²) element moves — quadratic work for a linear job. Ten times the queue costs a hundred times the copying, and the last row is five billion moves to empty a list of a hundred thousand.

Be fair about the constant, though. Each "move" is one pointer copy inside a single memmove, which a modern CPU does at gigabytes per second, so a queue that never exceeds a few hundred items really is fine on a list. What you cannot do is let n grow. list.insert(0, x) has the same problem pointing the other way.

Watching a ring buffer work

The fix is to stop moving the data and move the indices instead.

Take a fixed-size list of capacity slots and keep two numbers alongside it: head, the index of the oldest item, and size, how many slots are in use. The back of the queue — the next free slot — is then always at (head + size) % capacity. Dequeue reads slot head and advances head by one; enqueue writes to that computed tail and increases size. Neither touches any other slot.

The modulo is what turns a flat list into a circle: when an index would step off the right-hand end, % capacity folds it back to 0, so the storage has no end to fall off. Trace it on capacity 4, writing . for a free slot:

• start — [. . . .], head 0, tail 0, size 0.
• enqueue A, B, C — they land in slots 0, 1 and 2. head 0, tail 3, size 3.
• dequeue twice — returns A, then B. Those slots are cleared and head walks to 2, size drops to 1. Nothing moved: C still sits physically at index 2.
• enqueue D — tail is (2 + 1) % 4 = 3, so D goes to index 3, giving [. . C D].
• enqueue E — tail is now (2 + 2) % 4 = 0, so E goes to index 0, before C in the list and after it in the queue. That is the wraparound: [E . C D].
• enqueue F — tail is (2 + 3) % 4 = 1, giving [E F C D] with size 4. The buffer is full, and head and tail are both 2.

That last line is the trap in every hand-rolled ring buffer. When it is completely full, tail has walked all the way round onto head — and when it is completely empty, tail equals head as well. From the indices alone the two states are indistinguishable. An explicit size, which the code below keeps, settles it; the other classic fix is to leave one slot permanently empty so "full" means (tail + 1) % capacity == head.

The code

class RingBuffer:
    """A fixed-capacity FIFO queue stored in one Python list, with wraparound.

    Nothing ever shifts. `head` names the slot holding the oldest item and
    `size` says how many slots after it are in use, so the back of the queue is
    always at (head + size) % capacity.
    """

    def __init__(self, capacity: int) -> None:
        if capacity < 1:
            raise ValueError("capacity must be at least 1")
        self._slots: list = [None] * capacity  # None marks a free slot
        self._head = 0
        self._size = 0

    def __len__(self) -> int:
        return self._size

    @property
    def head(self) -> int:
        """Index of the oldest item. Printed by the trace below."""
        return self._head

    @property
    def tail(self) -> int:
        """Index of the next free slot, which is where the next item lands."""
        return (self._head + self._size) % len(self._slots)

    def enqueue(self, value: object) -> None:
        if self._size == len(self._slots):
            raise IndexError("enqueue on a full buffer")
        self._slots[self.tail] = value
        self._size += 1

    def dequeue(self) -> object:
        if self._size == 0:
            raise IndexError("dequeue from an empty buffer")
        value = self._slots[self._head]
        self._slots[self._head] = None  # release the reference so it can be freed
        self._head = (self._head + 1) % len(self._slots)
        self._size -= 1
        return value

    def peek(self) -> object:
        if self._size == 0:
            raise IndexError("peek at an empty buffer")
        return self._slots[self._head]

    def snapshot(self) -> list:
        """A copy of the raw storage, so the trace can show the physical slots."""
        return list(self._slots)

Running the trace from the previous section for real, printing the physical slots rather than the logical queue:

def show(buffer: RingBuffer, note: str) -> None:
    slots = " ".join("." if slot is None else str(slot) for slot in buffer.snapshot())
    print(f"{note:<11} [{slots}]  head={buffer.head} tail={buffer.tail} size={len(buffer)}")


buffer = RingBuffer(4)
show(buffer, "start")

for name in ("A", "B", "C"):
    buffer.enqueue(name)
    show(buffer, f"enqueue {name}")

for _ in range(2):
    value = buffer.dequeue()
    show(buffer, f"dequeue {value}")

for name in ("D", "E", "F"):
    buffer.enqueue(name)
    show(buffer, f"enqueue {name}")

try:
    buffer.enqueue("G")
except IndexError as error:
    print(f"enqueue G   -> IndexError: {error}")

start       [. . . .]  head=0 tail=0 size=0
enqueue A   [A . . .]  head=0 tail=1 size=1
enqueue B   [A B . .]  head=0 tail=2 size=2
enqueue C   [A B C .]  head=0 tail=3 size=3
dequeue A   [. B C .]  head=1 tail=3 size=2
dequeue B   [. . C .]  head=2 tail=3 size=1
enqueue D   [. . C D]  head=2 tail=0 size=2
enqueue E   [E . C D]  head=2 tail=1 size=3
enqueue F   [E F C D]  head=2 tail=2 size=4
enqueue G   -> IndexError: enqueue on a full buffer

How the code maps to the idea

self._slots never changes length. It is allocated once and every later operation writes into an existing slot. That is what makes a ring buffer attractive in real-time code: after construction it never allocates, so it can never pause to grow.

tail is derived, not stored. Computing it from head and size means there is no second field to keep in sync, and no way for the two to drift apart. Store both indices independently and the full-versus-empty ambiguity comes straight back.

% len(self._slots) is the whole wraparound. It appears exactly twice, in tail and in dequeue, and both are the same idea: advance an index, then fold it back into the range 0 to capacity − 1. Miss it in one of the two and the buffer works perfectly until the first wrap, which is the worst kind of bug because tests rarely fill it.

Clearing the slot on dequeue is about memory, not correctness. head has already moved past it, so nothing will read it — but leaving the object there keeps a reference alive, and a buffer of capacity 10,000 can pin 10,000 dead objects.

The overflow policy is a design decision. This version raises. The alternatives are to block until a consumer frees a slot (what a thread-safe queue does), to overwrite the oldest item (what a log buffer does), or to drop the new one. Drifting into one by accident is how monitoring data quietly disappears.

The edge cases fall out of the arithmetic. Capacity 1 works, because tail is always (head + size) % 1, which is 0. Empty is caught by the size == 0 guard before any index is computed, full by size == capacity. There is no special case for the wrap itself.

collections.deque, and what to actually use

You will almost never write that class at work, because the standard library ships something better.

from collections import deque

tasks = deque(["render", "email", "invoice"])
tasks.append("backup")      # arrives at the back, like any other job
tasks.appendleft("urgent")  # jumps the queue, which a plain list cannot do cheaply
print(list(tasks))

print(tasks.popleft(), tasks.pop())
print(list(tasks), len(tasks))

recent = deque(maxlen=3)  # a fixed-size ring buffer, straight from the library
for line in ("line 1", "line 2", "line 3", "line 4", "line 5"):
    recent.append(line)
print(list(recent))

['urgent', 'render', 'email', 'invoice', 'backup']
urgent backup
['render', 'email', 'invoice'] 3
['line 3', 'line 4', 'line 5']

deque gives you O(1) append, appendleft, pop and popleft. It grows on demand, so there is no capacity to choose, and deque(maxlen=n) hands you a bounded ring buffer in one keyword argument: once full, every new append discards one item from the opposite end. That last line kept the most recent three of five without you managing a single index.

It reaches O(1) at both ends by not being one contiguous array. CPython implements a deque as a doubly linked list of fixed-size blocks, 64 item slots each. append writes into the rightmost block and links a fresh one only when that block fills; popleft reads from the leftmost and unlinks it when it empties. Neither end disturbs the other, and no element ever moves.

The trade-off is worth knowing before you reach for it everywhere. Because the blocks are chained, getting to the middle means walking the chain: d[0] and d[-1] are O(1), an index near the centre is O(n), and insert, remove and the in operator are O(n) too. A deque is a queue, not a faster list.

For threads, do not build your own locking around one. queue.Queue is the standard library's producer–consumer queue — blocking get, an optional maxsize for backpressure, task_done and join for waiting on completion — and it stores its items in a collections.deque internally. asyncio.Queue does the same for coroutines. Individual append and popleft calls are atomic, but "if it is non-empty, pop it" is two calls, and two calls race.

The two-stack queue, and amortised cost

There is a classic trick worth understanding even though you should not ship it in Python: a FIFO queue built from two LIFO stacks. Arrivals are pushed onto an inbox stack, departures are popped from an outbox stack, and when the outbox runs dry you pour the whole inbox into it. Because a stack reverses whatever you pour through it, the oldest item ends up on top.

class TwoStackQueue:
    """A FIFO queue built from two LIFO stacks: arrivals in, departures out."""

    def __init__(self) -> None:
        self._inbox: list[str] = []   # newest arrival on top
        self._outbox: list[str] = []  # oldest arrival on top
        self.moves = 0                # every individual push and pop, counted

    def __len__(self) -> int:
        return len(self._inbox) + len(self._outbox)

    def enqueue(self, value: str) -> None:
        self._inbox.append(value)
        self.moves += 1

    def dequeue(self) -> str:
        if not self._outbox:
            # Pour only when the outbox is empty. Pouring on top of leftovers
            # would stack newer items above older ones and break FIFO order.
            while self._inbox:
                self._outbox.append(self._inbox.pop())
                self.moves += 2
        if not self._outbox:
            raise IndexError("dequeue from an empty queue")
        self.moves += 1
        return self._outbox.pop()


small = TwoStackQueue()
for letter in "ABC":
    small.enqueue(letter)
print(small.dequeue(), small.dequeue())
small.enqueue("D")
print(small.dequeue(), small.dequeue())
print(small.moves, "unit moves for 4 enqueues and 4 dequeues")

big = TwoStackQueue()
for index in range(1000):
    big.enqueue(str(index))
drained = [big.dequeue() for _ in range(1000)]
print(drained[0], drained[-1], big.moves, "moves =", big.moves / 2000, "per operation")

A B
C D
16 unit moves for 4 enqueues and 4 dequeues
0 999 4000 moves = 2.0 per operation

Now the counting argument, because "amortised O(1)" has to be earned. Follow one item through its whole life: pushed onto the inbox once, popped off the inbox at most once, pushed onto the outbox at most once, popped off the outbox at most once. Four constant-time steps, and no item is ever poured twice, because the pour only happens when the outbox is empty and an item only enters the outbox once.

So m operations cost at most 4m unit steps in total, however the enqueues and dequeues interleave, and dividing by m gives a constant average. The counters confirm it: 4 elements cost 16 moves, 1,000 elements cost 4,000 — 2.0 moves per operation in both cases, unchanged as n grows a thousandfold.

The honest caveat is that one dequeue can still be slow. If a thousand items have piled up in the inbox, the dequeue that triggers the pour does a thousand moves before it returns. Amortised O(1) bounds the total, not any individual call. For a batch job that is irrelevant; for a request handler with a latency budget, a ring buffer or a deque with worst-case O(1) is the safer choice.

Complexity

Everything above is O(1) per operation except the list:

The ring buffer's O(1) is worst case, not amortised. enqueue and dequeue each run a fixed number of statements: one bounds check, one index computation, one assignment, one counter update. No loop means no input size for the cost to depend on, and nothing can trigger a resize because the storage was allocated at full size up front.

The deque's O(1) is amortised, by a factor of 64. Most appends write into a block that already has room. One append in every 64 allocates a new block — a single fixed-size allocation, and CPython keeps recently freed blocks on a small free list so fill-and-drain cycles usually reuse them. Spread that allocation over the 64 appends it serves and the per-append cost is constant.

The list's amortised O(1) append comes from geometric over-allocation. CPython grows a full list by roughly one eighth, so n appends trigger O(log n) reallocations copying O(n) elements in total, which averages to O(1) each. pop(0)'s problem is not allocation at all — the shift is simply unavoidable in a contiguous array.

Space. A ring buffer costs O(capacity) permanently, whether it holds one item or all of them; that fixed footprint is the feature. A deque costs O(n), rounded up to whole 64-slot blocks. The two-stack queue costs O(n) across its two lists.

When to use it, and when not to

Use a queue when arrival order is service order and you only touch the two ends: work waiting for a worker, nodes waiting to be explored, bytes waiting to be written.

In Python that means collections.deque by default — written in C, O(1) at both ends, no configuration. Use deque(maxlen=n) when you want only the most recent n of something, and queue.Queue or asyncio.Queue the moment more than one thread or task is involved, because those add blocking, timeouts and backpressure a bare deque does not have.

Write your own ring buffer only when the fixed allocation is the requirement — in C, in embedded firmware, in an audio callback that must never allocate. In Python, deque(maxlen=n) already is that ring and is implemented in C, so hand-rolling one is a learning exercise rather than an optimisation.

Do not use a queue when priority matters. If the next item out should be the most urgent rather than the oldest, you want a heap-backed priority queue and heapq; scanning a queue for the most important item makes every dequeue O(n). Do not use one when you need random access or slicing either — that is a list. And do not use an in-process queue for work that must survive a crash, because durability needs a broker or a database table, not a deque in memory.

Where it shows up in the real world

Breadth-first search. A queue holds the frontier of nodes discovered but not yet explored. Because it is FIFO, every node at distance 1 is expanded before any node at distance 2, which is exactly why BFS finds shortest paths in an unweighted graph. Swap popleft for pop and the same code goes depth-first:

graph = {
    "A": ["B", "C"],
    "B": ["D"],
    "C": ["D", "E"],
    "D": ["F"],
    "E": ["F"],
    "F": [],
}


def traverse(graph: dict[str, list[str]], start: str, breadth_first: bool) -> list[str]:
    """Visit every reachable node; FIFO gives breadth-first, LIFO gives depth-first."""
    seen = {start}
    frontier = deque([start])
    order: list[str] = []

    while frontier:
        node = frontier.popleft() if breadth_first else frontier.pop()
        order.append(node)
        for neighbour in graph[node]:
            if neighbour not in seen:
                seen.add(neighbour)
                frontier.append(neighbour)

    return order


print("popleft ->", traverse(graph, "A", breadth_first=True))
print("pop     ->", traverse(graph, "A", breadth_first=False))

popleft -> ['A', 'B', 'C', 'D', 'E', 'F']
pop     -> ['A', 'C', 'E', 'F', 'D', 'B']

FIFO visits A, then both of A's neighbours, then theirs: strictly by distance. LIFO dives to F before it ever comes back for B. Each node is enqueued at most once and dequeued at most once, and each edge is examined once from its owner, so either traversal is O(V + E). Read breadth-first search and depth-first search for the full treatment.

Inside Python itself. The asyncio event loop keeps its ready-to-run callbacks in a collections.deque and pops them from the left each iteration. queue.Queue and asyncio.Queue both store their items in one. multiprocessing.Queue buffers outgoing objects in a deque before its feeder thread writes them to the pipe. The tail recipe in the itertools documentation is nothing but deque(iterable, maxlen=n).

Job queues. Sidekiq stores jobs in Redis lists and pulls them with BRPOP, a blocking dequeue. Celery and every other task runner have the same shape: producers enqueue work, a pool of workers dequeues it, and FIFO ordering keeps waiting times predictable.

Ring buffers in systems software. The Linux kernel log is a ring buffer, which is why dmesg eventually loses the oldest boot messages instead of exhausting memory. Network cards exchange packets with the kernel through RX and TX descriptor rings, and io_uring names its two shared rings in the API itself. Real-time audio moves samples between the device callback and the application through a ring, because the callback must never allocate — the same reason LMAX built their trading exchange's Disruptor around a preallocated one.

Sliding window maxima. A deque used as a monotonic queue answers "what is the largest value in every window of k consecutive items" in linear time, by holding indices whose values decrease from left to right so the front is always the current maximum:

def sliding_window_max(values: list[int], width: int) -> list[int]:
    """The maximum of every window of `width` consecutive values, in O(n) total.

    `window` holds indices whose values decrease from left to right, so the
    leftmost index is always the maximum of the current window.
    """
    if not 1 <= width <= len(values):
        raise ValueError("width must be between 1 and len(values)")

    window: deque[int] = deque()
    result: list[int] = []

    for index, value in enumerate(values):
        # The front index can fall off the left edge, and only one can per step.
        if window and window[0] <= index - width:
            window.popleft()
        # A smaller value that is also older can never win again, so drop it.
        while window and values[window[-1]] <= value:
            window.pop()
        window.append(index)
        if index >= width - 1:
            result.append(values[window[0]])

    return result


print(sliding_window_max([1, 3, -1, -3, 5, 3, 6, 7], 3))
print(sliding_window_max([9, 8, 7, 6], 2), sliding_window_max([4], 1))

[3, 3, 5, 5, 6, 7]
[9, 8, 7] [4]

That inner while loop looks like it could be O(n) per step, which would make the whole thing quadratic. It cannot be. Every index is appended exactly once and popped at most once, so the entire run performs at most n appends and n pops — 2n deque operations for n items, therefore O(n) total. The naive alternative, calling max() on each window, is O(n × width). See the sliding window technique for more of the pattern.

Common mistakes

Calling list.pop(0) in a loop. The headline bug of this whole post: it looks like O(1), it is O(n), and it turns an otherwise linear algorithm quadratic. The fix is one import and one method name.

Indexing a deque in a loop. Having switched to a deque, writing for i in range(len(d)): use(d[i]) is O(n²), because every index walks the block chain. Iterate the deque directly instead, which is O(n).

Applying the modulo to only one index. Wrapping the tail but not the head, or the reverse, gives a buffer that behaves perfectly until the moment it first wraps. Test past capacity or you will never see it.

Testing emptiness with head == tail. True when the buffer is empty and equally true when it is completely full. Keep a size counter, or deliberately leave one slot unused.

Leaving dequeued references in the slots. Not a correctness bug, but a fixed-capacity buffer that never clears its slots pins every object it has ever held until that slot is reused.

Pouring into a non-empty outbox in the two-stack queue. It stacks newer items above older ones and silently breaks FIFO order. Guard the pour with if not self._outbox.

Scanning a queue for the most urgent item. That is a priority queue wearing the wrong structure; use heapq.

Practice

1. Add an enqueue_front method to RingBuffer using head = (head - 1) % capacity, and check it does the right thing when head is already 0.
2. Change the overflow policy so a full buffer overwrites its oldest item instead of raising, then confirm the result matches deque(maxlen=capacity) on the same input.
3. Write a rotate for a full ring buffer that moves the front k items to the back in constant time, and explain why deque.rotate(k) cannot manage the same trick.
4. Build a queue from a singly linked list that keeps both a head and a tail pointer, and argue why both enqueue and dequeue are O(1).
5. Use a single deque to test whether a string is a palindrome by comparing popleft() with pop() until fewer than two characters remain.

Summary

A queue is one rule — oldest out first — and all the interest lies in keeping that rule O(1) at both ends. A list cannot, because removing the front of a contiguous array shifts everything behind it, at a total cost of n(n − 1) / 2 moves to drain n items. A ring buffer can, by advancing indices modulo the capacity so nothing ever moves. collections.deque does the same with a chain of 64-slot blocks, handles growth for you, and is written in C.

Reach for deque by default, deque(maxlen=n) for a bounded window, and queue.Queue when threads are involved. Write the ring buffer yourself only to understand it.

Keep reading

• Stacks in Python — the mirror image, last in first out, and the other half of every traversal.
• Breadth-First Search — the algorithm that turns a queue into shortest paths.
• Arrays and Dynamic Arrays — why append is cheap and pop(0) is not, from the memory layout up.