Queues & Deques

First-in, first-out, the fairness principle behind BFS and task scheduling

A queue is the line at a shop. You join at the back. You get served from the front. First to arrive is first to leave. That is the fair way, and it has a name: FIFO, first in, first out.
This is the exact opposite of a stack. A stack takes from the top (the newest); a queue takes from the front (the oldest). The toy below lets you feel both, side by side.

One more handy cousin: a deque (say "deck", short for double-ended queue). It lets you add or remove from both ends quickly. Python has one built in, collections.deque, and it is the tool you reach for whenever you need a fast queue.

Queue for BFS level-order traversalpython

from collections import deque

def level_order_print(graph, start):
    """Print all nodes level by level, classic BFS pattern."""
    visited = {start}
    queue = deque([start])

    while queue:
        node = queue.popleft()   # O(1), deque is O(1) for both ends
        print(node, end=' ')
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [], 'E': [], 'F': []
}
level_order_print(graph, 'A')  # → A B C D E F

Why not use a list as a queue? list.pop(0) is O(n), it shifts every element. deque.popleft() is O(1). For anything BFS-related, always use collections.deque.

🤔Quick Check

You're implementing a print job scheduler. Jobs should be processed in the order they arrive. Which structure?

🎯

Phase Complete!

Linear Structures

You've mastered arrays, two pointers, linked lists, stacks, and queues, the fundamental linear data structures. Ready to search and sort?

0/500

Practice Exercises

0/1 solved

Exercise 1 of 1medium

⏱ 00:00

Moving Average

Calculate the moving average of the last k elements as numbers stream in.
Expected output:1.01.52.02.5

solution.py

1 / 1

Solve all 1 exercise to unlock completion

Previous Next