Deque

A vector is quick at its end and slow at its front. Pushing at the end writes into the next free slot; putting a value at position zero means shifting every other value along by one to make room — a thousand moves for a thousand values.

A Deque<T> — a double-ended queue, said "deck" — is quick at both ends. It remembers where its contents start as well as where they end, so adding at the front moves a marker, not the values. Its everyday use is a queue: work joins at the back and is served from the front, which is exactly the pair of operations a vector is bad at.

Four operations, two ends

flowchart LR
    f["`PushFront`<br/>`PopFront`"] <--> front["front"]
    front --- mid["…"]
    mid --- back["back"]
    back <--> b["`PushBack`<br/>`PopBack`"]

A deque is made like a vector, from an allocator:

var queue = Deque<int>(allocator);

A queue of tickets

Tickets join at the back, in the order they arrive. Each push may need more room, and so can fail; ? hands that failure to Main:

queue.PushBack(101)?;
queue.PushBack(102)?;
queue.PushBack(103)?;

An urgent ticket jumps the line by going in at the front:

queue.PushFront(900)?;

The queue is now 900 101 102 103. Serving takes from the front:

PrintLine("served   {}", queue.PopFront() ?? -1);
PrintLine("served   {}", queue.PopFront() ?? -1);

The urgent ticket, 900, is served first, then 101 — first in, first out. Both pops return an optional, int?, since an empty deque has nothing to give; ?? -1 supplies a stand-in that never prints here.

The newest arrival changes their mind and leaves from the back:

PrintLine("left     {}", queue.PopBack() ?? -1);

That is 103, leaving only 102 waiting.

When the queue runs dry

After one more pop the deque is empty, and the next PopFront returns none. A match says so properly rather than printing a stand-in:

match queue.PopFront() {
    ticket? => PrintLine("served   {}", ticket),
    none => PrintLine("empty    nobody is waiting")
}

Looking without taking

Show prints the queue without changing it. It borrows the deque as &Deque<int> and reads each position with Get, which, like a vector's, returns an optional:

func Show(label: char8[..], queue: &Deque<int>) {
    Print("{:8}", label);
    for i in 0..queue.Length() {
        Print(" {}", queue.Get(i) ?? -1);
    }
    PrintLine();
}

Position 0 is always the front, whichever end the values came in by.

Which to reach for

A vector when values only come and go at the end — a list you build and then read. A deque when both ends are in play — a queue, a window of the latest readings, a list of jobs where some jump the line. The deque's bookkeeping costs a little on every operation, which is why it is not simply the default.

The program

The whole lesson is one package in the Examples repository. Its comments explain every step.

// A vector is quick at its end and slow at its front: putting a value at position zero means
// shifting every other value along to make room.
//
// A `Deque<T>` — a double-ended queue, said "deck" — is quick at both ends. It remembers where its
// contents start as well as where they end, so adding at the front moves a marker, not the
// values. The everyday use is a queue: work joins at the back and is served from the front,
// which is exactly the pair of operations a vector is bad at.
import Allocator::{ Allocator, SystemAllocator };
import Collections::{ CollectionError, Deque };
import Io::{ Print, PrintLine };

func Show(label: char8[..], queue: &Deque<int>) {
    Print("{:8}", label);
    for i in 0..queue.Length() {
        Print(" {}", queue.Get(i) ?? -1);
    }
    PrintLine();
}

func Main() -> ! CollectionError {
    var system = SystemAllocator();
    let allocator: Allocator = system;

    var queue = Deque<int>(allocator);

    // Tickets join at the back, in the order they arrive. Each push may need more room, and so
    // can fail; `?` hands that failure to `Main`.
    queue.PushBack(101)?;
    queue.PushBack(102)?;
    queue.PushBack(103)?;
    Show("arrived", queue);

    // An urgent ticket jumps the line by going in at the front.
    queue.PushFront(900)?;
    Show("urgent", queue);

    // Serving takes from the front. Both pops return an optional, `int?`, since an empty deque
    // has nothing to give.
    PrintLine("served   {}", queue.PopFront() ?? -1);
    PrintLine("served   {}", queue.PopFront() ?? -1);

    // The newest arrival changes their mind and leaves from the back.
    PrintLine("left     {}", queue.PopBack() ?? -1);
    Show("waiting", queue);

    PrintLine("served   {}", queue.PopFront() ?? -1);
    match queue.PopFront() {
        ticket? => PrintLine("served   {}", ticket),
        none => PrintLine("empty    nobody is waiting")
    }

    // Which to reach for: a vector when values only come and go at the end, a deque when both
    // ends are in play. The deque's bookkeeping costs a little per operation, which is why it
    // is not simply the default.
}

Besides Io, its Rux.toml lists Allocator and Collections under [Dependencies].

Run it

cd Examples/Collections/Deque
rux run

arrived  101 102 103
urgent   900 101 102 103
served   900
served   101
left     103
waiting  102
served   102
empty    nobody is waiting

Common mistakes

Try it yourself

1. Use the deque as a stack: push three values with PushBack and pop them with PopBack. In which order do they come out?
2. Make a round robin: pop a ticket from the front, print it, and push it on the back, six times over three tickets.
3. Keep only the latest three readings: push each new reading at the back, and pop from the front whenever the length passes three.

Learn more

• Vector — the container a deque is compared with
• Presence and Coalesce — unwrapping the optional a pop returns
• Reference — borrowing the deque in Show
• Hash map — finding values by key instead of by position