Introduction

deque (pronounced "deck", short for double-ended queue) is a list-like container from Python's built-in collections module, optimized for fast appends and pops from both ends. While a normal list is slow when you insert or remove at the front (an \(O(n)\) operation), a deque does it in \(O(1)\). This makes it the go-to structure for queues, stacks, breadth-first search, and sliding-window algorithms.

Real-World Analogy

Prerequisites

Getting Started

Create a deque from any iterable, then add and remove from either end.

from collections import deque

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

d.append(4)        # add to the right   -> deque([1, 2, 3, 4])
d.appendleft(0)    # add to the left    -> deque([0, 1, 2, 3, 4])

d.pop()            # remove from right  -> returns 4
d.popleft()        # remove from left   -> returns 0

print(d)           # deque([1, 2, 3])

Essential deque Methods

Rotating a deque

rotate(n) shifts elements to the right; a negative n shifts left.

from collections import deque

d = deque([1, 2, 3, 4, 5])

d.rotate(2)     # right by 2
print(d)        # deque([4, 5, 1, 2, 3])

d.rotate(-1)    # left by 1
print(d)        # deque([5, 1, 2, 3, 4])

Bounded deque with maxlen

A deque with maxlen automatically discards items from the opposite end when full — perfect for sliding windows and rolling logs.

from collections import deque

# Keep only the last 3 items
recent = deque(maxlen=3)

for i in range(6):
    recent.append(i)
    print(recent)

# deque([0], maxlen=3)
# deque([0, 1], maxlen=3)
# deque([0, 1, 2], maxlen=3)
# deque([1, 2, 3], maxlen=3)   <- 0 dropped
# deque([2, 3, 4], maxlen=3)
# deque([3, 4, 5], maxlen=3)

Using deque as a Queue (FIFO)

Add to the right, remove from the left — first in, first out.

from collections import deque

queue = deque()
queue.append("task1")     # enqueue
queue.append("task2")
queue.append("task3")

print(queue.popleft())    # task1  (dequeue)
print(queue.popleft())    # task2
print(queue)              # deque(['task3'])

Using deque as a Stack (LIFO)

Add and remove from the same (right) end — last in, first out.

from collections import deque

stack = deque()
stack.append("page1")     # push
stack.append("page2")
stack.append("page3")

print(stack.pop())        # page3  (pop)
print(stack.pop())        # page2
print(stack)              # deque(['page1'])

Real Example: Breadth-First Search

BFS is the classic deque application — a FIFO frontier of nodes to visit.

from collections import deque

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

def bfs(start):
    visited = []
    queue = deque([start])
    while queue:
        node = queue.popleft()      # FIFO
        if node not in visited:
            visited.append(node)
            queue.extend(graph[node])
    return visited

print(bfs("A"))   # ['A', 'B', 'C', 'D', 'E', 'F']

deque vs list Performance

Why Front Operations Are Fast

A list stores items in a contiguous array, so inserting at the front shifts all \(n\) elements — cost \(O(n)\). A deque is a doubly-linked structure of blocks, so end operations cost a constant:

\[ T_{\text{list front}} = O(n) \qquad\qquad T_{\text{deque front}} = O(1) \]

For workloads dominated by front insertions/removals, a deque is dramatically faster.

Best Practices

Common Mistakes

Interview Questions

Quick Revision