Std.Deque.Deque

type

This declaration introduces a public type.

What it does

A queue that can be added to and taken from at either end.

An array is cheap at its back and dear at its front: adding or removing a

first element moves every other one. A program that queues work — a

breadth-first walk, a scheduler, a window over a stream — takes from the

front on every step, and pays that cost on every step.

This holds two arrays instead. The front is kept reversed, so taking from

the front and adding to the back are both work at the end of an array,

which is where an array is cheap. When one side runs out, the other is

split across the two. Each element moves a bounded number of times over its

life in the queue, so the cost per operation averages out to a constant

even though a single one occasionally does more.

Read the signature

• This declaration has no value signature because it introduces a type or trait.