Queues
Implement FIFO queues with append() and popleft().
Python · Class
deque
collections.deque is a double-ended, list-like container with efficient appends and pops at either end. An optional maxlen bounds its size and automatically discards items from the opposite end when full.
How it works
collections.deque stores items in a double-ended queue. It supports efficient insertion and removal at either end, and an optional maxlen automatically bounds its size by discarding items from the opposite end when new items arrive.
Syntax
collections.deque([iterable[, maxlen]])Parameters
| Name | Type | Description |
|---|---|---|
iterable | iterable | Optional iterable whose items initialize the deque from left to right. |
maxlen | int or None | Optional maximum number of items; None leaves the deque unbounded. |
Returns
A new collections.deque object initialized from iterable, or empty when iterable is omitted.
Key points
- A deque can model either a stack or queue because items can be added and removed at both ends.
- End insertions and removals are designed to be thread-safe and memory-efficient.
- Appending or popping at the left or right end takes approximately constant time.
- Passing an iterable preserves its order while initializing the new deque.
- The class provides methods for mutation and access in addition to standard container behavior.
Common mistakes
- Without maxlen, a deque is unbounded; supply a maximum length when automatic size control is required.
Example: Bounded double-ended queue
from collections import deque
recent = deque(["a", "b"], maxlen=3)
recent.append("c")
recent.appendleft("start")
print(list(recent))
print(recent.pop())Creates a bounded deque, adds items at both ends, and removes the rightmost item.
When to use it
Stacks
Implement LIFO behavior with append() and pop().
Rolling buffers
Maintain the most recent fixed number of items using maxlen.
Interview questions
QWhy choose deque instead of list for queue operations?
deque is a list-like container designed for fast appends and pops on either end. These end operations have approximately O(1) performance in either direction, making it suitable for both stacks and queues.
Follow-up: How would you implement a fixed-size rolling buffer? Use deque(iterable, maxlen=n); once full, adding an item removes one from the opposite end.
QWhat arguments does collections.deque accept?
The constructor accepts an optional iterable and maxlen. Elements from the iterable initialize the deque from left to right, while maxlen limits its capacity when provided.
Follow-up: What happens when a bounded deque is full and you append? The item is added at the requested end and an equal number of items is discarded from the other end.
QWhich operations are central to using a deque?
A deque supports operations at both ends, including append and appendleft for insertion and pop and popleft for removal. It also supports common container behavior such as iteration and len().
Follow-up: Which operation removes from the left? popleft() removes and returns the leftmost element, raising IndexError if the deque is empty.
Related
collections.OrderedDictcollections.defaultdictcollections.Countercollections.ChainMap