Deque

Jr Codex DSA Notes

Level: Intermediate Prerequisites: Chapter 3 Time to complete: ~15 minutes

Table of Contents

1. What Is a Deque?
2. Deque Operations and Their Complexity
3. A Deque Generalizes Both Stack and Queue
4. Preview: Sliding Window Maximum
5. Summary & Next Steps

1. What Is a Deque?

A deque (pronounced "deck," short for double-ended queue) is a sequence that supports adding and removing elements from both ends efficiently. It's strictly more flexible than a stack (one active end) or a queue (add at one end, remove from the other) — a deque allows any combination of the two.

from collections import deque
 
dq = deque()
 
dq.append(1)        # add to the right:  deque([1])
dq.append(2)         # deque([1, 2])
dq.appendleft(0)      # add to the left:  deque([0, 1, 2])
 
dq.pop()               # remove from the right → 2, deque([0, 1])
dq.popleft()            # remove from the left  → 0, deque([1])

2. Deque Operations and Their Complexity

collections.deque is implemented as a doubly linked list of fixed-size blocks under the hood (doubly linked lists are covered fully in Module 6) — this is precisely what gives it O(1) performance at both ends, something a plain Python list cannot offer at its front:

That last row matters: a deque trades away fast random-access indexing (which a list has) in exchange for fast operations at both ends (which a list doesn't have at its front). Pick whichever structure matches how your code actually accesses the data.

3. A Deque Generalizes Both Stack and Queue

Using only append/pop (both on the right) reproduces a stack; using append/popleft reproduces a queue:

# Deque used as a stack (Chapter 1's LIFO behavior):
dq = deque()
dq.append(1); dq.append(2); dq.append(3)
dq.pop()          # 3 — last in, first out
 
# Deque used as a queue (Chapter 3's FIFO behavior):
dq = deque()
dq.append(1); dq.append(2); dq.append(3)
dq.popleft()      # 1 — first in, first out

In practice, most Python code uses deque directly instead of writing separate Stack/Queue wrapper classes, precisely because it already covers both cases with one structure.

4. Preview: Sliding Window Maximum

Deques become essential — not just convenient — for problems that need to efficiently track a maximum (or minimum) across a moving window, because you need to add new elements at one end while discarding stale ones from either end. A monotonic deque (one kept in strictly decreasing order from front to back) supports this in O(1) amortized per element, rather than the naive O(n) per window position you'd get by scanning the whole window each time.

# Conceptual sketch only — this is the classic "sliding window maximum"
# problem, revisited in full in Module 11's pattern cheat sheet:
#
# For each new element:
#   1. Remove elements from the BACK of the deque that are smaller than it
#      (they can never be the max again while this new, larger element is in play)
#   2. Add the new element to the back
#   3. Remove the FRONT of the deque if it has fallen outside the window
#   4. The current window's max is always the FRONT of the deque

You now have the vocabulary (deque, O(1) at both ends) to understand why this pattern works, even without solving it in full here — Module 11 revisits it as a named pattern once you've seen more of the problems it generalizes from.

5. Summary & Next Steps

Key Takeaways

• A deque supports O(1) add/remove at both ends, generalizing both the stack (Chapter 1) and the queue (Chapter 3) into one structure.
• The tradeoff for that flexibility: indexing into the middle of a deque is O(n), unlike a list's O(1) random access.
• collections.deque is Python's standard, idiomatic choice whenever a problem needs efficient operations at both ends — including monotonic-deque patterns like sliding window maximum.

Concept Check

1. What can a deque do that neither a stack nor a queue alone can?
2. Why is indexing into the middle of a deque O(n) rather than O(1), unlike a list?
3. In the sliding window maximum sketch, why is it safe to discard elements from the back of the deque that are smaller than the incoming element?

Next Chapter

→ Chapter 5: Practice Problems

Jr Codex — 1-on-1 Personalized Coaching | Back to Module Index