Queues: Deque and PriorityQueue

Two collections take elements out in an order other than an Array’s:

An Array can stand in for either, but removing its first element takes O(n), and keeping it sorted takes O(n) per insert.

Deque

A Deque (a double-ended queue) is a ring buffer that grows when full: push_back, push_front, pop_back and pop_front add and remove at the two ends, front() and back() read them, and d[i] reads or writes the element i places from the front. It is the queue of a breadth-first search, a sliding window, or an undo history that drops its oldest entry.

# Breadth-first search: a Deque is the queue of nodes to visit.
main(): int {
    # Each node's neighbors: 0 - 1 - 2 - 4 and 0 - 3 - 4.
    int[][] edges = [[1, 3], [0, 2], [1, 4], [0, 4], [2, 3]];
    int[] hops = [0, -1, -1, -1, -1];

    Deque<int> queue = [0];
    while (!queue.is_empty) {
        var node = queue.pop_front();
        for (var next in edges[node as ulong]) {
            if (hops[next as ulong] >= 0) {
                continue;
            }
            hops[next as ulong] = hops[node as ulong] + 1;
            queue.push_back(next);
        }
    }
    assert(hops[4] == 2, "two hops from node 0 to node 4");

    # Both ends work: a window of the last three readings.
    var window = Deque<int>();
    for (var reading in [4, 8, 15, 16, 23]) {
        window.push_back(reading);
        if (window.count > 3) {
            window.pop_front();
        }
    }
    assert(window.front() == 15 and window.back() == 23, "the last three");
    assert(window[1] == 16, "indexed from the front");
    return 0;
}

An array converts to a Deque, so an array literal can initialize one. count, is_empty, capacity, reserve and clear work as they do on an Array. A for loop visits the elements from front to back; changing the deque while a loop iterates it panics (“Deque modified during iteration”). Popping, or reading front() or back(), of an empty deque panics, as does an index past the back.

PriorityQueue

A PriorityQueue is a binary heap: push adds an element in O(log n), pop removes the greatest in O(log n), and peek() reads the greatest without removing it. It is the frontier of Dijkstra’s and A* searches, a scheduler’s run queue, or the k largest values of a stream.

# A scheduler: the job with the earliest deadline runs first.
struct Job {
    var name: String;
    var deadline: int;

    construct(name: String, deadline: int) {
        this.name = name;
        this.deadline = deadline;
    }
}

main(): int {
    # The comparer is reversed, so the smallest deadline is the greatest.
    var jobs = PriorityQueue<Job>((a, b) => b.deadline.compare(a.deadline));
    jobs.push(Job("backup", 30));
    jobs.push(Job("email", 5));
    jobs.push(Job("report", 12));
    assert(jobs.peek().name == "email", "the earliest deadline");

    var order = "";
    while (!jobs.is_empty) {
        order = $"{order}{jobs.pop().name} ";
    }
    assert(order == "email report backup ", "by deadline");

    # Comparable elements need no comparer: the greatest comes out first.
    PriorityQueue<int> scores = [72, 95, 88, 61];
    assert(scores.pop() == 95, "the top score");
    var rest = scores.into_sorted_array();
    assert(rest == [61, 72, 88], "the rest, ascending");
    return 0;
}

Elements are ordered by compare<T>, so numbers, String, and any Comparable type need nothing more. To order by something else, pass a comparer to the constructor: a function that returns a negative number, zero or a positive number as its first argument sorts before, with or after its second. For the smallest first, reverse the comparer, (a, b) => b.compare(a). Elements that sort together come out in no particular order.

An array converts to a PriorityQueue, and PriorityQueue<T>(items, compare) builds one from an array with a comparer; both take O(n), and copy the array. into_sorted_array() empties the queue and returns its elements from smallest to greatest. pop and peek of an empty queue panic.

Neither type is [Shared]: like an Array, each stays on one thread.