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: 1Three 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: 0Three 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 orderThis 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:
firstNow 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: 42The 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.dequefor any FIFO queue in single-threaded code — never use a plain list withpop(0), since that turns every dequeue into an O(n) operation. - If multiple threads will enqueue and dequeue concurrently, use
queue.Queuefrom the standard library instead of a baredeque; it adds locking and blocking behavior that plaindequedoes not provide. - Always check
is_empty()(or the deque’s truthiness) before dequeuing, or wrap the call in atry/except IndexError, so an empty queue doesn’t crash the program. - Wrap the raw
dequein 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 misusingpop()on the wrong end. - Don’t use
dequefor 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
- 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 newappendautomatically drops the oldest item from the front — after enqueuing all five numbers, the final contents should be[3, 4, 5]. - BFS with a queue: Given an adjacency list like
{"A": ["B", "C"], "B": ["D"], "C": ["D"], "D": []}, use adequeand avisitedset to print nodes in breadth-first order starting from"A". Hint: the expected visiting order isA, B, C, D. - 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:
enqueueadds to the back,dequeueremoves 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.dequegives O(1)append/appendleftandpop/popleftat 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 meanpopleft()— that mistake silently turns a queue into a stack. - Wrap a raw deque in a small
Queueclass withenqueue,dequeue,peek, andis_emptyfor cleaner, safer call sites in real projects.
