Stacks & Queues4 min read

Queue

A line of people waiting — the first one in is the first one served

enqueue: \(O(1)\)dequeue: \(O(1)\)peek: \(O(1)\)search: \(O(n)\)space: \(O(n)\)

Imagine a line of people waiting to buy tickets. The person who joined the line first gets served first. Nobody cuts in front. Everyone waits their turn.

That's a queue. It follows one simple rule: First In, First Out — or FIFO for short.

Enqueue and Dequeue

There are two main moves:

Enqueue — join the back of the line (add to the rear)
Dequeue — serve the person at the front (remove from the front)

You can also peek — check who's at the front without serving them yet.

Where do queues appear?

Everywhere fair waiting is needed! Print jobs line up in a queue. Requests to a web server are queued. In algorithms, the famous BFS (Breadth-First Search) uses a queue to explore a graph level by level.

◈ Join the queue and get served!

← → arrow keys to step · click elements to interact

Queue Operations

from collections import deque

queue = deque()
queue.append(10)   # enqueue
queue.append(20)
queue.append(30)
print('Front:', queue[0])    # peek
print('Size:', len(queue))
val = queue.popleft()         # dequeue
print('Dequeued:', val)
print('Queue:', list(queue))

Output

Front: 10
Size: 3
Dequeued: 10
Queue: [20, 30]

Note: A queue is fair — whoever waited the longest is served first, just like in real life.

Why is enqueue and dequeue \(O(1)\)?

A queue tracks two pointers: the front and the back. Adding to the back takes one step. Removing from the front takes one step. No shifting needed. That's why both are instant. Under the hood, an efficient queue is often backed by a doubly linked list or a circular buffer.

Queues in BFS

In Breadth-First Search, you explore a graph in waves — all neighbors at distance 1 first, then distance 2, and so on. A queue makes this natural: enqueue neighbors you discover, dequeue the next node to explore. The order stays correct automatically.

Queue vs Stack

The key difference is order. A stack is LIFO — the newest item comes out first, like a pile of plates. A queue is FIFO — the oldest item comes out first, like a line of people. Both are useful depending on what order you need.

Complexity

EnqueueAdd to back in one step

Instant\(O(1)\)

DequeueRemove from front in one step

Instant\(O(1)\)

PeekCheck front without removing

Instant\(O(1)\)

SearchMust scan through all items

Slow\(O(n)\)

SpaceOne slot per item in line

Grows with n\(O(n)\)

BFS with a Queue

from collections import deque

def bfs(graph, start):
    visited = {start}
    queue = deque([start])
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for nb in graph[node]:
            if nb not in visited:
                visited.add(nb)
                queue.append(nb)
    return order

graph = {0: [1, 2], 1: [3], 2: [3], 3: []}
print(bfs(graph, 0))