Dheerendra Varma
21 / 388 min read

Queue

First-In First-Out — the structure that drives BFS, level-order traversal, and the sliding window maximum. Understand the deque and monotonic queue patterns that appear in advanced problems.

What is a Queue?

A queue is a linear data structure where elements are added at the rear (enqueue) and removed from the front (dequeue). This First-In First-Out (FIFO) ordering guarantees that elements are processed in the exact order they arrived — like a line of customers at a counter.

Queues are the natural structure for any breadth-first exploration: processing all nodes at distance 1 before those at distance 2, all nodes at level k before level k+1. This property makes queues the backbone of BFS in both graphs and trees, shortest-path algorithms in unweighted graphs, and level-order traversal.

Applications

BFS graph traversal uses a queue to guarantee shortest-path discovery in unweighted graphs. Operating system schedulers use priority queues (a generalisation) to pick which process runs next. Print spoolers queue jobs in the order they arrive. Streaming systems like Kafka and RabbitMQ are essentially distributed queues. Web servers queue incoming requests before workers pick them up. CPU instruction pipelines stage instructions through a sequence of queues.

Representations

Rust's VecDeque<T> from the standard library is a double-ended queue backed by a ring buffer. Push and pop at both ends are O(1) amortised. It is the correct default for any queue or deque in Rust.

use std::collections::VecDeque;
 
struct Queue<T> {
    data: VecDeque<T>,
}
 
impl<T> Queue<T> {
    fn new() -> Self {
        Queue { data: VecDeque::new() }
    }
 
    fn enqueue(&mut self, val: T) {
        self.data.push_back(val);
    }
 
    fn dequeue(&mut self) -> Option<T> {
        self.data.pop_front()
    }
 
    fn front(&self) -> Option<&T> {
        self.data.front()
    }
 
    fn is_empty(&self) -> bool {
        self.data.is_empty()
    }
 
    fn size(&self) -> usize {
        self.data.len()
    }
}
 
fn main() {
    let mut q: Queue<i32> = Queue::new();
    q.enqueue(1); q.enqueue(2); q.enqueue(3);
    println!("front: {:?}", q.front());    // Some(1)
    println!("dequeue: {:?}", q.dequeue()); // Some(1)
    println!("front: {:?}", q.front());    // Some(2)
}

A naive Vec<T> queue using push (enqueue at back) and remove(0) (dequeue from front) is O(n) per dequeue because all elements shift left. Always use VecDeque for O(1) operations at both ends.

A circular array queue can be implemented manually when you know the maximum capacity in advance, using head and tail indices modulo capacity. VecDeque implements exactly this under the hood with dynamic resizing.

Operations and Time Complexity

OperationTimeNotes
enqueue (push_back)O(1) amortised
dequeue (pop_front)O(1) amortised
front / peekO(1)
push_front (deque)O(1) amortisedVecDeque only
pop_back (deque)O(1) amortisedVecDeque only
is_emptyO(1)
searchO(n)Linear scan

Fundamental Algorithms and Problems

BFS — Shortest Path in an Unweighted Grid

Find the shortest path from the top-left to the bottom-right of a grid where 0 is open and 1 is blocked. BFS explores all cells at distance k before any cell at distance k+1, so the first time it reaches the destination it has found the shortest path. Track visited cells to avoid re-processing, and store the distance alongside each cell in the queue.

use std::collections::VecDeque;
 
fn bfs_shortest_path(grid: &Vec<Vec<i32>>) -> i32 {
    let rows = grid.len();
    let cols = grid[0].len();
    if grid[0][0] == 1 || grid[rows-1][cols-1] == 1 { return -1; }
 
    let mut visited = vec![vec![false; cols]; rows];
    let mut queue = VecDeque::new();
    queue.push_back((0usize, 0usize, 1i32));
    visited[0][0] = true;
 
    let dirs: [(i32, i32); 4] = [(-1,0),(1,0),(0,-1),(0,1)];
 
    while let Some((r, c, dist)) = queue.pop_front() {
        if r == rows - 1 && c == cols - 1 { return dist; }
        for (dr, dc) in dirs {
            let nr = r as i32 + dr;
            let nc = c as i32 + dc;
            if nr >= 0 && nr < rows as i32 && nc >= 0 && nc < cols as i32 {
                let (nr, nc) = (nr as usize, nc as usize);
                if !visited[nr][nc] && grid[nr][nc] == 0 {
                    visited[nr][nc] = true;
                    queue.push_back((nr, nc, dist + 1));
                }
            }
        }
    }
    -1
}
 
fn main() {
    let grid = vec![
        vec![0, 0, 0],
        vec![1, 1, 0],
        vec![0, 0, 0],
    ];
    println!("{}", bfs_shortest_path(&grid)); // 5
}

Level-Order Traversal of a Binary Tree

Process a binary tree level by level, returning each level's values as a separate list. After dequeuing a node, enqueue its children. Because all children of the current level are enqueued before any grandchildren, snapshotting queue.len() at the start of each iteration gives exactly the number of nodes at the current level.

use std::collections::VecDeque;
 
#[derive(Debug)]
struct TreeNode {
    val: i32,
    left: Option<Box<TreeNode>>,
    right: Option<Box<TreeNode>>,
}
 
fn level_order(root: Option<&Box<TreeNode>>) -> Vec<Vec<i32>> {
    let mut result: Vec<Vec<i32>> = Vec::new();
    let root = match root { Some(r) => r, None => return result };
 
    let mut queue: VecDeque<&TreeNode> = VecDeque::new();
    queue.push_back(root);
 
    while !queue.is_empty() {
        let level_size = queue.len();
        let mut level = Vec::new();
        for _ in 0..level_size {
            let node = queue.pop_front().unwrap();
            level.push(node.val);
            if let Some(l) = &node.left  { queue.push_back(l); }
            if let Some(r) = &node.right { queue.push_back(r); }
        }
        result.push(level);
    }
    result
}

Sliding Window Maximum — Monotonic Deque

Given an array and window size k, find the maximum element in each window. The naive approach is O(n·k). The monotonic deque approach maintains a deque of indices whose values are in decreasing order. Before adding a new element, pop from the back all indices with smaller values — they can never be the maximum of any future window. Pop from the front any index that has slid out of the window. The front of the deque is always the maximum of the current window.

use std::collections::VecDeque;
 
fn sliding_window_max(arr: &[i32], k: usize) -> Vec<i32> {
    let n = arr.len();
    let mut result = Vec::with_capacity(n - k + 1);
    let mut deque: VecDeque<usize> = VecDeque::new(); // indices, decreasing value
 
    for i in 0..n {
        // Remove indices outside the window
        while let Some(&front) = deque.front() {
            if front + k <= i { deque.pop_front(); } else { break; }
        }
        // Remove indices with smaller values (they'll never be the max)
        while let Some(&back) = deque.back() {
            if arr[back] <= arr[i] { deque.pop_back(); } else { break; }
        }
        deque.push_back(i);
 
        if i + 1 >= k {
            result.push(arr[*deque.front().unwrap()]);
        }
    }
    result
}
 
fn main() {
    let arr = [1, 3, -1, -3, 5, 3, 6, 7];
    println!("{:?}", sliding_window_max(&arr, 3));
    // [3, 3, 5, 5, 6, 7]
}

First Non-Repeating Character in a Stream

As characters arrive one by one in a stream, report the first non-repeating character after each arrival. Maintain a queue of candidates in arrival order and a frequency map. After each character, skip the front of the queue while its frequency is greater than one (it's no longer unique). The front of the queue is the first non-repeating character.

use std::collections::{VecDeque, HashMap};
 
fn first_non_repeating_stream(stream: &str) -> Vec<Option<char>> {
    let mut freq: HashMap<char, usize> = HashMap::new();
    let mut queue: VecDeque<char> = VecDeque::new();
    let mut result = Vec::new();
 
    for ch in stream.chars() {
        *freq.entry(ch).or_insert(0) += 1;
        queue.push_back(ch);
 
        // Remove duplicates from front
        while let Some(&front) = queue.front() {
            if freq[&front] > 1 { queue.pop_front(); } else { break; }
        }
        result.push(queue.front().copied());
    }
    result
}
 
fn main() {
    let output = first_non_repeating_stream("aabcdb");
    let display: Vec<_> = output.iter().map(|o| o.map(|c| c.to_string())
        .unwrap_or("-".into())).collect();
    println!("{:?}", display); // ["a", "-", "b", "c", "c", "d"]
}

Task Scheduler — Greedy with Counting

Given tasks labelled A–Z and a cooldown n (same task must wait at least n intervals), find the minimum total time to finish all tasks. The greedy strategy: always execute the most frequent remaining task. If no valid task exists, idle. The answer is max(total_tasks, (max_freq - 1) * (n + 1) + count_of_max_freq_tasks). This formula accounts for the idle slots that the most frequent task forces between its executions.

fn least_interval(tasks: &[char], n: u32) -> u32 {
    let mut freq = [0u32; 26];
    for &t in tasks {
        freq[(t as u8 - b'A') as usize] += 1;
    }
    freq.sort_unstable();
 
    let max_freq = freq[25];
    let idle_slots = (max_freq - 1) * n;
 
    // Count tasks with same frequency as max
    let max_freq_count = freq.iter().filter(|&&f| f == max_freq).count() as u32;
 
    // idle_slots filled by other tasks, or we need extra slots for ties
    let remaining_tasks: u32 = freq[..25].iter().sum();
    let idle_remaining = idle_slots.saturating_sub(remaining_tasks);
 
    tasks.len() as u32 + idle_remaining
        + if max_freq_count > 1 { max_freq_count - 1 } else { 0 }
}
 
fn main() {
    let tasks = ['A','A','A','B','B','B'];
    println!("{}", least_interval(&tasks, 2)); // 8: A B _ A B _ A B
}