Queues & Deques

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

A queue is a FIFO (First In, First Out) data structure. Like a real queue, first person in line is first to be served.
A deque (double-ended queue) lets you add/remove from both ends in O(1). Python's collections.deque is the go-to implementation.

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