Python Queues

A queue is a data structure that stores items in the order they arrive and releases them in that same order — the first item added is the first one removed. This is called FIFO (First In, First Out), and it mirrors real life: the first person in line at a store is the first one served. Python doesn’t have a single built-in queue type the way it has list or dict; instead it offers several tools, each suited to a different situation, from simple in-memory FIFO buffers to thread-safe queues used to coordinate work between threads.

Overview: What Is a Queue and Why It Matters

Queues show up everywhere in programming: a printer processing print jobs in the order they were submitted, a web server handling incoming requests, a breadth-first search traversing a graph level by level, or a background worker pool processing tasks. The defining operations of a queue are enqueue (add an item to the back) and dequeue (remove an item from the front). Both operations should ideally run in constant time, O(1), regardless of how many items are already in the queue.

Python offers three main ways to build a queue, and choosing the right one matters for both correctness and performance:

  • collections.deque — a general-purpose, highly optimized double-ended queue implemented as a doubly linked list of fixed-size blocks. It supports O(1) appends and pops from both ends. This is the right choice for single-threaded FIFO or LIFO (stack) behavior.
  • queue.Queue (and its siblings LifoQueue and PriorityQueue) — thread-safe queues from the queue module, built internally on top of deque or heapq, but wrapped with locks and condition variables so multiple threads can safely put and get items without corrupting shared state. Use these for producer-consumer patterns with threads.
  • Plain list — technically usable as a queue with list.pop(0), but this is an anti-pattern you should avoid, explained under Common Mistakes below.

Internally, a Python list is a dynamic array: elements are stored contiguously in memory, so removing the first element means every remaining element has to shift one slot to the left — an O(n) operation. A deque, by contrast, is implemented so that both ends are equally cheap to touch, because it doesn’t need to shift a contiguous block; it just adjusts pointers to the next or previous linked block. That single implementation difference is why deque, not list, is the standard tool for queues in Python.

Syntax

The general shape of using a queue is the same regardless of which implementation you pick: create it, push items in, then pop items out in order.

from collections import deque

q = deque()            # create an empty deque
q.append(item)          # enqueue: add to the right (back)
q.popleft()              # dequeue: remove from the left (front)
q.appendleft(item)      # add to the front (used for stacks/deques)
q.pop()                  # remove from the right (used for stacks/deques)
len(q)                   # number of items currently queued
Type Import Thread-safe? Ordering
deque from collections import deque No (but append/pop are atomic under the GIL) FIFO or LIFO, your choice of end
queue.Queue import queue Yes FIFO
queue.LifoQueue import queue Yes LIFO (stack)
queue.PriorityQueue import queue Yes Smallest priority value first

Examples

Example 1: A Simple FIFO Queue with deque

This models a print queue where documents are printed in the order they were submitted.

from collections import deque

print_queue = deque()
print_queue.append("document1.pdf")
print_queue.append("document2.pdf")
print_queue.append("document3.pdf")

print(f"Queue: {list(print_queue)}")

while print_queue:
    current_job = print_queue.popleft()
    print(f"Printing: {current_job}")

print("All jobs printed.")

Output:

Queue: ['document1.pdf', 'document2.pdf', 'document3.pdf']
Printing: document1.pdf
Printing: document2.pdf
Printing: document3.pdf
All jobs printed.

Each append() call adds to the right side, and each popleft() call removes from the left side, so the very first document submitted is the very first one printed — classic FIFO behavior. The while print_queue: loop works because an empty deque is falsy, just like an empty list.

Example 2: A Thread-Safe Producer-Consumer Queue with queue.Queue

When multiple threads need to hand off work safely, queue.Queue is the right tool because its put() and get() methods use internal locking to prevent race conditions.

import queue
import threading
import time

def worker(q: queue.Queue, worker_id: int) -> None:
    while True:
        item = q.get()
        if item is None:
            q.task_done()
            break
        print(f"Worker {worker_id} processing task {item}")
        time.sleep(0.01)
        q.task_done()

def main() -> None:
    task_queue: queue.Queue = queue.Queue()

    thread = threading.Thread(target=worker, args=(task_queue, 1))
    thread.start()

    for task_id in range(1, 4):
        task_queue.put(task_id)

    task_queue.join()

    task_queue.put(None)
    thread.join()

    print("All tasks completed.")

main()

Output:

Worker 1 processing task 1
Worker 1 processing task 2
Worker 1 processing task 3
All tasks completed.

The main thread puts three tasks onto the queue, then calls task_queue.join(), which blocks until every item has been marked done with task_done(). The worker thread loops forever, pulling items with get() (which blocks if the queue is empty) and calling task_done() after each one. Sending None as a final “poison pill” is a common pattern for telling a worker thread to stop.

Example 3: Ordering Tasks by Priority

queue.PriorityQueue always returns the smallest item first, which is perfect for scheduling tasks that have different urgency levels.

import queue

priority_queue: queue.PriorityQueue = queue.PriorityQueue()

priority_queue.put((3, "Send weekly report"))
priority_queue.put((1, "Fix production outage"))
priority_queue.put((2, "Review pull request"))

while not priority_queue.empty():
    priority, task = priority_queue.get()
    print(f"Priority {priority}: {task}")

Output:

Priority 1: Fix production outage
Priority 2: Review pull request
Priority 3: Send weekly report

Each entry is a tuple of (priority_number, description). Python compares tuples element by element, so the queue orders entries by the first element (the priority number) regardless of the order they were inserted in. Lower numbers come out first, so a priority of 1 is treated as the most urgent.

Under the Hood

Understanding the internals helps you pick the right tool and avoid surprises:

  • deque is implemented in C as a doubly linked list of fixed-size blocks (not individual nodes per element, which would be slow). Because both ends of the structure are directly reachable, adding or removing from either end never requires shifting other elements, giving true O(1) performance at both ends. Random access to a middle index, however, is O(n) — this is the tradeoff versus a list.
  • queue.Queue wraps a deque internally and adds a threading.Lock plus condition variables (not_empty, not_full). When you call get() on an empty queue, the calling thread blocks on a condition variable instead of busy-waiting, and it’s woken up automatically the moment another thread calls put(). This is what makes it safe and efficient to coordinate threads.
  • queue.PriorityQueue stores items in a plain list but maintains the heap invariant using the heapq module, giving O(log n) insertion and removal while always keeping the smallest element accessible in O(1) at index 0.
  • queue.LifoQueue is the same locking machinery as Queue, but get() pops from the end of the internal list instead of the front, giving last-in-first-out (stack) behavior.

Common Mistakes

Mistake 1: Using a list as a queue with pop(0)

It’s tempting to reach for a plain list since it’s already familiar:

queue_list = []
queue_list.append("task1")
queue_list.append("task2")
first_task = queue_list.pop(0)  # O(n) — shifts every remaining element

Every call to pop(0) forces Python to shift all remaining elements one position to the left in memory, which is O(n). Do this repeatedly on a large queue and the whole operation degrades to O(n²). The fix is to use a deque, which pops from the left in O(1):

from collections import deque

queue_deque = deque()
queue_deque.append("task1")
queue_deque.append("task2")
first_task = queue_deque.popleft()  # O(1)

Mistake 2: Forgetting to call task_done()

When using queue.Queue with join() to wait for all work to finish, every successful get() must be paired with a task_done() call. If a worker forgets it, join() waits forever because the queue’s internal unfinished-task counter never reaches zero:

def broken_worker(q):
    while True:
        item = q.get()
        process(item)
        # missing q.task_done() -- q.join() will hang forever

Always call task_done() exactly once for every item retrieved with get(), typically in a try/finally block so it still runs if processing raises an exception.

Best Practices

  • Use collections.deque for single-threaded FIFO or LIFO logic — it’s faster and simpler than queue.Queue when you don’t need thread safety.
  • Use queue.Queue (or LifoQueue/PriorityQueue) whenever multiple threads produce or consume items concurrently.
  • Bound a queue with Queue(maxsize=N) when producers might outpace consumers, so put() blocks instead of letting memory grow without limit.
  • Always pair get() with task_done() when you plan to call join(), ideally inside try/finally.
  • Prefer a sentinel value like None, or queue.Empty handling with a timeout, to signal worker threads to shut down cleanly.
  • For CPU-bound work, remember the Global Interpreter Lock (GIL) means threads won’t give you true parallelism — consider multiprocessing.Queue instead for that case.
  • When items need custom priority ordering but aren’t naturally comparable, wrap them in a tuple like (priority, count, item) where count is a tie-breaking sequence number, avoiding comparison errors when two priorities are equal.

Practice Exercises

  • Exercise 1: Use a deque to simulate a customer service line. Enqueue five customer names, then dequeue and print them one at a time along with their position number (1st, 2nd, and so on).
  • Exercise 2: Write a function that uses collections.deque to check whether a string is a palindrome by comparing characters popped from both ends simultaneously until the deque has one or zero items left.
  • Exercise 3: Build a small task scheduler using queue.PriorityQueue that accepts tasks as (priority, task_name) tuples, where priority 1 is “urgent”, 2 is “normal”, and 3 is “low”. Print the tasks in the order they’d actually be worked on.

Summary

  • A queue follows FIFO ordering: the first item added is the first item removed.
  • collections.deque is the fastest choice for single-threaded FIFO or LIFO use, offering O(1) operations at both ends thanks to its doubly linked block structure.
  • queue.Queue, LifoQueue, and PriorityQueue from the queue module add thread-safe locking on top of similar underlying structures, making them the right choice for producer-consumer patterns across threads.
  • Avoid using a plain list with pop(0) as a queue — it’s O(n) per call and becomes a performance bottleneck as the queue grows.
  • Always match every get() with a task_done() when using join(), or your program can hang indefinitely.