Queues

Analogy categoryAnalogies

Introduction

A queue is a linear data structure that follows the First-In-First-Out (FIFO) principle: the earliest element added is the first one removed. Picture a line at a coffee shop — customers are served in the order they arrived. Queues model task scheduling, print spoolers, request handling, and are the core structure behind breadth-first search (BFS).

🏏

Cricket analogy: A queue is FIFO like the order in which net-bowlers line up for their turn at practice — whoever joined the net queue first bowls first — and this same ordering principle drives ball-by-ball match simulations that process deliveries breadth-first over by over.

Syntax

python

from collections import deque

# collections.deque is the recommended queue implementation in Python
queue = deque()

# Enqueue (add to the back)
queue.append("first")
queue.append("second")
queue.append("third")

# Dequeue (remove from the front)
front = queue.popleft()

# Peek at the front without removing
next_up = queue[0]

# Check if empty
is_empty = len(queue) == 0

Explanation

A plain Python list is a poor choice for a queue because removing from the front with pop(0) is O(n): every remaining element must shift left. collections.deque is implemented as a doubly linked list of fixed-size blocks, giving O(1) amortized time for appends and pops at BOTH ends (append/appendleft/pop/popleft). This makes deque the correct tool whenever FIFO or double-ended behavior is needed. For multi-threaded producer/consumer scenarios, queue.Queue provides the same FIFO semantics plus built-in locking.

🏏

Cricket analogy: Using a plain list as a queue is like making the front bowler in a long net-queue physically shuffle every other bowler forward each time someone bowls — O(n) — while a deque acts like a rotating net roster where both ends adjust in O(1); for a multi-ground scheduling system with several coaches assigning bowlers concurrently, a locking queue prevents two coaches from grabbing the same bowler.

Example

python

from collections import deque

def bfs(graph: dict, start: str) -> list:
    """Breadth-first traversal of a graph using a queue."""
    visited = {start}
    order = []
    queue = deque([start])

    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

    return order


graph = {"A": ["B", "C"], "B": ["D"], "C": ["D"], "D": []}
print(bfs(graph, "A"))  # ['A', 'B', 'C', 'D']

Complexity

With a deque-backed queue: enqueue (append) is O(1) amortized, dequeue (popleft) is O(1), and peek at the front is O(1). Space complexity is O(n) for n elements. Using a list instead would make dequeue O(n), so deque is the standard, interview-expected choice for FIFO structures in Python.

🏏

Cricket analogy: With a deque-backed net queue, adding a new bowler to the back is O(1) amortized, sending the front bowler in to bowl is O(1), and checking who's next is O(1); the queue takes O(n) space for n waiting bowlers, and using a plain list instead would make calling the next bowler an O(n) shuffle.

Key Takeaways

Queues follow FIFO: the first element enqueued is the first dequeued.
Use collections.deque with append()/popleft() for O(1) queue operations — a plain list's pop(0) is O(n).
Queues are the core structure behind breadth-first search (BFS) and task scheduling.
queue.Queue adds thread-safety for producer/consumer patterns.
Peeking at the front element is O(1) via deque[0].

Practice what you learned

1. Which principle defines a queue's behavior?

2. Why is collections.deque preferred over a plain list for implementing a queue in Python?

3. Which classic graph algorithm relies on a queue?

4. What is the time complexity of dequeue (popleft) using collections.deque?

Was this page helpful?

Stacks

Circular Queues

Topics covered

#Python#DataStructuresStudyNotes#DataStructures#Queues#Syntax#Explanation#Example#Complexity#StudyNotes#SkillVeris