Queue Applications

TL;DR

Queues excel at FIFO processing for level-order traversals, task scheduling, and sliding window problems. BFS uses queues to explore graphs layer-by-layer in O(V+E) time. Task scheduling leverages queue ordering for fair processing. Deques enable sliding window maximum problems by maintaining useful elements in decreasing order, achieving O(n) complexity. Understanding these applications transforms complex problems into elegant queue-based solutions.

Core Concepts

BFS and Level-Order Traversal

Breadth-first search explores nodes level-by-level, visiting all neighbors before descendants. Unlike depth-first search (which uses stacks), BFS uses queues to maintain FIFO order, guaranteeing shortest paths in unweighted graphs.

Level-order traversal applies BFS to trees, processing nodes by depth. Each complete iteration of the queue represents one level. This enables layer-wise operations like finding maximum per level, building level-sum arrays, or detecting structural properties.

Shortest path in unweighted graphs follows naturally from BFS properties: first discovery of a node represents shortest path. Distance equals depth in BFS tree from source.

Connected component detection repeatedly runs BFS from unvisited nodes, with each BFS run identifying one connected component. Time complexity is O(V+E).

Task Scheduling and Priority Processing

FIFO task scheduling processes tasks in arrival order using queues. Simple and fair, but ignores task characteristics like priority or duration.

Round-robin scheduling allocates fixed time slices to each task. When a task's time expires, it re-enters the queue for another slice. Deques support efficient append/remove-front operations needed for this.

Priority-based variants extend queues with priority comparisons, though priority queues (heaps) are better suited. Standard queues maintain order for fairness.

Starvation prevention requires careful queue management. In task scheduling, lower-priority tasks might never execute if higher-priority tasks continuously arrive. Queues help implement aging: priority increases with wait time.

Sliding Window Maximum

Sliding window problem maintains maximum element in a moving window of fixed size. Naive approach recalculates max each step: O(nk) time. Deques solve this in O(n).

Monotonic deque strategy maintains elements in decreasing order. New element compares to deque back: if smaller, append; if larger, remove back repeatedly until no larger exists. Front always holds maximum.

Index management prevents using outdated elements. Store indices in deque, check if front index is outside current window before using.

Generalizations extend to sliding window minimum (increasing order) and variants like kth element or sum range. Core principle remains: monotonic ordering enables O(1) queries.

Key Algorithms and Techniques

BFS Template

Explore graph level-by-level maintaining all frontier nodes in queue. Mark visited to avoid cycles.

Level-Order Tree Traversal

Process tree level-by-level using queue. Separate levels using level-size counter or sentinel nodes.

Sliding Window Maximum with Monotonic Deque

Maintain deque with indices in decreasing value order. Remove outdated indices and back-elements smaller than current.

Task Scheduling Round-Robin

Allocate time quantum to each task. If incomplete, re-enqueue with remaining time. Repeat until queue empty.

Practical Example

Python

from collections import deque

# BFS for shortest path in unweighted graph
def bfs_shortest_path(graph, start, end):
    """Find shortest path from start to end using BFS."""
    queue = deque([start])
    visited = {start}
    parent = {start: None}

    while queue:
        node = queue.popleft()
        if node == end:
            # Reconstruct path
            path = []
            current = end
            while current is not None:
                path.append(current)
                current = parent[current]
            return path[::-1]

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

    return []  # No path found

# Level-order tree traversal
def level_order_traversal(root):
    """Traverse binary tree level-by-level."""
    if not root:
        return []

    queue = deque([root])
    result = []

    while queue:
        level_size = len(queue)
        current_level = []

        for _ in range(level_size):
            node = queue.popleft()
            current_level.append(node.val)

            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

        result.append(current_level)

    return result

# Sliding window maximum using monotonic deque
def sliding_window_maximum(nums, k):
    """Find maximum in each sliding window of size k."""
    if not nums or k == 0:
        return []

    deq = deque()  # Store indices
    result = []

    for i in range(len(nums)):
        # Remove indices outside current window
        while deq and deq[0] < i - k + 1:
            deq.popleft()

        # Remove indices of elements smaller than current
        while deq and nums[deq[-1]] < nums[i]:
            deq.pop()

        deq.append(i)

        # Add max to result once window is full
        if i >= k - 1:
            result.append(nums[deq[0]])

    return result

# Task scheduling with round-robin
def round_robin_scheduling(tasks, time_quantum):
    """Schedule tasks with round-robin algorithm."""
    queue = deque(tasks)  # Each task is (name, duration)
    schedule = []
    current_time = 0

    while queue:
        name, duration = queue.popleft()

        if duration <= time_quantum:
            current_time += duration
            schedule.append((name, current_time))
        else:
            current_time += time_quantum
            queue.append((name, duration - time_quantum))

    return schedule

# Test cases
graph = {
    0: [1, 2],
    1: [0, 3],
    2: [0, 3],
    3: [1, 2]
}
print(f"Shortest path 0->3: {bfs_shortest_path(graph, 0, 3)}")
print(f"Sliding window max [1,3,-1,-3,5,3,6,7], k=3: {sliding_window_maximum([1,3,-1,-3,5,3,6,7], 3)}")

tasks = [("A", 8), ("B", 4), ("C", 2)]
print(f"Round-robin schedule: {round_robin_scheduling(tasks, 4)}")

Java

import java.util.*;

public class QueueApplications {
    // BFS for shortest path in unweighted graph
    static List<Integer> bfsShortestPath(Map<Integer, List<Integer>> graph,
                                        int start, int end) {
        Queue<Integer> queue = new LinkedList<>();
        Set<Integer> visited = new HashSet<>();
        Map<Integer, Integer> parent = new HashMap<>();

        queue.offer(start);
        visited.add(start);
        parent.put(start, -1);

        while (!queue.isEmpty()) {
            int node = queue.poll();
            if (node == end) {
                // Reconstruct path
                List<Integer> path = new ArrayList<>();
                int current = end;
                while (current != -1) {
                    path.add(0, current);
                    current = parent.get(current);
                }
                return path;
            }

            for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    parent.put(neighbor, node);
                    queue.offer(neighbor);
                }
            }
        }
        return new ArrayList<>();
    }

    // Sliding window maximum using monotonic deque
    static int[] slidingWindowMaximum(int[] nums, int k) {
        if (nums.length == 0 || k == 0) return new int[0];

        Deque<Integer> deq = new LinkedList<>();
        int[] result = new int[nums.length - k + 1];
        int resultIdx = 0;

        for (int i = 0; i < nums.length; i++) {
            // Remove indices outside current window
            while (!deq.isEmpty() && deq.peekFirst() < i - k + 1) {
                deq.pollFirst();
            }

            // Remove indices of smaller elements
            while (!deq.isEmpty() && nums[deq.peekLast()] < nums[i]) {
                deq.pollLast();
            }

            deq.addLast(i);

            // Add max to result once window is full
            if (i >= k - 1) {
                result[resultIdx++] = nums[deq.peekFirst()];
            }
        }

        return result;
    }

    // Task scheduling with round-robin
    static List<String> roundRobinScheduling(Queue<Task> tasks, int timeQuantum) {
        List<String> schedule = new ArrayList<>();
        int currentTime = 0;

        while (!tasks.isEmpty()) {
            Task task = tasks.poll();

            if (task.duration <= timeQuantum) {
                currentTime += task.duration;
                schedule.add(task.name + " completed at " + currentTime);
            } else {
                currentTime += timeQuantum;
                task.duration -= timeQuantum;
                tasks.offer(task);
            }
        }

        return schedule;
    }

    static class Task {
        String name;
        int duration;
        Task(String name, int duration) {
            this.name = name;
            this.duration = duration;
        }
    }

    public static void main(String[] args) {
        int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
        System.out.println("Sliding window max: " +
            Arrays.toString(slidingWindowMaximum(nums, 3)));
    }
}

TypeScript

// BFS for shortest path
function bfsShortestPath(
    graph: Map<number, number[]>,
    start: number,
    end: number
): number[] {
    const queue: number[] = [start];
    const visited = new Set([start]);
    const parent = new Map([[start, -1]]);

    while (queue.length > 0) {
        const node = queue.shift()!;

        if (node === end) {
            const path: number[] = [];
            let current: number | undefined = end;
            while (current !== -1) {
                path.unshift(current);
                current = parent.get(current);
            }
            return path;
        }

        for (const neighbor of graph.get(node) || []) {
            if (!visited.has(neighbor)) {
                visited.add(neighbor);
                parent.set(neighbor, node);
                queue.push(neighbor);
            }
        }
    }

    return [];
}

// Sliding window maximum with monotonic deque
function slidingWindowMaximum(nums: number[], k: number): number[] {
    if (nums.length === 0 || k === 0) return [];

    const deq: number[] = [];  // Store indices
    const result: number[] = [];

    for (let i = 0; i < nums.length; i++) {
        // Remove indices outside window
        while (deq.length > 0 && deq[0] < i - k + 1) {
            deq.shift();
        }

        // Remove smaller elements from back
        while (deq.length > 0 && nums[deq[deq.length - 1]] < nums[i]) {
            deq.pop();
        }

        deq.push(i);

        // Add max when window is full
        if (i >= k - 1) {
            result.push(nums[deq[0]]);
        }
    }

    return result;
}

// Test
const nums = [1, 3, -1, -3, 5, 3, 6, 7];
console.log("Sliding window max:", slidingWindowMaximum(nums, 3));

Common Pitfalls

warning

Forgetting to mark visited in BFS: Without marking nodes as visited, cycles cause infinite loops. Mark before adding to queue, not when removing.

Index confusion in deque problems: Store indices, not values, in monotonic deques for sliding window. Using values prevents proper window boundary checking.

Off-by-one in window initialization: Sliding window maximum should start output when window is full (i >= k-1), not before. Starting too early produces incorrect results.

Task scheduling with starvation: Simple FIFO scheduling can starve low-priority tasks. Implement aging or multi-level queues to ensure fairness.

Not handling empty input: Empty arrays, null roots, or empty graphs require explicit handling before queue operations.

Self-Check

1. Why does BFS find shortest paths in unweighted graphs? What changes for weighted graphs?
2. How does the monotonic deque maintain maximum efficiently? Why is index storage critical?
3. Explain round-robin scheduling. What is the purpose of the time quantum parameter?

One Takeaway

info

Queues are powerful for level-based exploration (BFS), fair scheduling (FIFO), and sliding window problems (with deques). Monotonic deques specifically unlock O(n) sliding window solutions. Recognizing when queue-based approaches apply separates optimized solutions from brute force implementations.

References

• Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
• McDowell, G. L. (2015). Cracking the Coding Interview (6th ed.). CareerCup.