Queue

A first-in, first-out sequence. enqueue adds at the end in O(1). dequeue takes from the front in amortised O(1): most calls are O(1), and now and then one pays O(n) to put the elements added at the end in order.

When to choose it

For first in, first out: a work list, a breadth-first walk. It also has the other sequence methods, but access by index walks the queue; choose Vector for that.

var queue = Queue.of("a", "b").enqueue("c");  // Queue<String>
var next  = queue.dequeue();                  // Tuple2<String, Queue<String>>
// next is (a, Queue(b, c))

var work    = Queue.of(1);
var visited = 0;
while (!work.isEmpty() && visited < 5) {
    var step = work.dequeue(); // Tuple2<Integer, Queue<Integer>>
    work     = step._2().enqueue(step._1() * 2, step._1() * 2 + 1);
    visited++;
}
// visited is 5, work is Queue(6, 7, 8, 9, 10, 11)

Costs

Operation	Cost	Note
head	O(1)	O(1).
tail	amortised O(1)	amortised O(1) over a chain of calls, each on the result of the previous one. When the removed element is the last one before the elements held at the back, the call puts those in order in one O(n) step. The Queue keeps that result: calling tail() again on the same older Queue is O(1).
last	O(n)	O(n); O(1) when some elements are held at the back, as after an enqueue.
init	amortised O(1)	amortised O(1) over a chain of calls, each on the result of the previous one. When no element is held at the back, the call moves the second half of the Queue there in one O(n) step, which the next calls use up. The Queue keeps that result: calling init() again on the same older Queue is O(1).
get	O(n)	O(n); O(i) for an index i that falls before the elements held at the back. Every index does on a Queue built by ofAll; on a Queue built by enqueue, only index 0 does.
update	O(n)	O(n).
prepend	O(1)	O(1).
append	O(1)	O(1), as enqueue.
prependAll	O(m)	O(m) for m prepended elements.
appendAll	O(m)	O(m) for m appended elements.
insert	O(n)	O(n).
removeAt	O(n)	O(n).
take	O(n)	O(n).
drop	O(n)	O(n).
slice	O(n)	O(n).
splitAt(Predicate<? super T>)	O(n)	O(n).
splitAt(int)	O(n)	O(n).
reverse	O(n)	O(n).
sorted	O(n log n)	O(n log n) comparisons.
size	O(n)	O(n): the elements are counted. isEmpty is O(1).
sizeCompare(Iterable<?>)	O(min(n, m))	O(min(n, m)), at most: a size that is not stored is counted only up to the other one; O(1) when the size of that is stored. The elements held at the back, of this queue and of a Queue that, are counted where they are, not put in order first, as iterator() does once it reaches them.
sizeCompare(int)	O(min(n, k))	O(min(n, k)) for k = otherSize: at most k + 1 elements are counted, where size() counts them all.
contains	O(n)	O(n): the elements are compared one by one until an equal one is found. The sets and the maps override it with a lookup.
indexOf	O(n)	O(n).
zip	O(n)	O(n); O(min(n, m)) for an argument of m elements when the pairing stops before the elements held at the back, which it must otherwise put in order. On a Queue built by enqueue, even a one-element argument costs O(n).
sliding(int)	O(n * size)	O(n * size); each window is copied into its own Queue.
sliding(int, int)	O(n + (n / step) * size)	O(n + (n / step) * size): every element is walked, and each window is copied into its own Queue.
grouped	O(n)	O(n); each block is copied into its own Queue.
distinct	O(n)	O(n).

Every method: complexity page.

Sharp edges

• dequeue() on an empty queue throws; dequeueOption() returns an Option.
• The amortised cost holds when each dequeue works on the queue the previous one returned. A queue keeps the result of its O(n) step, so calling dequeue again on the same old queue pays it once. A new queue made from that old one, by an enqueue for example, pays the step again when it is dequeued.
• Creating an iterator() can cost O(n), and so can get(i) for a small i: on a queue built by enqueue, most elements are still waiting at the end, in reverse order. size() counts the elements; isEmpty() is O(1), and sizeCompare(n) counts at most n + 1 of them.