Queues and deques
A Queue<E> hands out elements from its head. A Deque<E> adds and removes at both ends, so it serves as a FIFO
queue and as a LIFO stack. Concurrent and blocking queues are not included.
| Need | Use |
|---|---|
| FIFO queue, stack, or both ends | ArrayDeque: O(1) at both ends, one array |
| Always take the smallest or highest-priority item | PriorityQueue: O(log n) insert and remove |
A queue that is also a List, or holds null |
LinkedList |
Pass a stack to code that expects a Queue |
Collections.asLifoQueue(deque) |
| Sorted iteration, not only sorted removal | TreeSet / TreeMap |
Queue and Deque methods
Section titled “Queue and Deque methods”Each operation comes in two forms: one throws when it cannot do its job, the other returns a special value. Use
poll/peek where an empty queue is normal (a processing loop), remove/element where it is a bug. See
throwing and non-throwing pairs.
| Operation | Queue, throws |
Queue, special value |
Deque head |
Deque tail |
|---|---|---|---|---|
| insert | add(e) |
offer(e): false if rejected |
addFirst / offerFirst |
addLast / offerLast |
| remove | remove() |
poll(): null if empty |
removeFirst / pollFirst |
removeLast / pollLast |
| examine | element() |
peek(): null if empty |
getFirst / peekFirst |
getLast / peekLast |
The throwing forms raise NoSuchElementException on an empty queue. Through Queue, a deque is FIFO: add/offer
work on the tail, remove/poll/peek on the head. remove(o) with an argument is the ordinary
Collection.remove; removeFirstOccurrence(o) and removeLastOccurrence(o) scan from the head or the tail.
Using a deque as a stack
Section titled “Using a deque as a stack”push(e) is addFirst(e), pop() is removeFirst() and peek() is peekFirst(). The head is the top of the
stack, so iteration and toString() go top first. This is the recommended stack, rather than the legacy
Stack. Note that push and add work on opposite ends: mixing stack and queue methods on one
deque reorders it.
import { ArrayDeque } from '@ylcnfrht/collections';
const stack = new ArrayDeque<string>();stack.push('a');stack.push('b');stack.push('c');console.log(stack.toString()); // → [c, b, a]console.log(stack.pop()); // → cconsole.log(stack.peek()); // → bArrayDeque
Section titled “ArrayDeque”src/queue/ArrayDeque.tsExtendsAbstractCollectionVerified against the JDK42 members, 103,263 comparisons, 4 excludedA resizable circular array: every end operation is O(1) and there is no per-element allocation. The backing array is
a power of two, 16 slots by default; it doubles when full and never shrinks (clear() keeps the capacity). There is
no indexed access; use ArrayList for that.
import { ArrayDeque } from '@ylcnfrht/collections';
const queue = new ArrayDeque<string>();queue.offer('a');queue.offer('b');queue.offer('c');console.log(queue.peek()); // → aconsole.log(queue.poll()); // → aconsole.log([...queue]); // → [ 'b', 'c' ]console.log(queue.pollLast()); // → cimport { ArrayDeque, HashMap, HashSet, ArrayList, List } from '@ylcnfrht/collections';
// breadth-first search: the deque holds the frontier, poll() returning null ends the loopconst graph = HashMap.of<string, List<string>>( ['a', ArrayList.of('b', 'c')], ['b', ArrayList.of('d')], ['c', ArrayList.of('d', 'e')],);
function bfs(start: string): string[] { const order: string[] = []; const seen = HashSet.of(start); const frontier = ArrayDeque.of(start); let node: string | null; while ((node = frontier.poll()) !== null) { order.push(node); for (const next of graph.getOrDefault(node, List.of())) { if (seen.add(next)) frontier.offer(next); // add() is false if already seen } } return order;}
console.log(bfs('a')); // → [ 'a', 'b', 'c', 'd', 'e' ]Replace offer/poll with push/pop, or wrap the deque in Collections.asLifoQueue, and the same loop is a
depth-first search.
PriorityQueue
Section titled “PriorityQueue”src/queue/PriorityQueue.tsExtendsAbstractQueueVerified against the JDK24 members, 105,550 comparisons, 4 excludedAn unbounded binary min-heap: the head is always the least element, by natural ordering or by a comparator. offer
and poll are O(log n), peek is O(1).
import { PriorityQueue } from '@ylcnfrht/collections';
const pq = new PriorityQueue<number>();pq.offer(5);pq.offer(1);pq.offer(3);console.log(pq.peek()); // → 1console.log(pq.poll(), pq.poll(), pq.poll()); // → 1 3 5console.log(pq.poll()); // → nullimport { PriorityQueue, Comparator } from '@ylcnfrht/collections';
// due time, then priority, then submission order: the heap is not stable,// so the sequence number makes ties deterministicinterface Task { name: string; due: number; priority: number; seq: number }
const schedule = new PriorityQueue<Task>( Comparator.thenComparing( Comparator.comparing((t: Task) => t.due), Comparator.comparing((t: Task) => t.priority), Comparator.comparing((t: Task) => t.seq), ),);
let seq = 0;const submit = (name: string, due: number, priority: number) => schedule.offer({ name, due, priority, seq: seq++ });
submit('backup', 30, 2);submit('email', 10, 1);submit('report', 10, 0);submit('cleanup', 10, 1);
const ran: string[] = [];let t: Task | null;while ((t = schedule.poll()) !== null) ran.push(t.name);console.log(ran); // → [ 'report', 'email', 'cleanup', 'backup' ]Priority ordering
Section titled “Priority ordering”Without a comparator, natural ordering applies (see ordering); adding an object with no
natural ordering throws ClassCastException. Pass Comparator.reverseOrder() for a max-heap, or a key comparator
for objects. comparator() returns the comparator, or null for natural ordering. Ties come out in arbitrary order.
import { PriorityQueue, Comparator } from '@ylcnfrht/collections';
const pq = PriorityQueue.of(5, 1, 4, 2, 3);// with new:// const pq = new PriorityQueue<number>();// for (const n of [5, 1, 4, 2, 3]) pq.add(n);console.log(pq.toString()); // → [1, 2, 4, 5, 3]
// k largest: a min-heap of size k evicts the smallest, O(n log k)const top3 = new PriorityQueue<number>();for (const v of [5, 1, 9, 3, 7, 8, 2]) { top3.offer(v); if (top3.size() > 3) top3.poll();}console.log(top3.peek()); // → 7
const max = new PriorityQueue<number>(Comparator.reverseOrder<number>());[3, 9, 1].forEach((n) => max.offer(n));console.log(max.poll()); // → 9
try { new PriorityQueue<object>().add({});} catch (e) { console.log((e as Error).name); // → ClassCastException}LinkedList as a queue
Section titled “LinkedList as a queue”LinkedList implements Deque with O(1) end operations. Choose it over ArrayDeque only
when you also need the List API on the same object, or must store null (then check isEmpty() rather than
trusting poll()).
import { LinkedList } from '@ylcnfrht/collections';
const jobs = LinkedList.of('resize-1', 'resize-2', 'upload-1');// cancel a pending job by valueconsole.log(jobs.remove('resize-2')); // → trueconsole.log(jobs.poll()); // → resize-1
const withNull = new LinkedList<string | null>();withNull.add(null);console.log(withNull.poll(), withNull.isEmpty()); // → null trueLIFO view of a deque
Section titled “LIFO view of a deque”Collections.asLifoQueue(deque) returns a live Queue view whose add and offer push onto the front, so code that
takes a Queue processes items last-in-first-out. Its equals and hashCode use identity.
import { ArrayDeque, Collections } from '@ylcnfrht/collections';
const backing = new ArrayDeque<number>();const lifo = Collections.asLifoQueue(backing);lifo.add(1);lifo.add(2);lifo.add(3);console.log(lifo.poll()); // → 3console.log(backing.toString()); // → [2, 1]Creating a queue
Section titled “Creating a queue”| Form | Result |
|---|---|
new ArrayDeque<E>() |
empty deque with 16 slots |
new ArrayDeque<E>(n) |
empty deque sized for n elements (a hint, rounded up to a power of two) |
new ArrayDeque<E>(collection), ArrayDeque.of(a, b, c) |
deque of the elements, head first |
new PriorityQueue<E>(comparator?) |
empty queue; no comparator or null means natural ordering |
new PriorityQueue<E>(initialCapacity, comparator?) |
the same, with a capacity hint |
new PriorityQueue<E>(collection), PriorityQueue.of(a, b, c) |
heap built bottom-up in O(n); a PriorityQueue or sorted-set source passes on its comparator |
deque.clone() |
independent shallow copy of an ArrayDeque |
import { ArrayDeque, PriorityQueue, TreeSet, Comparator } from '@ylcnfrht/collections';
const c = ArrayDeque.of(1, 2, 3);// with new:// const c = new ArrayDeque<number>();// c.add(1);// c.add(2);// c.add(3);const e = c.clone();e.addLast(4);console.log(c.toString(), e.toString()); // → [1, 2, 3] [1, 2, 3, 4]
const desc = new TreeSet<number>(Comparator.reverseOrder<number>());desc.add(1);desc.add(3);console.log(new PriorityQueue(desc).poll()); // → 3Views and iteration
Section titled “Views and iteration”A deque iterates head to tail. descendingIterator() walks tail to head, and reversed() returns a
live reverse-ordered Deque whose writes go through. Iterators of all three
classes are fail-fast.
import { ArrayDeque } from '@ylcnfrht/collections';
const d = ArrayDeque.of(1, 2, 3);console.log(d.descendingIterator().next()); // → 3const rev = d.reversed();rev.addFirst(4); // = d.addLast(4)console.log(d.toString()); // → [1, 2, 3, 4]console.log(rev.peek()); // → 4Complexity
Section titled “Complexity”For LinkedList, see list complexity.
| Operation | ArrayDeque |
PriorityQueue |
|---|---|---|
insert (offer, add, push, addFirst, addLast) |
O(1) amortized | O(log n) |
remove head (poll, remove(), pop) |
O(1) | O(log n) |
remove tail (pollLast, removeLast) |
O(1) | — |
peek, element, size, isEmpty |
O(1) | O(1) |
contains, remove(o) |
O(n) | O(n) |
removeIf, removeAll, retainAll |
O(n) | O(n), then re-heapify |
| build from a collection | O(n) | O(n) |
reversed(), descendingIterator() |
O(1) | — |
drain in order with poll |
O(n) | O(n log n) |