Queue — First In, First Out

What is it? #

A queue adds at one end and removes from the other. The first item in is the first out — the opposite of a stack.

Two operations matter: enqueue (add at the back) and dequeue (remove from the front). Both should be O(1).

In Python, do not use a list for this. pop(0) shifts every remaining item, so draining a list of 100,000 jobs does billions of moves. collections.deque removes from either end in constant time.

Queues are how you process things fairly and in order, and they are the core of breadth-first search.

Think of it like this #

A queue at a ticket counter. Whoever arrived first is served first, and newcomers join the back. Nobody pushes in at the front, and that fairness is the entire point.

A stack, by contrast, is the pile of unread emails where you keep reading the newest one — the oldest never gets attention.

Simple example #

A background job system. Tasks arrive continuously and workers take the oldest waiting task. Order matters: a signup email sent before its account is created would be wrong.

Code #

from collections import deque

queue = deque()
queue.append("job-1")        # enqueue at the back
queue.append("job-2")
queue.append("job-3")

print(queue.popleft())       # dequeue from the front -> job-1
print(queue[0])              # peek at the front      -> job-2
print(len(queue))            # 2

# Why not a list?
# list.pop(0) is O(n): every remaining item shifts left
# deque.popleft() is O(1)

# A simple worker loop
def process_jobs(jobs):
    pending = deque(jobs)
    done = []
    while pending:
        job = pending.popleft()
        if job.get("retries", 0) > 0 and job["fails"]:
            job["retries"] -= 1
            pending.append(job)      # send it to the back, not the front
        else:
            done.append(job["id"])
    return done


# A fixed-size queue that drops the oldest automatically
recent_events = deque(maxlen=3)
for event in ["a", "b", "c", "d"]:
    recent_events.append(event)
print(list(recent_events))   # ['b', 'c', 'd']


# Queues drive breadth-first traversal
def level_order(tree_root, children_of):
    order, queue = [], deque([tree_root])
    while queue:
        node = queue.popleft()
        order.append(node)
        for child in children_of(node):
            queue.append(child)
    return order

Stack vs queue

                stack (LIFO)      queue (FIFO)
add             push to top       enqueue at back
remove          pop from top      dequeue from front
used for        undo, parsing     job processing, BFS
python          list              collections.deque

How it works #

deque is a double-ended queue. Internally it is a chain of small blocks, so adding or removing at either end never shifts a large array.

append puts an item at the back and popleft takes one from the front. Both are O(1), which is what makes a real job queue viable.

In process_jobs, a failed job that still has retries goes to the back of the queue with append. Putting it at the front would let one broken job block everything behind it — a real failure mode in production systems.

deque(maxlen=3) is a ring buffer. Once full, adding an item automatically drops the oldest. This is how you keep "the last N events" without any manual trimming.

level_order is breadth-first traversal: visit a node, add its children to the back, repeat. Because the queue is FIFO, everything at one depth is processed before anything deeper. Swap the deque for a stack and the same code becomes depth-first.

Real-world use #

Queues are the backbone of background processing. A web request enqueues a job — send an email, generate a PDF, resize an image — and returns immediately, while a worker picks it up. Systems like RabbitMQ, SQS and Redis-backed queues are this structure made durable across machines, covered in the System Design track.

Operating systems queue processes for the CPU and packets for the network card. Printers queue documents. Rate limiters queue or reject requests.

The fixed-size variant is used for recent-history displays, rolling averages and log buffers.

The key production lesson is what happens when a queue grows faster than it drains. That backlog is the signal your workers cannot keep up, which is why queue depth is one of the first metrics worth monitoring.

Common mistakes #

• Using list.pop(0) as a dequeue, which is O(n) and gets slow fast.
• Re-queuing a failing job at the front, letting it block everything else.
• Never monitoring queue depth, so a growing backlog goes unnoticed until timeouts start.
• Assuming a queue guarantees exactly-once processing. Most real systems deliver at least once, so jobs must be idempotent.
• Using a queue when order does not matter and a simple set of parallel tasks would do.

Practice #

Simulate a support desk: enqueue five tickets, process them in order, and re-queue any ticket marked "needs info" at the back with one fewer retry. Then use deque(maxlen=5) to keep the last five processed ticket IDs and print them.