deque & Queues

Reviewed & published by Brayan K

A deque (pronounced "deck") is a double-ended queue from the collections module that adds and removes items from both ends in fast O(1) time, making it the ideal tool for queues, stacks, sliding windows, and fixed-size history buffers.

Part of the free Python course at LearnCodingFast — hands-on lessons with examples you run in your browser, plus practice exercises and a quick quiz.

Lists are great, but removing from the front of a long list is painfully slow. A deque fixes that and unlocks elegant queue and buffer patterns.

What You'll Learn in This Lesson

• Creating a deque from collections
• Fast O(1) appendleft() and popleft()
• Using a deque as a FIFO queue
• Building a ring buffer with maxlen
• Rotating elements with rotate()
• When a list still beats a deque

1 Both Ends Are Fast

A deque gives you four push/pop methods: append and pop on the right (like a list), plus appendleft and popleft on the left. All four are O(1):

from collections import deque

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

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

print(d.pop())      # 4  (remove from the right)
print(d.popleft())  # 0  (remove from the left)
print(d)            # deque([1, 2, 3])

# extend works on both ends too
d.extendleft([0, -1])   # note: each item is pushed to the left
print(d)                # deque([-1, 0, 1, 2, 3])

from collections import deque

# A deque can act as a simple browser history
history = deque()
history.append("home")
history.append("about")
history.append("pricing")

# Go back: pop from the right
print("Now on:", history[-1])
history.pop()
print("Back to:", history[-1])

# ✅ Expected output:
# Now on: pricing
# Back to: about

2 A Proper FIFO Queue

A queue is "first in, first out": the first person in line is served first. With a deque you append new arrivals on the right and popleft the next to serve — both O(1):

from collections import deque

queue = deque()
queue.append("Ada")     # Ada joins the line
queue.append("Ben")
queue.append("Cleo")

# Serve in arrival order
print(queue.popleft())  # Ada
print(queue.popleft())  # Ben
print(queue)            # deque(['Cleo'])

# Why not a list? list.pop(0) is O(n):
# every remaining element shifts down — slow for big queues.
# deque.popleft() is O(1) no matter the size.

For a small list the difference is invisible, but a queue with hundreds of thousands of items processed in a loop can be hundreds of times slower with list.pop(0) than with deque.popleft().

3 Ring Buffers with maxlen & rotate()

Give a deque a maxlen and it becomes a fixed-size ring buffer: once full, every new item pushes the oldest one out automatically. And rotate(n) shifts every element n places, wrapping around:

from collections import deque

# Keep only the last 3 readings
recent = deque(maxlen=3)
for reading in [10, 20, 30, 40, 50]:
    recent.append(reading)
    print(list(recent))
# [10]
# [10, 20]
# [10, 20, 30]
# [20, 30, 40]   <- 10 fell off the left
# [30, 40, 50]   <- 20 fell off the left

# rotate(1) moves everything right by 1, wrapping the end to the front
letters = deque(["a", "b", "c", "d"])
letters.rotate(1)
print(letters)          # deque(['d', 'a', 'b', 'c'])
letters.rotate(-2)      # negative rotates left
print(letters)          # deque(['b', 'c', 'd', 'a'])

from collections import deque

# Rolling average of the last 3 temperatures
window = deque(maxlen=3)
temps = [20, 22, 24, 26, 28]

for t in temps:
    window.append(t)
    avg = sum(window) / len(window)
    print(f"After {t}: window={list(window)}, avg={avg:.1f}")

# ✅ Expected output:
# After 20: window=[20], avg=20.0
# After 22: window=[20, 22], avg=21.0
# After 24: window=[20, 22, 24], avg=22.0
# After 26: window=[22, 24, 26], avg=24.0
# After 28: window=[24, 26, 28], avg=26.0

🎯 Your Turn: Fill in the Blanks

Replace each ___ so the print jobs are processed in arrival order (FIFO).

# 🎯 YOUR TURN: process a print queue first-in-first-out
from collections import ___

jobs = deque()
jobs.append("report.pdf")
jobs.append("photo.png")
jobs.append("notes.txt")

while jobs:
    nxt = jobs.___()    # take the OLDEST job (left side)
    print("Printing:", nxt)

# Expected output:
# Printing: report.pdf
# Printing: photo.png
# Printing: notes.txt

Common Errors

❌ Using list.pop(0) for a big queue

q = list(range(1000000))
while q:
    q.pop(0)   # O(n) each time — extremely slow

✅ Use a deque for O(1) popleft

from collections import deque
q = deque(range(1000000))
while q:
    q.popleft()   # O(1) each time

❌ Indexing the middle of a deque in a tight loop

d[len(d) // 2]   # O(n) — deques are slow in the middle

✅ Use a list when you need random access

data = [...]      # lists give O(1) indexing anywhere

❌ Forgetting extendleft reverses order

d = deque([3])
d.extendleft([1, 2])
print(d)   # deque([2, 1, 3]) — not [1, 2, 3]!

✅ Reverse first, or append one by one

d = deque([3])
d.extendleft(reversed([1, 2]))
print(d)   # deque([1, 2, 3])

🎯 Mini Challenge: Palindrome Checker

A deque is perfect for checking palindromes: compare the two ends, then chop them off and repeat.

# 🎯 Mini Challenge: is the word a palindrome?
from collections import deque

def is_palindrome(word):
    d = deque(word)
    while len(d) > 1:
        if d.popleft() != d.pop():   # compare both ends
            return False
    return True

for w in ["racecar", "level", "python", "noon"]:
    print(w, "->", is_palindrome(w))

# Expected output:
# racecar -> True
# level -> True
# python -> False
# noon -> True

📚 Keep Learning

• Python docs: collections.deque
• Python docs: deque recipes (moving average, tail, and more)
• Python docs: queue module (thread-safe queues)

Frequently Asked Questions

Lesson complete — you wield queues like a pro!

You can build O(1) queues and stacks with append/popleft, keep a rolling window with maxlen, shift elements with rotate(), and you know exactly when a plain list is the better choice.

Practice quiz

Continue this course

• Previous: Counter & defaultdict
• Next: Heaps with heapq (Priority Queues) — Build priority queues and find top-k with the heapq module
• Quick reference: Python cheat sheet

Frequently asked questions

What is a deque and how do you say it?

A deque (pronounced 'deck') is a double-ended queue from the collections module. It behaves like a list but is optimized so that adding or removing items at BOTH ends is fast — O(1). It's the right tool for queues, sliding windows, and undo histories where you push and pop from either side.

Why is deque faster than a list for queues?

Removing the first element of a list with pop(0) is O(n) because every remaining element must shift down one slot. A deque uses a doubly-linked block structure, so popleft() and appendleft() are O(1) no matter how big it gets. For a queue with thousands of items, that's a massive difference.

What does maxlen do?

Passing maxlen turns a deque into a fixed-size ring buffer. Once it's full, every new item you append automatically drops the item at the opposite end. It's perfect for keeping 'the last N events', a rolling average window, or a recent-history list — you never have to trim it yourself.

Should I always use deque instead of a list?

No. A list is still better for random access by index and for general-purpose storage, and indexing the middle of a deque is O(n). Choose deque specifically when your hot path is adding or removing at the ends — queues, stacks used heavily, and sliding windows. Use a list for everything else.