Deque
A deque (double-ended queue, pronounced "deck") from the collections module provides O(1) time appends and pops from both ends. from collections import deq...
What is a Deque?
A deque (double-ended queue, pronounced "deck") from the collections module provides O(1) time appends and pops from both ends. from collections import deque; d = deque([1, 2, 3]). Unlike a list where inserting at index 0 is O(n) (all elements shift), deque.appendleft() and deque.popleft() are O(1). This makes deque the ideal structure for implementing queues, breadth-first search, and sliding window algorithms.
Core Deque Operations
append(item) adds to the right. appendleft(item) adds to the left. pop() removes from the right. popleft() removes from the left. extend(iterable) adds multiple items to the right. extendleft(iterable) adds items to the left (in reversed order). rotate(n) rotates the deque: positive n moves n elements from the right to the left; negative n moves from the left to the right. rotate(1) on deque([1,2,3]) gives deque([3,1,2]).
Bounded Deque
Creating a deque with a maxlen argument makes it a bounded deque: d = deque(maxlen=3). When the deque is full and you append, the opposite end is automatically discarded. deque([1,2,3], maxlen=3); d.append(4) gives deque([2, 3, 4]) — element 1 was dropped. This is perfect for implementing a fixed-size sliding window or keeping track of the last N items (like recent search history or a log buffer) without manual size management.
Deque vs List for Queues
If you use a list as a queue by appending to the right and popping from the left with list.pop(0), each pop is O(n) because all remaining elements must shift. A deque.popleft() is O(1). For FIFO (first-in, first-out) queues, always use deque over list. For stacks (LIFO), lists work fine because append and pop from the right are both O(1). The choice between list and deque signals understanding of time complexity in data structure questions.
Deque in BFS
Breadth-first search requires a queue that efficiently dequeues from the front. from collections import deque; queue = deque([start_node]); while queue: node = queue.popleft(); process(node); for neighbor in graph[node]: if neighbor not in visited: visited.add(neighbor); queue.append(neighbor). Using deque.popleft() instead of list.pop(0) makes BFS O(V + E) rather than O(V^2 + E), a significant difference on large graphs.
Exam Tip
Common deque exam questions: what is the time complexity of appendleft() and popleft()? O(1). What happens when you append to a bounded deque that is full? The item on the opposite end is automatically removed. Is a deque indexable? Yes — d[0] and d[-1] work in O(1), and d[k] works in O(n). What module contains deque? collections. The most important thing to know: deque is the right choice whenever you need efficient operations on both ends of a sequence, particularly for implementing queues and sliding window problems.