Introduction
A deque (pronounced "deck", short for double-ended queue) is a linear data structure that allows insertion and removal from both ends efficiently. Unlike a stack (one open end) or a plain queue (insert at back, remove from front only), a deque generalizes both: it can behave as a stack, a queue, or something in between. This flexibility makes it useful for sliding-window algorithms, palindrome checking, and undo/redo systems that need access to both recent and oldest history.
Cricket analogy: A rain-delay substitutes bench where players can be added or pulled from either the front (next in) or back (last resort) generalizes a simple batting order (add only at the end); this flexibility is exactly what's needed for a fielding rotation that must react from both directions during a match.
Syntax
from collections import deque
d = deque()
# Insert at back / front
d.append(1) # back
d.appendleft(0) # front
# Remove from back / front
d.pop() # removes from back
d.popleft() # removes from front
# Peek without removing
front_val = d[0]
back_val = d[-1]
# Optional: bound the size, useful for sliding windows
bounded = deque(maxlen=3)Explanation
collections.deque is implemented internally as a doubly linked list of fixed-size blocks, which gives O(1) amortized time for append, appendleft, pop, and popleft — operations at either end never require shifting other elements, unlike a Python list. The optional maxlen parameter automatically discards elements from the opposite end once capacity is exceeded, which is perfect for maintaining a fixed-size sliding window. Because a deque supports both stack (LIFO via append/pop) and queue (FIFO via append/popleft) semantics, it is the general-purpose recommendation whenever you need efficient operations at both ends.
Cricket analogy: A team's rolling "last 6 balls" tracker built like a chain of small over-blocks lets the scorer add a new ball or drop the oldest one instantly from either end, and once it hits its 6-ball limit, the oldest ball automatically falls off — perfect for tracking the current over's run rate.
Example
from collections import deque
def sliding_window_maximum(nums: list, k: int) -> list:
"""Return the max of every window of size k using a monotonic deque."""
dq = deque() # stores indices, values decreasing front-to-back
result = []
for i, num in enumerate(nums):
# Remove indices outside the current window
while dq and dq[0] <= i - k:
dq.popleft()
# Remove smaller values from the back; they can never be the max
while dq and nums[dq[-1]] < num:
dq.pop()
dq.append(i)
if i >= k - 1:
result.append(nums[dq[0]])
return result
print(sliding_window_maximum([1, 3, -1, -3, 5, 3, 6, 7], 3))
# [3, 3, 5, 5, 6, 7]Complexity
All four core deque operations — append, appendleft, pop, popleft — run in O(1) amortized time. Random access by index (e.g., d[5]) is O(n) because deque is not backed by a contiguous array, unlike a list, so avoid it in tight loops. The sliding-window-maximum algorithm above runs in O(n) overall since each index is pushed and popped from the deque at most once.
Cricket analogy: Adding or removing a ball from either end of a rolling "last N balls" tracker is instant, but jumping straight to "the 4th-most-recent ball" is slow since the tracker isn't laid out like a numbered scorecard; computing the rolling highest score over a window still takes only one pass total since each ball enters and leaves the tracker once.
Key Takeaways
- A deque supports O(1) insertion and removal at both the front and the back.
- collections.deque is the standard Python implementation, backed by a doubly linked list of blocks.
- A deque can emulate a stack (append/pop) or a queue (append/popleft), making it a flexible default choice.
- deque(maxlen=k) auto-evicts from the opposite end, ideal for fixed-size sliding windows.
- Random index access on a deque is O(n), unlike O(1) for a list — avoid indexing deques in hot loops.
Practice what you learned
1. What distinguishes a deque from a standard queue?
2. Which Python method removes an element from the front of a collections.deque?
3. What happens when you append an element to a deque created with deque(maxlen=3) that already has 3 elements?
4. What is the time complexity of accessing an arbitrary element by index (e.g., d[5]) in a collections.deque?
Was this page helpful?
You May Also Like
Stacks
A LIFO data structure supporting O(1) push and pop, used for undo history, parsing, and recursion simulation.
Queues
A FIFO data structure supporting O(1) enqueue and dequeue, ideal for task scheduling and breadth-first traversal.
Circular Queues
A fixed-size queue that reuses freed slots by wrapping indices with the modulo operator, avoiding wasted space.