deque & Queues

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.

Choose the end that defines your queue

A help desk should serve the first request that arrived. Put arrivals on the right with append and take work from the left with popleft. Using pop instead silently changes the policy to newest first. Both operations are valid Python, so a queue-order bug will not necessarily produce an exception.

from collections import deque

arrivals = ["Asha", "Ben", "Cleo"]
waiting = deque(arrivals)
newest_first = deque(arrivals)
print("FIFO:", waiting.popleft())
print("LIFO:", newest_first.pop())
print("Still waiting:", list(waiting))

# ✅ Expected output:
# FIFO: Asha
# LIFO: Cleo
# Still waiting: ['Ben', 'Cleo']

Here the input list is a snapshot; constructing the deque gives it its own container. The names tell the story: FIFO is first in, first out; LIFO is last in, first out. A list is already a sensible stack when all additions and removals happen at its right end. Review ordinary list mutation in Lists and Collections.

from collections import deque

waiting = deque()
waiting.popleft()

# ✅ Expected error:
# IndexError: pop from an empty deque

An empty removal raises an error rather than returning None. In a single-threaded loop, while waiting: prevents that final removal. It does not coordinate competing workers; the blocking producer-and-consumer tools belong to Thread-Safe Queues (queue).

A bounded history discards data; a work queue usually must not

A history of the last three readings can forget earlier readings. Pending work cannot usually be forgotten just because four requests arrived. maxlen is therefore a retention rule, not a guarantee that every added item will eventually be processed. On an append to a full deque, an item leaves from the opposite end.

from collections import deque

recent = deque([10, 20, 30], maxlen=3)
recent.append(40)
print(list(recent))
recent.appendleft(5)
print(list(recent))
print("Limit:", recent.maxlen)

# ✅ Expected output:
# [20, 30, 40]
# [5, 20, 30]
# Limit: 3

After appending on the right, the leftmost value disappears. Appending on the left then discards the rightmost value. Nothing returns the discarded item for you. If it matters, read it before the operation or choose an unbounded deque and handle capacity explicitly. Inserting into the middle of a full bounded deque behaves differently:

from collections import deque

recent = deque([10, 20, 30], maxlen=3)
recent.insert(1, 15)

# ✅ Expected error:
# IndexError: deque already at its maximum size

This distinction matters when a program sometimes appends and sometimes inserts. A capacity error from insert is not evidence that append will refuse new data too. Keep the history policy visible where the deque is created.

Left extension and rotation change order in different ways

from collections import deque

first = deque(["C"])
first.extendleft(["A", "B"])
second = deque(["C"])
second.extendleft(reversed(["A", "B"]))
print(list(first))
print(list(second))

# ✅ Expected output:
# ['B', 'A', 'C']
# ['A', 'B', 'C']

extendleft inserts each supplied item at the left in turn: the later item ends up before the earlier one. Reverse the incoming sequence when its order should be preserved at the front. rotate instead moves existing items around the ends; it neither sorts nor reverses them.

from collections import deque

teams = deque(["red", "blue", "green"])
for turn in range(5):
    print(teams[0])
    teams.rotate(-1)
print("Next:", teams[0])

# ✅ Expected output:
# red
# blue
# green
# red
# blue
# Next: green

A negative rotation moves the front item to the back for this one-step case. Positive one-step rotation moves the last item to the front. The loop is bounded by five turns, not by deque truthiness: rotating never empties this roster. A while teams: loop with only rotations would therefore run indefinitely.

Fast ends do not mean fast arbitrary positions

Python documents roughly constant-time appends and pops at either end. Access near the middle slows to linear time, while list indexing stays constant time. Removing the front of a list shifts its remaining entries; a deque avoids that shift. These are growth-rate comparisons, not measured speedup promises for every small input.

from collections import deque

recent = deque([10, 20, 30, 40])
print(recent[1:3])

# ✅ Expected error:
# TypeError: sequence index must be integer, not 'slice'

For an occasional snapshot, convert to a list and slice that copy. Repeated arbitrary indexing or slicing is a reason to keep the data in a list in the first place. The syntax and boundary rules are covered by Slicing Lists & Strings.

Complete a queue that keeps a short audit history

Process all three requests in arrival order, while retaining only the last two completed names. Fill the import, removal method and history limit. Notice that only completed history is bounded.

from collections import ___

waiting = deque(["Asha", "Ben", "Cleo"])
completed = deque(maxlen=___)
while waiting:
    name = waiting.___()
    completed.append(name)
    print("Served:", name)
print("Recent:", list(completed))

# 👉 replace ___ with deque
# 👉 replace ___ with 2
# 👉 replace ___ with popleft

# ✅ Expected output:
# Served: Asha
# Served: Ben
# Served: Cleo
# Recent: ['Ben', 'Cleo']

Dispatch requests without confusing priority with recency

Start with normal requests A and B. Append normal request C, then place urgent request U at the front. Drain the queue in service order, recording only the last two completed requests. Print each served name and the final history. Use separate deques for pending work and completed history; the first must not discard requests.

from collections import deque

waiting = deque(["A", "B"])
history = deque(maxlen=2)
waiting.append("C")
waiting.appendleft("U")
while waiting:
    request = waiting.popleft()
    print("Serving:", request)
    history.append(request)
print("Completed recently:", list(history))

# ✅ Expected output:
# Serving: U
# Serving: A
# Serving: B
# Serving: C
# Completed recently: ['B', 'C']

The urgent request is explicitly moved ahead of the others. This is one queue policy, not a general priority scheduler. Multiple priority levels and tied priorities are the concern of Heaps with heapq (Priority Queues).

Practice quiz

What does this program print? from collections import deque d = deque(["A", "B"]) d.append("C") print(d.popleft(), d.pop())

  • C A
  • A B
  • A C
  • B C

Answer: A C. popleft removes A; pop then removes C from the opposite end.

What does this program print? from collections import deque d = deque([1, 2], maxlen=2) d.appendleft(0) print(list(d))

  • [0, 1]
  • [1, 2]
  • [0, 1, 2]
  • [0, 2]

Answer: [0, 1]. A full left append discards the rightmost value.

What does this program print? from collections import deque d = deque([3]) d.extendleft([1, 2]) print(list(d))

  • [1, 2, 3]
  • [3, 1, 2]
  • [3, 2, 1]
  • [2, 1, 3]

Answer: [2, 1, 3]. Each incoming item goes before the current front.

What does this program print? from collections import deque d = deque(["A", "B", "C"]) d.rotate(-1) print(list(d))

  • ['C', 'A', 'B']
  • ['B', 'C', 'A']
  • ['C', 'B', 'A']
  • ['A', 'B', 'C']

Answer: ['B', 'C', 'A']. One negative rotation takes the first item around to the end.

Which error ends this program? from collections import deque d = deque([1], maxlen=1) d.insert(0, 2)

  • IndexError: pop from an empty deque
  • TypeError: insertion is not supported
  • IndexError: deque already at its maximum size
  • ValueError: full queue

Answer: IndexError: deque already at its maximum size. insert raises instead of evicting when it would exceed maxlen.

Which job best fits an unbounded deque?

  • Repeated middle-index lookups
  • Sorted range searches
  • Keeping only the last five events
  • FIFO processing without dropping pending requests

Answer: FIFO processing without dropping pending requests. Append arrivals on one side and remove them from the other without maxlen eviction.

What does this program print? from collections import deque d = deque([1, 2]) while d: print(d.popleft()) print(len(d))

  • 1 2 0
  • 2 1 0
  • 1 2 2
  • IndexError: pop from an empty deque

Answer: 1 2 0. The truth test stops the single-threaded loop before another removal.

Why is while d: d.rotate(-1) unsuitable for draining a nonempty deque?

  • It sorts the data
  • Rotation keeps its length unchanged
  • A negative rotation is forbidden
  • Rotation copies the deque

Answer: Rotation keeps its length unchanged. A rotation changes positions, so the deque never becomes empty.

Continue this course

Related lessons