Queue¶
A first-in, first-out sequence. enqueue adds at the end and dequeue takes from the front, both in amortised O(1):
most calls are O(1), and now and then a dequeue pays O(n) to reorder the queue.
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.
Queue<String> queue = Queue.of("a", "b").enqueue("c");
Tuple2<String, Queue<String>> next = queue.dequeue();
// next is (a, Queue(b, c))
Queue<Integer> work = Queue.of(1);
int visited = 0;
while (!work.isEmpty() && visited < 5) {
Tuple2<Integer, Queue<Integer>> step = work.dequeue();
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); the head of the front list. |
tail |
amortised O(1) | amortised O(1); the front loses its head, and the rear is reversed onto it only when the front runs out. |
last |
O(n) | O(n) when the rear is empty and the front is walked; O(1) when the rear is non-empty. |
init |
amortised O(1) | amortised O(1); the last element is the head of the rear list, unless the rear is empty and the front is walked. |
get |
O(index) | O(index) while the index is in the front; O(n) once it falls in the rear, which is measured and indexed from its end. |
update |
O(n) | O(n). |
prepend |
O(1) | O(1); the element is prepended to the front list. |
append |
amortised O(1) | amortised O(1); the element is prepended to the rear list. |
prependAll |
O(m) | O(m) for m prepended elements. |
appendAll |
O(m) | O(m) for m appended elements. |
insert |
O(n) | O(n); the front, and the rear when the index falls in it, are walked. |
removeAt |
O(n) | O(n). |
take |
O(n) | O(n). |
drop |
O(n) | O(n); the front and the rear are both walked. |
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. |
length |
O(n) | O(n); the front and the rear are counted. |
contains |
O(n) | O(n) for this default, which walks the elements; the sets and the maps override it with their own lookup. |
indexOf |
O(n) | O(n). |
zip |
O(min(n, m)) | O(min(n, m)) for an argument of m elements. |
sliding(int) |
O(n * size) | O(n * size); each window is copied into its own Queue. |
sliding(int, int) |
O(n * size / step) | O(n * size / step); 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 anOption.- The amortised cost holds when each
dequeueworks on the queue the previous one returned. Callingdequeueagain and again on the same old queue can pay the O(n) step every time. - Creating an
iterator()can cost O(n).