Practical Queues and Sliding Windows with Python deque

Many programs need a sequence that changes at both ends. A worker may append new jobs on the right and consume the oldest job from the left. A monitoring loop may keep only the most recent measurements. An algorithm may need to add or remove candidates from either side while scanning an input stream.

A Python list is excellent when random access and operations near the right end dominate. It is a poor fit for a FIFO queue that repeatedly removes index zero, because the remaining list elements must be shifted. The collections.deque type is designed for efficient appends and pops at both ends.

The name is short for double-ended queue and is pronounced “deck.” Its useful property is not that it replaces lists everywhere, but that it makes operations at both boundaries cheap and explicit.

Build a FIFO queue

A basic first-in, first-out queue appends new work on the right and removes old work from the left:

from collections import deque

queue = deque(["first", "second"])
queue.append("third")

while queue:
    item = queue.popleft()
    print(item)

The output preserves arrival order:

first
second
third

For a deque, appends and pops at either end have approximately O(1) performance. By contrast, list.pop(0) requires O(n) data movement because elements after the removed item shift toward the beginning.

That difference matters for queues that can grow large or are drained frequently. For a tiny collection used occasionally, either representation may be fast enough, so choose the structure that makes the access pattern clear.

Peek without removing

The two ends are directly indexable:

from collections import deque

queue = deque(["oldest", "middle", "newest"])

print(queue[0])
print(queue[-1])

Indexing at either end is O(1). Access becomes slower toward the middle of a deque, reaching O(n), so a deque should not replace a list when frequent arbitrary indexing is important.

Use both ends deliberately

The core operations come in left and right pairs:

append()       appendleft()
pop()          popleft()
extend()       extendleft()

This makes a deque suitable for both queue and stack behavior.

A stack can use the right side only:

from collections import deque

stack = deque()
stack.append("a")
stack.append("b")

assert stack.pop() == "b"

A FIFO queue normally uses append() with popleft().

Using both sides is useful for algorithms that maintain a frontier or a small working set, but define the meaning of each end before writing the operations. Code becomes difficult to review when appendleft(), append(), popleft(), and pop() are mixed without a clear invariant.

Watch the ordering of extendleft

extendleft() is easy to misread. It performs a series of left appends, so the iterable’s order is reversed in the resulting deque:

from collections import deque

values = deque([3, 4])
values.extendleft([1, 2])

print(list(values))

The result is:

[2, 1, 3, 4]

If the intended result is [1, 2, 3, 4], reverse the incoming iterable before extending the left side:

values = deque([3, 4])
values.extendleft(reversed([1, 2]))

This behavior follows directly from repeated appendleft() calls; it is not equivalent to prepending a list as one block.

Keep bounded recent history with maxlen

A deque can enforce a maximum length:

from collections import deque

recent = deque(maxlen=3)

for value in [10, 20, 30, 40, 50]:
    recent.append(value)

print(list(recent))

The result is:

[30, 40, 50]

Once a bounded deque is full, adding an item at one end discards an item from the opposite end. This makes maxlen useful for recent-event histories, fixed-size tails, and simple sliding windows where old values should expire automatically.

The maximum length is fixed when the deque is created and is exposed through the read-only maxlen attribute.

Automatic eviction is silent

The convenience of maxlen is also a trade-off. append() does not return the element that was discarded.

If the application must perform cleanup, persist the evicted object, or update another data structure when an item leaves the window, detect the outgoing item before appending:

from collections import deque

window = deque(maxlen=3)


def append_with_eviction(value):
    evicted = window[0] if len(window) == window.maxlen else None
    window.append(value)
    return evicted

This example assumes None is an acceptable “nothing evicted” marker. If None is a valid stored value, return a separate boolean or use a unique sentinel so the two cases cannot be confused.

Also note that insert() behaves differently on a full bounded deque: if insertion would exceed maxlen, it raises IndexError rather than silently evicting an element.

Build a fixed-size sliding window

A bounded deque is a compact way to retain the last n observations:

from collections import deque


def moving_average(values, size):
    if size <= 0:
        raise ValueError("size must be positive")

    window = deque(maxlen=size)
    total = 0

    for value in values:
        if len(window) == size:
            total -= window[0]

        window.append(value)
        total += value

        if len(window) == size:
            yield total / size


print(list(moving_average([2, 4, 6, 8, 10], 3)))

The output is:

[4.0, 6.0, 8.0]

The running total avoids summing the whole window on every step. Before appending to a full deque, the code subtracts the value that is about to be evicted. After the append, it adds the new value.

This pattern works well for additive statistics such as sums and averages. Other window calculations may need different data structures. For example, repeatedly finding the minimum of a large window by calling min(window) scans the window each time; specialized monotonic-queue algorithms can do better when that operation is performance-critical.

Rotate when the logical boundary moves

rotate() moves elements around the ends without requiring manual pop-and-append loops in application code:

from collections import deque

workers = deque(["a", "b", "c"])
workers.rotate(-1)

print(list(workers))

The result is:

['b', 'c', 'a']

A positive rotation moves elements to the right; a negative rotation moves them to the left. For a non-empty deque, rotating one step right is equivalent to moving the rightmost item to the left, and rotating one step left is equivalent to moving the leftmost item to the right.

Rotation can express round-robin traversal cleanly:

from collections import deque

workers = deque(["worker-a", "worker-b", "worker-c"])

for _ in range(5):
    current = workers[0]
    print(current)
    workers.rotate(-1)

This is appropriate when all workers remain in the cycle. A real scheduler often needs additional logic for unavailable workers, weights, backpressure, or fairness guarantees; rotate() alone does not provide those policies.

Remove from the correct end

pop() and popleft() both raise IndexError when the deque is empty:

from collections import deque

queue = deque()

if queue:
    item = queue.popleft()

Checking first is suitable when an empty deque is an expected state in single-threaded code.

Do not treat if queue: queue.popleft() as synchronization between threads. Another thread can change shared state between logically separate operations. If producers and consumers need blocking behavior, capacity management, task tracking, or coordinated multi-thread access, use the queue module or explicit synchronization designed for the workflow.

Understand the thread-safety boundary

Python’s documentation describes deque appends and pops at either end as thread-safe. That guarantee is useful, but it does not turn an arbitrary sequence of deque operations into one atomic transaction.

For example, this is a compound operation:

if queue:
    item = queue.popleft()

The emptiness check and removal are separate actions. Application-level invariants spanning multiple actions still need appropriate synchronization.

For producer-consumer programs, queue.Queue provides locking semantics and operations such as blocking put() and get(). Use deque directly when its data-structure operations are what you need; use a synchronized queue when coordination between threads is part of the requirement.

Avoid arbitrary middle operations on hot paths

A deque supports methods such as index(), remove(), and indexed access, but its performance strengths are concentrated at the ends.

This code is valid:

from collections import deque

values = deque([10, 20, 30, 40])
values.remove(30)

It should not be mistaken for a constant-time arbitrary deletion. Finding a value or reaching a middle position requires traversal.

If the dominant workload is searching by key, deleting arbitrary records, or accessing many positions by index, another representation may be more appropriate. A dictionary, set, list, or a combination of structures may better match the required operations.

Be careful when mutating during iteration

Treat iteration and structural mutation as separate phases unless the algorithm is explicitly designed around end operations.

Instead of iterating over a deque while simultaneously adding or removing elements from it, a queue-processing loop is usually clearer:

from collections import deque

pending = deque([1, 2, 3])

while pending:
    item = pending.popleft()
    print(item)

If processing can enqueue more work, decide whether those new items belong in the same run and which end they should enter. That decision changes traversal semantics and should be part of the algorithm rather than an accidental consequence of mutation.

Choose deque, list, or Queue by access pattern

Use a deque when the program frequently adds or removes items at both ends, needs an efficient FIFO queue in non-blocking application logic, or wants a bounded recent-history buffer.

Use a list when random indexed access is important and mutations are concentrated near the right end. Lists also provide familiar slicing and sorting operations that a deque is not designed to replace.

Use queue.Queue when threads need a synchronized producer-consumer abstraction with blocking operations and queue-management semantics.

The distinction is about behavior, not which type is more advanced. A deque is deliberately specialized around its boundaries.

Common pitfalls

Using list.pop(0) for a busy FIFO queue

Removing the first list element shifts the remaining elements. A deque expresses the same FIFO operation with popleft() and avoids that O(n) movement.

Assuming every deque operation is O(1)

End operations are the strength of a deque. Searching and accessing the middle require traversal.

Forgetting that extendleft reverses input

extendleft([1, 2]) behaves like appendleft(1) followed by appendleft(2), leaving 2 before 1.

Losing data unexpectedly with maxlen

A full bounded deque evicts from the opposite end when new items are appended. That is useful only when automatic loss of the oldest or opposite-end data is intentional.

Treating thread-safe end operations as a complete concurrency design

Individual supported operations do not make a multi-step workflow atomic. Use synchronization or queue.Queue when correctness depends on coordination across operations.

Choosing deque for random access

Although indexing is supported, middle access is not the deque’s optimized use case. Prefer a list when frequent arbitrary indexing dominates.

Make the ends part of the design

A deque works best when the meaning of its left and right boundaries is explicit. In a FIFO queue, the left side is the oldest work and the right side receives new work. In a recent-history buffer, the left side is the next value to expire. In a round-robin collection, rotation moves the logical current item while retaining the same elements.

Those simple invariants make code easier to reason about than treating a deque as a generic list substitute.

Use collections.deque when your access pattern is genuinely double-ended. Its combination of fast boundary operations, optional bounded length, and rotation provides a small set of tools that cover queues, recent-history windows, and many streaming algorithms without unnecessary data movement.