Double-ended queues

What is the largest of the last four values, at every step? A deque keeps the answer at its front. Watch it slide.

⋯14void push_back(struct deque *d, int v)15{16    d->items[(d->head + d->count) % CAP] = v;17    d->count++;18}⋯27void pop_back(struct deque *d)28{29    d->count--;30}31 32void pop_front(struct deque *d)33{34    d->head = (d->head + 1) % CAP;35    d->count--;36}37 38int front(const struct deque *d)39{40    return d->items[d->head];41}42 43int back(const struct deque *d)44{45    return d->items[(d->head + d->count - 1) % CAP];46}⋯48int main(void)49{50    const int x[N] = { 2, 7, 3, 1, 8, 6, 4, 2, 5, 3, 9, 1 };51    struct deque d = { .count = 0 };52    for (int i = 0; i < N; i++) {53        while (d.count > 0 && x[back(&d)] <= x[i])54            pop_back(&d);55        push_back(&d, i);56        if (d.count > most)57            most = d.count;58        if (front(&d) <= i - W)59            pop_front(&d);60        if (i >= W - 1)61            printf("%d ", x[front(&d)]);62    }63    printf("\n");64    printf("deque held at most %d\n", most);65    return 0;66}

Both ends

A double-ended queue, or deque (said “deck”), lets items join and leave at both ends. It has four operations:

• push_front and push_back: add an item at the front or at the back.
• pop_front and pop_back: remove the item at the front or at the back.

with front and back to read the two ends. Used only at the back, a deque is a stack; joining at the back and leaving at the front, it is a queue. Two in-between forms have names of their own: an input-restricted deque adds at one end only but removes at both, and an output-restricted deque removes at one end only but adds at both.

The code and its cost

A deque on a ring

The ring buffer of Circular queues already moves its head forward round the ring; a deque also lets it move back. This one keeps head and a count, and works out where the back is:

struct deque {
    int items[CAP];
    int head, count;
};

void push_back(struct deque *d, int v)
{
    d->items[(d->head + d->count) % CAP] = v;
    d->count++;
}

void push_front(struct deque *d, int v)
{
    d->head = (d->head + CAP - 1) % CAP;
    d->items[d->head] = v;
    d->count++;
}

void pop_back(struct deque *d)
{
    d->count--;
}

void pop_front(struct deque *d)
{
    d->head = (d->head + 1) % CAP;
    d->count--;
}

The back’s next free cell is (head + count) % CAP, and the back item is one before it. push_front steps head back one cell. It adds CAP − 1 rather than subtracting 1, because in C the remainder keeps the sign of what is divided: for head 0, (0 − 1) % 8 is −1, not 7, while (0 + 7) % 8 is 7. As in Stacks, the pops trust their caller to check that count is more than 0. Every operation is a fixed few steps.

sizeof (struct deque) is 40 bytes. In the clip, d sits at 0x7f90, so items[k] is at 0x7f90 + 4k, head at 0x7fb0 and count at 0x7fb4; x, the twelve values, is at 0x7fc0.

A deque can also be built on the nodes of Doubly linked lists, where each end is a node with a pointer to its neighbour; then it has no capacity, at the price of a malloc per push.

The largest value in a sliding window

Given n values, the task is to print the largest of every run of W in a row: here W = 4 and twelve values, so nine windows. Looking at all four values of every window would work. The deque does better by keeping only the candidates: values that could still be the largest of some window to come.

When a new value arrives, every value before it that is no larger can never be a maximum again: the new value is at least as large and will stay in the window longer. So:

1. Drop from the back every candidate no larger than the new value.
2. Push the new value at the back.
3. Drop from the front the candidate that has left the window.
4. The front is the window’s maximum.

The candidates left are always in decreasing order from front to back, so the front is the largest. The deque holds indices, not values: the value is x[index], and the index tells when a candidate has fallen out of the window.

for (int i = 0; i < N; i++) {
    while (d.count > 0 && x[back(&d)] <= x[i])
        pop_back(&d);
    push_back(&d, i);
    if (d.count > most)
        most = d.count;
    if (front(&d) <= i - W)
        pop_front(&d);
    if (i >= W - 1)
        printf("%d ", x[front(&d)]);
}

On the twelve values the program prints the nine maxima, then how full the deque ever got:

7 8 8 8 8 6 5 9 9
deque held at most 4

What it costs

Each index is pushed once and popped at most once, from one end or the other, so n values take at most 2n deque operations, however large the window. On these twelve values there were 12 pushes, 8 pops from the back and 2 from the front. The plain way compares W − 1 times per window: 3 × 9 = 27 comparisons here. The deque needs no more than a few cells, here 4 of its 8.

Running it yourself

gcc -std=c11 -Wall -Wextra -pedantic window-max.c -o window-max
./window-max

Worked example

Why the 2 goes. At i = 1, 7 arrives. The 2 at index 0 is smaller, and every window that will ever hold the 2 again also holds the 7. So the 2 can never be printed, and it is dropped from the back.

By hand. The window maxima of 1, 2, 3, 4, 5 with W = 2 are 2, 3, 4, 5. Each value drops the one before it, so the deque never holds more than one index after its push.

A long signal. For a million values and a window of 1,000, the plain method makes 999 comparisons for each of nearly a million windows, about a billion in all. The deque makes at most two million operations.

The minimum. Change <= to >= in the drop from the back, and the front is always the window’s smallest value instead.

Where it’s used

Running maxima of signals. The largest value over the last second of a sensor, the peak level of an audio meter: the maximum over a sliding window is a non-linear cousin of the moving average of Simple smoothing filters. Unlike an average, it ignores dips narrower than the window.

Images. The same window, swept over an image, gives the dilation and erosion of morphological image processing.

Schedulers. In work-stealing schedulers, each worker takes tasks from one end of its own deque, and an idle worker steals from the other end.

Reference card

Platform: C11, gcc on x86-64 Linux: int 4 bytes, pointers 8, little-endian. Addresses in the pictures are short stand-ins, by one rule for the whole course; sizes are the real ones.