Chapter 30

Home

Queues and Fair Processing

A stack is LIFO. A queue is FIFO — First In, First Out. Think of a ticket counter: the first person in line gets served first. Queues model fairness, ordering, and breadth-first traversal.

The Queue Mentality

Three operations: push (enqueue) to the back, pop (dequeue) from the front, front to peek.

10 20 30 → front → pop here back ← push here

C++ — std::queue

#include <bits/stdc++.h>
using namespace std;

int main() {
    queue<int> q;

    q.push(10);
    q.push(20);
    q.push(30);

    cout << q.front() << "\n";  // 10
    q.pop();                       // remove 10
    cout << q.front() << "\n";  // 20
    cout << q.size() << "\n";    // 2
    cout << q.empty() << "\n";   // 0 (false)

    return 0;
}

pop() removes the front but doesn't return it.

Rust — VecDeque

use std::collections::VecDeque;

fn main() {
    let mut q: VecDeque<i32> = VecDeque::new();

    q.push_back(10);
    q.push_back(20);
    q.push_back(30);

    println!("{}", q.front().unwrap());   // 10
    q.pop_front();                         // remove 10
    println!("{}", q.front().unwrap());   // 20
    println!("{}", q.len());              // 2
    println!("{}", q.is_empty());         // false
}

Rust's VecDeque is a double-ended queue — use push_back + pop_front for FIFO.

💡 Why not Vec for a queue?

Removing from the front of a Vec / vector is O(N) — every element shifts down. A queue / VecDeque is O(1) for both front and back operations. Always use the right tool.

Simulating a Ticket Counter

Each person takes a certain time to serve. Process them one by one, tracking wait times and total time. 

// C++ — process queue of customers
queue<int> customers;  // each element = service time
customers.push(5);
customers.push(3);
customers.push(8);

int total_time = 0;
while (!customers.empty()) {
    total_time += customers.front();
    cout << "Served after: " << total_time << "\n";
    customers.pop();
}

Queue in BFS (Preview)

The queue is the engine behind Breadth-First Search. You'll see this in detail in Phase 8, but here's a sneak peek — exploring a grid level by level:

C++ — BFS skeleton

using pii = pair<int,int>;
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

void bfs(vector<vector<int>>& grid, int sx, int sy) {
    queue<pii> q;
    q.push({sx, sy});

    while (!q.empty()) {
        auto [x, y] = q.front(); q.pop();
        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d], ny = y + dy[d];
            if (nx >= 0 && nx < grid.size() &&
                ny >= 0 && ny < grid[0].size() &&
                grid[nx][ny] == 0) {
                grid[nx][ny] = grid[x][y] + 1;
                q.push({nx, ny});
            }
        }
    }
}

📐 The BFS order property

BFS visits nodes in order of their distance from the start. The queue ensures that all distance-1 nodes are processed before any distance-2 node, and so on. This is why BFS finds the shortest path in an unweighted graph.

Key Takeaways

Practice