collections.deque — Use collections.deque as a queue (append/popleft) (intro-to-standard) - Python

SECTION 1

Historical Context & Motivation

Imagine you are standing in a lunch line at school. The first person who arrives is the first person served, and new people join at the back. This everyday pattern is exactly what computer scientists call a queue — a data structure that follows First-In, First-Out (FIFO) ordering. Queues have been a fundamental concept in computing since the earliest days of operating systems, where processes waited in line for CPU time.

In Python, you might be tempted to use a regular list as a queue, but there is a critical problem: removing an element from the front of a list with list.pop(0) forces Python to shift every remaining element one position to the left. For a list with a million items, that means a million moves for a single removal. The collections.deque class was created to solve exactly this performance bottleneck.

1960s • Queue Data Structure Formalized

Computer scientists formally defined the queue abstract data type as part of early operating system research, using it for task scheduling and buffer management.

1991 • Python 1.0 Released

Guido van Rossum released Python with built-in lists. Lists supported append and pop but lacked an efficient way to remove elements from the front.

2004 • collections.deque Added (Python 2.4)

Raymond Hettinger introduced deque (double-ended queue) to the collections module, giving Python developers O(1) append and pop operations on both ends.

2009 • maxlen Parameter Introduced

Python 2.6 added the maxlen parameter, enabling bounded deques that automatically discard items from the opposite end when full — perfect for sliding-window algorithms.

The key question that drove the creation of deque was simple: How can we add and remove items from both ends of a sequence in constant time? The answer lies in a clever implementation using a doubly-linked list of fixed-size blocks, which we will explore in the next sections.

SECTION 2

Core Principles & Definitions

Before diving into code, let's nail down the core ideas that make collections.deque so useful. A deque (pronounced "deck") stands for double-ended queue. Unlike a regular queue that only allows adding at the back and removing from the front, a deque supports efficient operations on both ends. However, in this lesson we focus on using it as a standard FIFO queue: append() to add at the right and popleft() to remove from the left.

FIFO Ordering

Elements leave in the same order they arrive. The first item you append() is the first item returned by popleft().

O(1) Both Ends

Both append() and popleft() run in constant time — the speed does not depend on how many items are stored.

Thread-Safe Operations

In CPython, deque's append() and popleft() are atomic, meaning they are safe to use in multithreaded programs without extra locking.

Optional Bounded Size

Pass maxlen=N to limit the deque to N items. When full, adding an item on one end automatically discards an item from the other.

✦

KEY TAKEAWAY

Think of a deque as a tube of tennis balls. You can push a ball in from either end, and you can pop a ball out from either end — both actions are instant. A regular Python list is more like a stack of books on a table: adding on top is easy, but pulling one from the bottom means lifting everything above it first.

SECTION 3

Visual Explanation — How a Deque Queue Works

This diagram shows three steps of queue operation. In Step 1, three items are appended from the right. In Step 2, popleft() removes 'A' from the front. In Step 3, a new item 'D' enters at the back via append(). Notice how the queue maintains FIFO order throughout.

The diagram above illustrates the fundamental rhythm of a queue: items flow in one direction, entering at the back and exiting at the front. With collections.deque, both of these operations — append() and popleft() — happen in O(1) constant time, regardless of how many elements are stored. This is the key advantage over using a plain Python list.

SECTION 4

How It Works — Performance Under the Hood

To understand why deque is faster than a list for queue operations, you need to know how each stores data in memory. A Python list uses a contiguous array — all elements sit next to each other in a single block of memory. This makes index access fast (O(1)), but inserting or removing at the front requires shifting every subsequent element. A deque, on the other hand, uses a doubly-linked list of fixed-size blocks. Each block holds up to 64 item references, and blocks are chained together. Adding or removing from either end only touches the first or last block.

LIST POP(0) TIME COMPLEXITY

T(list.pop(0)) = O(n)

Where n is the number of elements in the list. Every element after index 0 must shift left by one position.

DEQUE POPLEFT TIME COMPLEXITY

T(deque.popleft()) = O(1)

Constant time — only the pointer to the front element is updated. No elements are shifted, no matter how large the deque.

DEQUE APPEND TIME COMPLEXITY

T(deque.append(x)) = O(1) amortized

Adding to the right end is constant time on average. Occasionally a new block must be allocated, but this is rare and averages out.

⚠

Why Not Use a List?

If your queue processes 100,000 items, using list.pop(0) instead of deque.popleft() can result in roughly 5 billion extra element shifts over the lifetime of the queue. That is the difference between a program that runs in milliseconds and one that takes minutes.

SECTION 5

Key Methods & Usage Patterns

While our focus is on using deque as a FIFO queue with append() and popleft(), it helps to see the full picture. The table below lists the most important deque methods, grouped by their role. The methods highlighted in amber are the two you will use most often for queue behavior.

Method	Description	Time Complexity
`append(x)`	Add x to the right end (back of queue)	O(1)
`popleft()`	Remove and return from the left end (front of queue)	O(1)
`appendleft(x)`	Add x to the left end	O(1)
`pop()`	Remove and return from the right end	O(1)
`len(d)`	Return number of elements	O(1)
`d[i]`	Access element at index i	O(n)
`rotate(k)`	Rotate all elements k steps to the right	O(k)

Common deque methods and their time complexities

This chart compares the total time to dequeue all items. The red curve (list.pop(0)) grows quadratically — O(n²) total — while the green line (deque.popleft()) stays nearly flat because each individual removal is O(1).

💡

Trade-Off Alert

Notice that d[i] (random index access) is O(n) for deque but O(1) for a list. If you frequently need to access items by index in the middle, a list may be the better choice. Use deque when your primary operations are adding and removing from the ends.

SECTION 6

Worked Example — Print Job Queue

Let's build a simple print job queue. A school computer lab has one printer shared by many students. Print jobs arrive in order and must be processed first-come, first-served. We will use collections.deque to manage this queue and track which jobs are completed.

Print Job Queue Simulation

1
Step 1 — Import and Create the Deque

First, import deque from the collections module, then create an empty deque to serve as our print queue. from collections import deque print_queue = deque()

An empty deque is created: deque([])
2
Step 2 — Enqueue Print Jobs

Three students submit print jobs. We add each one to the back of the queue using append(). print_queue.append('Essay - Alice') print_queue.append('Lab Report - Bob') print_queue.append('Homework - Carol')

deque(['Essay - Alice', 'Lab Report - Bob', 'Homework - Carol'])
3
Step 3 — Process the First Job

The printer is ready. We dequeue the first job using popleft(), which removes and returns the item at the front. current_job = print_queue.popleft() print(f'Now printing: {current_job}')

Output: Now printing: Essay - Alice. The queue now contains: deque(['Lab Report - Bob', 'Homework - Carol'])
4
Step 4 — Add Another Job and Process Loop

A new job arrives while printing continues. We can enqueue it and then process all remaining jobs in a while loop. print_queue.append('Poster - Dave') while print_queue: job = print_queue.popleft() print(f'Now printing: {job}')

Output: Now printing: Lab Report - Bob Now printing: Homework - Carol Now printing: Poster - Dave
5
Step 5 — Check if Queue Is Empty

After all jobs are processed, we verify the queue is empty. An empty deque is falsy in Python, so we can use it directly in an if-statement. if not print_queue: print('All jobs complete!') print(len(print_queue)) # 0

Output: All jobs complete! and 0. The queue is empty and all jobs were processed in FIFO order.

SECTION 7

Deque vs. Other Queue Options in Python

Python offers several ways to implement queue behavior. Each has different strengths and is suited for different situations. The table below compares the most common options so you can make an informed choice.

Feature	list	collections.deque	queue.Queue
Enqueue speed	O(1) — append()	O(1) — append()	O(1) — put()
Dequeue speed	O(n) — pop(0)	O(1) — popleft()	O(1) — get()
Thread-safe	No	Partially (append/popleft)	Yes — full locking
Random access	O(1) — d[i]	O(n) — d[i]	Not supported
Best for	Stacks, index-heavy code	Fast queues, BFS, sliding windows	Multi-threaded producers/consumers

Comparison of Python queue implementations

🎯

WHEN TO CHOOSE DEQUE

Use collections.deque whenever you need a fast, lightweight queue in a single-threaded program. It is the standard recommendation from the Python documentation itself. Reserve queue.Queue for situations where multiple threads are producing and consuming data simultaneously. Avoid using a plain list as a queue — the O(n) cost of pop(0) can quietly destroy your program's performance.

SECTION 8

Connections to Advanced Topics

Mastering collections.deque as a queue is your gateway to several important algorithms and patterns in computer science. Understanding FIFO queues opens up a world of powerful techniques that you'll encounter in more advanced CS courses.

This Lesson (Intro)	Advanced Application
Basic FIFO queue with append/popleft	Breadth-First Search (BFS) — Uses a deque to explore graph nodes level by level
Bounded deque with maxlen	Sliding window algorithms — Track the last N values in streaming data (e.g., moving averages)
Using deque as both stack and queue	Deque-based monotonic queue — Solves min/max sliding window problems in O(n)
Single-threaded queue	asyncio task scheduling — Coroutines use deque-like structures internally for event loop management

From basic queues to advanced applications

The most immediately useful next step is learning Breadth-First Search (BFS). In BFS, you start at a node in a graph and explore all its neighbors before moving on to their neighbors. The queue ensures you process nodes in the order they were discovered — exactly the FIFO behavior you just learned. When you encounter BFS in a future course or coding interview, you will already have the fundamental tool in your toolkit: collections.deque.

SECTION 9

Practice Problems

Question 1: CONCEPTUAL

Explain in your own words why deque.popleft() is O(1) while list.pop(0) is O(n). What is happening in memory that causes the difference?

Show answer

A Python list stores elements in a contiguous block of memory. When you remove the first element with pop(0), every remaining element must be shifted one position to the left to fill the gap, which takes O(n) time. A deque uses a doubly-linked list of blocks, so removing from the front only requires updating a pointer to the next element — no shifting is needed. This pointer update takes the same amount of time regardless of how many elements are stored, making it O(1).

Question 2: BASIC CALCULATION

What is the output of the following code?

from collections import deque

q = deque([10, 20, 30])
q.append(40)
first = q.popleft()
q.append(50)
second = q.popleft()
print(first, second, list(q))

Show answer

The output is 10 20 [30, 40, 50]. The deque starts as [10, 20, 30]. After append(40) it becomes [10, 20, 30, 40]. The first popleft() removes and returns 10. After append(50) the deque is [20, 30, 40, 50]. The second popleft() removes and returns 20, leaving [30, 40, 50].

Question 3: INTERMEDIATE

Write a function hot_potato(names, num) that simulates a hot potato game. The function takes a list of player names and a number. It repeatedly moves the front person to the back of the queue num times, then eliminates the person at the front. It continues until one player remains and returns that player's name. Use a deque.

Show answer

Here is one solution:

from collections import deque

def hot_potato(names, num):
    q = deque(names)
    while len(q) > 1:
        for _ in range(num):
            q.append(q.popleft())
        q.popleft()  # eliminate
    return q[0]

The key insight is that rotating the queue simulates passing the potato: q.append(q.popleft()) moves the front person to the back. After num passes, the person now at the front is eliminated with another popleft(). This repeats until only one player remains.

Question 4: APPLIED

A web server receives requests and processes them one at a time. Write a class RequestQueue with three methods: add_request(url) to enqueue a URL, process_next() to dequeue and return the next URL (or None if empty), and pending() to return the count of waiting requests. Use collections.deque internally.

Show answer

from collections import deque

class RequestQueue:
    def __init__(self):
        self._queue = deque()

    def add_request(self, url):
        self._queue.append(url)

    def process_next(self):
        if self._queue:
            return self._queue.popleft()
        return None

    def pending(self):
        return len(self._queue)

The class wraps a deque and exposes a clean interface. The process_next() method checks if the deque is non-empty before calling popleft() to avoid an IndexError on an empty deque. The pending() method uses len() which is O(1) for deques. This pattern of encapsulating a deque inside a class is common in real-world Python applications.

Question 5: CRITICAL THINKING

Consider a bounded deque: d = deque(maxlen=3). If you call d.append(1); d.append(2); d.append(3); d.append(4), what does d contain? Explain how this behavior could be useful for implementing a "recent history" feature (like the last 3 pages visited in a browser). What would happen if you used popleft() on this bounded deque? Does the maxlen affect popleft behavior?

Show answer

After the four appends, d contains deque([2, 3, 4], maxlen=3). When the deque is full and you append a new item on the right, the oldest item on the left is automatically discarded to maintain the size limit. This makes bounded deques perfect for a "recent history" feature: you simply append() each new page URL and the deque automatically forgets pages beyond the last 3. No manual cleanup is needed. Calling popleft() on a bounded deque works normally — it removes and returns the leftmost element, and the deque shrinks. The maxlen only triggers automatic eviction when appending would exceed the limit, not during explicit removals.

SUMMARY

Lesson Summary

Summary

Python's collections.deque provides a high-performance double-ended queue that is the recommended way to implement FIFO queue behavior in Python. By using append() to enqueue items at the back and popleft() to dequeue items from the front, you get O(1) constant-time performance for both operations. This is a dramatic improvement over using list.pop(0), which requires O(n) time due to element shifting.

Key concepts to remember: import deque with from collections import deque; use maxlen for bounded queues that auto-discard old items; check for emptiness with if not q or len(q); and be aware that random index access is O(n) — a trade-off for the fast end operations. Mastering deque prepares you for important algorithms like Breadth-First Search and sliding window techniques.