deque & Queues

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.

Learn deque & Queues in our free Python course — an interactive lesson with runnable examples, a practice exercise and a quick reference.

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.

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):

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):

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() .

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:

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

❌ Indexing the middle of a deque in a tight loop

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

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.

🚀 Up next: Heaps with heapq — always pull out the smallest item in O(log n).

Practice quiz

Which collections type gives O(1) appends and pops at BOTH ends?

  • list
  • tuple
  • deque
  • set

Answer: deque. A deque (double-ended queue) is optimized so appendleft/popleft and append/pop are all O(1).

To use a deque as a FIFO queue, you append on the right and remove with which method?

  • popleft()
  • pop()
  • remove()
  • pop(0)

Answer: popleft(). FIFO means removing the oldest item: append() adds on the right and popleft() removes from the left in O(1).

After deque(maxlen=3) receives 10, 20, 30, 40, 50 via append(), what does list() show?

A maxlen deque drops the oldest item from the left each time it overflows, leaving the last three: 30, 40, 50.

Given d = deque([3]) then d.extendleft([1, 2]), what is d?

extendleft appends each item to the left one at a time, so the order is reversed: 2, 1, 3.

Why is deque.popleft() far faster than list.pop(0) for a large queue?

  • list.pop(0) is O(n) because every remaining element shifts down, while popleft() is O(1)
  • pop(0) is not allowed on lists
  • They are the same speed
  • deque uses less memory only

Answer: list.pop(0) is O(n) because every remaining element shifts down, while popleft() is O(1). Removing the first list element shifts all others down (O(n)); a deque's linked-block structure makes popleft O(1).

deque(['a','b','c','d']).rotate(1) produces which result?

  • b
  • c
  • d
  • a

Answer: d. rotate(1) shifts everything right by one, wrapping the last element to the front: d, a, b, c.

What does a negative argument to rotate(), like rotate(-2), do?

  • Raises an error
  • Rotates the elements to the left
  • Reverses the deque
  • Clears the deque

Answer: Rotates the elements to the left. A negative count rotates left; rotate(-2) moves each element two places toward the front, wrapping around.

When you append to a full maxlen deque, the dropped item is...

  • Returned to you
  • Saved to a backup list
  • Raised as an exception
  • Silently discarded with no error or warning

Answer: Silently discarded with no error or warning. maxlen silently drops the item at the opposite end; if you need it you must capture it before it falls off.

For repeatedly indexing the MIDDLE element in a tight loop, which is the better choice?

  • deque, it is O(1) in the middle
  • list, because indexing the middle of a deque is O(n)
  • Either, both are O(1)
  • set, for fast lookup

Answer: list, because indexing the middle of a deque is O(n). Deques are slow (O(n)) for middle access; a list gives O(1) random indexing anywhere.

In the palindrome checker, which pair of methods compares the two ends of the deque?

  • append() and pop()
  • appendleft() and append()
  • popleft() and pop()
  • rotate() and pop()

Answer: popleft() and pop(). popleft() takes the leftmost char and pop() the rightmost, so comparing them checks the outer pair each iteration.