Queue

Prev Next

A queue is a linear data structure that follows the FIFO principle — First In, First Out. Whoever joined the line first gets served first; new arrivals go to the back. Print job spoolers, task scheduling, and breadth-first search all rely on exactly this "process things in arrival order" behavior. Queues need two different ends to be cheap at the same time — add at the back, remove from the front — and that's precisely where the stack lesson's advice stops working.

The Gotcha: A Plain List Makes a Bad Queue

In the previous lesson, a plain list was a perfectly good stack because both push and pop happened at the end, which is cheap. A queue needs to add at one end and remove from the other end. If you model that with list.append() to enqueue and list.pop(0) to dequeue, the append is still O(1) — but pop(0) removes the first element, which forces Python to shift every remaining element one slot to the left to close the gap. That's an O(n) operation, on every single dequeue.

queue = []
queue.append(1)
queue.append(2)
queue.append(3)

print(queue.pop(0))  # 1 -- correct FIFO result, but O(n): shifts 2 and 3 left

Time complexity: O(n) per pop(0) call — n-1 elements must shift left to fill the vacated slot. Space complexity: O(n) for the underlying list, unchanged by the shift.

Why this matters at scale: processing n items with pop(0) costs O(n) work per item, so the whole queue drains in O(n²) total instead of the O(n) you'd expect from a proper queue. On a queue of a few thousand items this is the difference between milliseconds and a visibly slow program.

The Fix: collections.deque

Python's collections.deque ("double-ended queue") is implemented as a doubly linked block structure specifically so that both ends are O(1) — appending or removing from the left is exactly as cheap as doing it on the right. It's the standard-library, production-grade way to build a queue in Python; reach for it any time you need to add or remove from either end efficiently.

from collections import deque

queue = deque()

queue.append(1)          # enqueue -- add to the back
queue.append(2)
queue.append(3)

print(queue.popleft())   # 1 -- dequeue: remove from the front, O(1)
print(queue.popleft())   # 2
print(queue[0])          # 3 -- peek at the front without removing
print(len(queue) == 0)  # False -- one element (3) remains

Time complexity: O(1) for append, popleft, indexing the front, and the emptiness check — deque tracks both ends directly with no shifting. Space complexity: O(n) for n stored elements, plus a modest per-block overhead from the underlying doubly linked block structure.

Wrapping It as a Queue Class

As with the stack, you rarely need a dedicated class just to use a deque as a queue, but wrapping it keeps the interface honest — nobody accidentally reaches for the wrong end.

from collections import deque

class Queue:
    def __init__(self):
        self._data = deque()

    def enqueue(self, value):
        self._data.append(value)

    def dequeue(self):
        if self.is_empty():
            raise IndexError("dequeue from an empty queue")
        return self._data.popleft()

    def peek(self):
        if self.is_empty():
            raise IndexError("peek at an empty queue")
        return self._data[0]

    def is_empty(self):
        return len(self._data) == 0

    def __len__(self):
        return len(self._data)

Time complexity: O(1) for enqueue, dequeue, peek, is_empty, and len — each delegates straight to deque's O(1) end operations. Space complexity: O(n) for n stored elements.

Also useful: queue.Queue from the standard library wraps a deque with locking for thread-safe producer/consumer use, and multiprocessing.Queue does the same across processes. For everyday single-threaded FIFO logic, though, a bare collections.deque is all you need.

Worked Problem: Implement a Queue Using Two Stacks

A frequent interview question deliberately ignores deque and asks you to build FIFO behavior out of two LIFO stacks (plain lists, pushing and popping only from the end). The trick: keep an in_stack for incoming elements and an out_stack for outgoing ones. Enqueue always pushes onto in_stack — O(1). Dequeue pops from out_stack; if that's empty, first dump the entire in_stack into it (which reverses the order back to FIFO) before popping.

class QueueFromStacks:
    def __init__(self):
        self.in_stack = []
        self.out_stack = []

    def enqueue(self, value):
        self.in_stack.append(value)                        # always O(1)

    def dequeue(self):
        if not self.out_stack:
            while self.in_stack:
                self.out_stack.append(self.in_stack.pop())  # reverse the order once
        if not self.out_stack:
            raise IndexError("dequeue from an empty queue")
        return self.out_stack.pop()


q = QueueFromStacks()
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
print(q.dequeue())   # 1 -- in_stack [1,2,3] dumped into out_stack as [3,2,1], pop gives 1
q.enqueue(4)
print(q.dequeue())   # 2 -- out_stack still has [3,2] left, no need to dump again

Trace: enqueue 1, 2, 3 leaves in_stack = [1, 2, 3], out_stack = []. First dequeue finds out_stack empty, so it dumps everything over, popping 3 then 2 then 1 off in_stack and pushing them onto out_stack, producing out_stack = [3, 2, 1] — then pops from the end, returning 1, exactly the FIFO order it went in. Enqueueing 4 afterward just appends to in_stack without disturbing out_stack, so the next dequeue can pop 2 straight off out_stack with no re-dump needed.

Time complexity: O(1) for enqueue always; dequeue is O(1) amortized — each element is moved from in_stack to out_stack at most once across its entire lifetime, even though any single dequeue call that triggers the dump costs O(n) in that moment. Space complexity: O(n) across both stacks for n stored elements.

Next up: now that stacks and queues are in hand, Linear & Binary Search moves from data structures to algorithms — starting with the two most fundamental ways to find a value in a list.

Prev Next