Python Deque: Fast Double-Ended Queues with collections.deque

Name

Soren Atelier

Updated on 2/10/2026

Using a Python list as a queue or stack seems natural -- until you start popping from the left side. Calling list.pop(0) is an O(n) operation because every remaining element must shift one position forward. In a loop that processes millions of items, this hidden cost turns a fast pipeline into a crawl. The same problem affects list.insert(0, x), which is also O(n). For any workload that touches both ends of a sequence, plain lists become a performance trap.

Python's collections.deque (double-ended queue, pronounced "deck") fixes this by providing O(1) append and pop operations from both ends. It is implemented as a doubly-linked list of fixed-length blocks, giving it constant-time performance at each end while still supporting indexed access. This guide covers everything you need to know about deque: creation, core operations, bounded queues, thread safety, and practical patterns.

Creating a Deque

from collections import deque
 
# From a list
d = deque([1, 2, 3, 4, 5])
print(d)  # deque([1, 2, 3, 4, 5])
 
# From a string
letters = deque("hello")
print(letters)  # deque(['h', 'e', 'l', 'l', 'o'])
 
# Empty deque
d = deque()
 
# With maxlen (bounded deque)
d = deque(maxlen=3)
d.append(1)
d.append(2)
d.append(3)
d.append(4)  # Adding to right drops leftmost item
print(d)  # deque([2, 3, 4], maxlen=3)

Core Operations

Deque provides symmetric operations for both ends of the sequence.

from collections import deque
 
d = deque([2, 3, 4])
 
# append and appendleft
d.append(5)        # Add to the right end
d.appendleft(1)    # Add to the left end
print(d)  # deque([1, 2, 3, 4, 5])
 
# pop and popleft
right = d.pop()       # Remove from right end
left = d.popleft()    # Remove from left end
print(right)  # 5
print(left)   # 1
 
# extend and extendleft
d = deque([3, 4, 5])
d.extend([6, 7, 8])        # Add multiple items to right
d.extendleft([2, 1, 0])    # Add to left (note: reversed order)
print(d)  # deque([0, 1, 2, 3, 4, 5, 6, 7, 8])

Note that extendleft processes items one at a time, inserting each at position 0. The resulting order is reversed compared to the input iterable.

Other Useful Methods

from collections import deque
 
d = deque([1, 2, 3, 2, 4, 2, 5])
 
print(d.count(2))   # 3
print(d.index(3))   # 2
d.remove(2)          # Remove first occurrence
d.insert(1, 99)      # Insert at position
d.reverse()          # Reverse in place
d.clear()            # Clear all items

Rotation with rotate()

The rotate() method rotates the deque n steps to the right. Negative n rotates to the left.

from collections import deque
 
d = deque([1, 2, 3, 4, 5])
 
d.rotate(2)    # Rotate 2 steps to the right
print(d)       # deque([4, 5, 1, 2, 3])
 
d.rotate(-3)   # Rotate 3 steps to the left
print(d)       # deque([2, 3, 4, 5, 1])

Bounded Deques with maxlen

Bounded deques are one of the most practical features. By setting maxlen, you create a fixed-size buffer that automatically evicts the oldest items when capacity is reached.

Sliding Window / Moving Average

from collections import deque
 
def moving_average(data, window_size):
    """Calculate moving average using a bounded deque."""
    window = deque(maxlen=window_size)
    averages = []
    for value in data:
        window.append(value)
        if len(window) == window_size:
            averages.append(sum(window) / window_size)
    return averages
 
prices = [100, 102, 104, 103, 105, 107, 106, 108, 110, 109]
print(moving_average(prices, 3))
# [102.0, 103.0, 104.0, 105.0, 106.0, 107.0, 108.0, 109.0]

Tail of a File (Last N Lines)

from collections import deque
 
def tail(filename, n=10):
    """Return the last n lines of a file."""
    with open(filename) as f:
        return deque(f, maxlen=n)

This is remarkably efficient. The bounded deque reads through the entire file but only keeps the last n lines in memory.

Deque as a Queue (FIFO)

Use append() to enqueue and popleft() to dequeue:

from collections import deque
 
queue = deque()
queue.append("first")
queue.append("second")
queue.append("third")
 
print(queue.popleft())    # first
print(queue.popleft())    # second
print(queue.popleft())    # third

This is where deque truly shines over a list. With a list, list.pop(0) is O(n). With deque, popleft() is O(1).

Deque as a Stack (LIFO)

Use append() to push and pop() to pull from the same end:

from collections import deque
 
stack = deque()
stack.append("first")
stack.append("second")
stack.append("third")
 
print(stack.pop())    # third
print(stack.pop())    # second
print(stack.pop())    # first

Performance Comparison: Deque vs List

The takeaway: use deque when you need fast operations at both ends. Use list when you need fast random access by index.

Benchmark

from collections import deque
import time
 
def benchmark_left_operations(n):
    """Compare popleft/appendleft performance."""
    # List: pop from position 0
    data = list(range(n))
    start = time.perf_counter()
    while data:
        data.pop(0)
    list_time = time.perf_counter() - start
 
    # Deque: popleft
    data = deque(range(n))
    start = time.perf_counter()
    while data:
        data.popleft()
    deque_time = time.perf_counter() - start
 
    print(f"n={n:>8,}")
    print(f"  list.pop(0):     {list_time:.4f}s")
    print(f"  deque.popleft(): {deque_time:.4f}s")
    print(f"  Speedup: {list_time / deque_time:.1f}x")
 
benchmark_left_operations(100_000)

Thread Safety

Python's deque provides thread-safe append(), appendleft(), pop(), and popleft() operations. These methods are atomic in CPython because they execute within a single bytecode instruction, protected by the GIL.

For production systems that need blocking behavior (waiting for items), use queue.Queue instead, which wraps deque internally and adds proper locking and condition variables.

Practical Patterns

BFS Graph Traversal

from collections import deque
 
def bfs(graph, start):
    """Breadth-first search using deque as queue."""
    visited = set()
    queue = deque([start])
    order = []
    while queue:
        node = queue.popleft()
        if node not in visited:
            visited.add(node)
            order.append(node)
            queue.extend(
                neighbor for neighbor in graph[node]
                if neighbor not in visited
            )
    return order
 
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}
 
print(bfs(graph, 'A'))  # ['A', 'B', 'C', 'D', 'E', 'F']

Sliding Window Maximum

from collections import deque
 
def sliding_window_max(nums, k):
    """Find maximum in each sliding window of size k."""
    result = []
    window = deque()  # Stores indices of useful elements
    for i, num in enumerate(nums):
        while window and window[0] < i - k + 1:
            window.popleft()
        while window and nums[window[-1]] < num:
            window.pop()
        window.append(i)
        if i >= k - 1:
            result.append(nums[window[0]])
    return result
 
nums = [1, 3, -1, -3, 5, 3, 6, 7]
print(sliding_window_max(nums, 3))
# [3, 3, 5, 5, 6, 7]

Undo History

A bounded deque makes an excellent undo history that automatically forgets the oldest actions:

from collections import deque
 
class TextEditor:
    def __init__(self, max_undo=50):
        self.content = ""
        self._undo_stack = deque(maxlen=max_undo)
 
    def type_text(self, text):
        self._undo_stack.append(self.content)
        self.content += text
 
    def delete_last(self, n=1):
        self._undo_stack.append(self.content)
        self.content = self.content[:-n]
 
    def undo(self):
        if self._undo_stack:
            self.content = self._undo_stack.pop()
 
editor = TextEditor(max_undo=10)
editor.type_text("Hello")
editor.type_text(" World")
print(editor.content)   # Hello World
editor.undo()
print(editor.content)   # Hello

Testing Data Structure Performance in Jupyter

When benchmarking deques against lists or tuning maxlen for your specific workload, interactive notebooks are invaluable. RunCell (opens in a new tab) provides an AI-powered Jupyter environment where you can profile data structure operations, visualize performance differences, and get intelligent suggestions for optimization.

FAQ

What is a deque in Python?

A deque (double-ended queue) is a data structure from Python's collections module that supports O(1) append and pop operations from both ends. Unlike a list, which takes O(n) time to insert or remove from the front, a deque provides constant-time performance for operations at either end.

When should I use deque instead of list?

Use deque when you need fast insertion or removal at both ends of the sequence, such as implementing queues (FIFO), maintaining sliding windows, or doing BFS traversals. Stick with list when you need fast random access by index (O(1) for list vs O(n) for deque).

Is Python deque thread-safe?

Yes, the append(), appendleft(), pop(), and popleft() methods are thread-safe in CPython. These operations are atomic because they complete within a single bytecode instruction, protected by the GIL. However, compound operations are not atomic, so use queue.Queue for producer-consumer patterns that need blocking semantics.

What does maxlen do in deque?

The maxlen parameter creates a bounded deque with a fixed maximum size. When the deque is full and a new item is appended, the item on the opposite end is automatically discarded. This is useful for implementing rolling windows, recent activity logs, and undo histories.

How does deque compare to queue.Queue?

collections.deque is designed for speed. queue.Queue wraps a deque internally but adds thread synchronization primitives like locks and condition variables. Use deque for single-threaded code. Use queue.Queue when you need blocking get() and put() operations in multi-threaded producer-consumer scenarios.

Conclusion

Python's collections.deque is one of the most useful yet underappreciated data structures in the standard library. It eliminates the O(n) penalty of left-side list operations, provides built-in bounded buffering with maxlen, offers thread-safe atomic operations, and serves as the foundation for queues, stacks, sliding windows, and graph traversal algorithms.

The key decision is straightforward: if your code touches both ends of a sequence, use deque. If you need fast random access by index, use list. For most queue and stack patterns, deque should be your default choice.