Implementing a Queue in Python

A queue is a linear data structure that processes items in First-In, First-Out (FIFO) order: whichever item was added first is the first one removed, just like a line of customers waiting to check out at a store. Queues show up everywhere in real software — task schedulers, print spoolers, message brokers, and breadth-first search all rely on the same enqueue-at-the-back, dequeue-from-the-front behavior. Python has no dedicated queue keyword, so knowing how to build one correctly, and which building block to reach for, is a core skill. This lesson implements a queue two different ways, explains why one is dramatically faster than the other, and wraps the fast version in a clean, reusable class.

Overview: How Queues Work

A queue exposes two core operations. Enqueue adds a new item to the back of the queue. Dequeue removes and returns the item at the front of the queue — the one that has been waiting the longest. This is the opposite discipline of a stack, which is Last-In, First-Out (LIFO): a stack pops whatever was pushed most recently, while a queue always serves whoever arrived first. Most queue implementations also support peek (look at the front item without removing it) and is_empty (check whether there is anything to serve).

The interesting design question is: what should hold the items underneath? Python’s built-in list is a dynamic array — a contiguous block of memory. Appending to the end of a list is O(1) amortized because there is usually spare capacity at the end. But removing from the front of a list, with list.pop(0), forces Python to shift every remaining element one slot to the left to close the gap. For a queue with n items, that shift is O(n) work, every single time you dequeue.

The fix is collections.deque (short for "double-ended queue"), which is implemented internally as a doubly linked list of fixed-size blocks rather than one contiguous array. That structure lets Python add or remove items from either end — append/appendleft and pop/popleft — in O(1) time, because no shifting is ever required; only a handful of pointers change. This is exactly why the standard library recommends deque for queue behavior instead of a plain list, and it’s why this lesson builds both versions: seeing the slow one makes the fast one make sense.

Time and Space Complexity

The table below compares a naive list-backed queue against a deque-backed queue. n is the number of items currently in the queue.

Operation List-backed (list.pop(0)) Deque-backed (deque)
enqueue (add to back) O(1) amortized O(1)
dequeue (remove from front) O(n) O(1)
peek (front item) O(1) O(1)
is_empty O(1) O(1)
Space O(n) O(n)

The list-backed dequeue cost is O(n) because every element after index 0 must be copied one position left when the front element is removed — there is no way around it with a plain array-backed list. The deque-backed dequeue is O(1) because popleft only has to detach the first block and update a couple of internal pointers; nothing else in the structure moves. Space is O(n) for both, since either way you’re storing n references to items, just with different overhead per node for the deque’s linked blocks.

Examples

Example 1: A naive queue backed by a list

This version is easy to write and works correctly, but it hides a performance trap: dequeue calls self.items.pop(0), which is O(n).

class ListQueue:
    def __init__(self) -> None:
        self.items: list[int] = []

    def enqueue(self, value: int) -> None:
        self.items.append(value)

    def dequeue(self) -> int:
        if not self.items:
            raise IndexError("dequeue from empty queue")
        return self.items.pop(0)

    def is_empty(self) -> bool:
        return len(self.items) == 0

    def __len__(self) -> int:
        return len(self.items)


def main() -> None:
    queue = ListQueue()
    queue.enqueue(10)
    queue.enqueue(20)
    queue.enqueue(30)
    print("Queue size:", len(queue))
    print("Dequeued:", queue.dequeue())
    print("Dequeued:", queue.dequeue())
    print("Queue size:", len(queue))


main()

Output:

Queue size: 3
Dequeued: 10
Dequeued: 20
Queue size: 1

Three items are enqueued, making self.items equal to [10, 20, 30]. Each dequeue() call removes index 0: first 10 comes out, leaving [20, 30], then 20 comes out, leaving [30]. The FIFO order (10 before 20) is correct — the only problem is that this correctness comes at O(n) cost per dequeue, which would slow down badly if the queue held thousands of items and was drained repeatedly.

Example 2: An efficient queue using collections.deque

Swapping the list for a deque and pop(0) for popleft() keeps the same FIFO behavior but makes every operation O(1).

from collections import deque


def process_orders(order_ids: list[int]) -> list[int]:
    queue: deque[int] = deque()
    processed: list[int] = []

    for order_id in order_ids:
        queue.append(order_id)

    while queue:
        current = queue.popleft()
        processed.append(current)

    return processed


def main() -> None:
    incoming_orders = [101, 102, 103, 104]
    result = process_orders(incoming_orders)
    print("Processed in order:", result)


main()

Output:

Processed in order: [101, 102, 103, 104]

All four order IDs are pushed onto the back of the deque with append, giving deque([101, 102, 103, 104]). The while queue: loop then repeatedly calls popleft(), which always removes the current front element. Because items are removed in the exact order they were added, the processed list ends up identical to the input order — that’s FIFO in action, and each popleft() call did O(1) work instead of shifting the rest of the collection.

Example 3: Wrapping deque in a reusable Queue class

In real code you rarely want callers touching a raw deque directly. Wrapping it in a small class gives you a clean interface (enqueue, dequeue, peek, is_empty) while keeping deque’s O(1) guarantees underneath.

from collections import deque


class Queue:
    def __init__(self) -> None:
        self._items: deque[str] = deque()

    def enqueue(self, value: str) -> None:
        self._items.append(value)

    def dequeue(self) -> str:
        if self.is_empty():
            raise IndexError("dequeue from empty queue")
        return self._items.popleft()

    def peek(self) -> str:
        if self.is_empty():
            raise IndexError("peek from empty queue")
        return self._items[0]

    def is_empty(self) -> bool:
        return len(self._items) == 0

    def __len__(self) -> int:
        return len(self._items)


def main() -> None:
    print_queue = Queue()
    print_queue.enqueue("resume.pdf")
    print_queue.enqueue("invoice.pdf")
    print_queue.enqueue("report.pdf")

    print("Next up:", print_queue.peek())

    while not print_queue.is_empty():
        job = print_queue.dequeue()
        print("Printing:", job)

    print("Jobs remaining:", len(print_queue))


main()

Output:

Next up: resume.pdf
Printing: resume.pdf
Printing: invoice.pdf
Printing: report.pdf
Jobs remaining: 0

Three filenames are enqueued in order, so the front of the queue is resume.pdf and peek() correctly reports it without removing it. The while-loop then drains the queue with dequeue(), printing each job in the exact order it was submitted: resume, then invoice, then report. After the loop, is_empty() is true and the length is 0.

How It Works Step by Step

Trace a sequence of operations on an initially empty deque-backed queue, tracking the front-to-back contents after each step:

Step Operation Queue (front → back) Returned value
1 enqueue(4) [4] —
2 enqueue(9) [4, 9] —
3 enqueue(2) [4, 9, 2] —
4 dequeue() [9, 2] 4
5 enqueue(7) [9, 2, 7] —
6 dequeue() [2, 7] 9
7 peek() [2, 7] 2

Notice that enqueue always adds at the right-hand end (the back) and never disturbs existing items, so it’s O(1) regardless of queue size. dequeue always removes from the left-hand end (the front), returning the oldest surviving value each time — step 4 returns 4 (the very first item enqueued), and step 6 returns 9 (the next-oldest), which is exactly the FIFO guarantee. peek in step 7 reads the front value (2) without changing the queue at all.

Common Mistakes

Mistake 1: Calling pop() instead of popleft() on a deque

deque supports operations at both ends, which means it’s easy to accidentally use the stack-style method and silently turn a queue into a stack.

from collections import deque

queue = deque()
queue.append("first")
queue.append("second")
queue.append("third")

print(queue.pop())  # WRONG: pop() removes from the right end, breaking FIFO order

This prints third — the most recently added item — because pop() removes from the back, giving LIFO behavior instead of FIFO. For a print queue or task scheduler, this means the newest job would jump ahead of everyone who was already waiting.

The fix is to always dequeue from the front with popleft():

from collections import deque

queue = deque()
queue.append("first")
queue.append("second")
queue.append("third")

print(queue.popleft())  # correct: popleft() removes from the front (FIFO)

Output:

first

Now the item that was enqueued first ("first") is the one returned, which is the FIFO contract a queue is supposed to honor.

Mistake 2: Dequeuing without checking for an empty queue

Calling popleft() on an empty deque doesn’t return None or wait — it raises immediately, which crashes an unguarded program.

from collections import deque

queue: deque[int] = deque()
print(queue.popleft())

Since the deque is empty, this raises IndexError: pop from an empty deque instead of printing anything. Any consumer loop that doesn’t check for emptiness first will crash the moment the queue runs dry.

Guard the call by checking truthiness (an empty deque is falsy) before dequeuing:

from collections import deque


def safe_dequeue(queue: deque[int]) -> int | None:
    if not queue:
        return None
    return queue.popleft()


def main() -> None:
    queue: deque[int] = deque()
    result = safe_dequeue(queue)
    print("Result:", result)

    queue.append(42)
    result = safe_dequeue(queue)
    print("Result:", result)


main()

Output:

Result: None
Result: 42

The first call finds an empty deque and returns None instead of raising. After appending 42, the second call finds a non-empty deque and safely returns the front value.

Best Practices

  • Default to collections.deque for any FIFO queue in single-threaded code — never use a plain list with pop(0), since that turns every dequeue into an O(n) operation.
  • If multiple threads will enqueue and dequeue concurrently, use queue.Queue from the standard library instead of a bare deque; it adds locking and blocking behavior that plain deque does not provide.
  • Always check is_empty() (or the deque’s truthiness) before dequeuing, or wrap the call in a try/except IndexError, so an empty queue doesn’t crash the program.
  • Wrap the raw deque in a small class (enqueue/dequeue/peek/is_empty) when a queue is a core part of your design — it keeps call sites readable and prevents callers from misusing pop() on the wrong end.
  • Don’t use deque for frequent random access by index; indexing into the middle of a deque is O(n), unlike a list. If you need both fast random access and fast end-operations, reconsider your data structure.
  • Use deque(maxlen=n) when you want a fixed-size, automatically-overwriting circular buffer (for example, tracking the last N events).

Practice Exercises

  1. Bounded queue: Using deque(maxlen=3), enqueue the numbers 1 through 5 one at a time, printing the queue’s contents after each insertion. Hint: once the deque is full, each new append automatically drops the oldest item from the front — after enqueuing all five numbers, the final contents should be [3, 4, 5].
  2. BFS with a queue: Given an adjacency list like {"A": ["B", "C"], "B": ["D"], "C": ["D"], "D": []}, use a deque and a visited set to print nodes in breadth-first order starting from "A". Hint: the expected visiting order is A, B, C, D.
  3. Queue via two stacks: Implement a FIFO queue using only two stacks (Python lists used with append/pop) — a classic interview question. Push new items onto an "in" stack; when dequeuing, if an "out" stack is empty, pour every item from "in" into "out" (reversing their order) before popping. Hint: each item moves between stacks at most twice, giving amortized O(1) dequeue.

Summary

  • A queue is a FIFO structure: enqueue adds to the back, dequeue removes from the front — the opposite discipline of a LIFO stack.
  • A list-backed queue is easy to write but has O(n) dequeue, because list.pop(0) must shift every remaining element left.
  • collections.deque gives O(1) append/appendleft and pop/popleft at both ends, because it’s backed by a doubly linked list of blocks rather than one contiguous array — this is the standard tool for queues in Python.
  • Space complexity for either implementation is O(n) for n stored items.
  • Always guard dequeue against an empty queue, and never use deque.pop() when you mean popleft() — that mistake silently turns a queue into a stack.
  • Wrap a raw deque in a small Queue class with enqueue, dequeue, peek, and is_empty for cleaner, safer call sites in real projects.