Queues, deques and priority queues

List, Map and Set cover most days. The remaining shapes answer a different question: not "what is in here?" but "what should I do next?"

Queue: first in, first out

Work arrives, work is handled in order.

Queue<Delivery> pending = new ArrayDeque<>();

pending.offer(delivery);          // add to the back
Delivery next = pending.poll();   // take from the front, null if empty
Delivery peek = pending.peek();   // look without taking, null if empty

Every Queue method comes in two flavours, and choosing correctly matters:

Use the second column. An empty queue is a completely normal state, and poll() returning null is easier to handle than catching NoSuchElementException:

Delivery next;
while ((next = pending.poll()) != null) {
    process(next);
}

The first column is right only when an empty queue genuinely means a bug.

Deque: both ends

A double-ended queue — push and pop at either end. It is the most useful of these and the one to default to.

Deque<Delivery> deque = new ArrayDeque<>();

deque.addFirst(urgent);     // jump the queue
deque.addLast(normal);      // join the back
Delivery front = deque.pollFirst();
Delivery back = deque.pollLast();

It is also your stack

Deque<String> undo = new ArrayDeque<>();
undo.push("added Priya");     // == addFirst
undo.push("added Arjun");
String last = undo.pop();     // "added Arjun" — == pollFirst

Do not use java.util.Stack. It extends Vector, so every method is synchronized whether you want it or not, and — worse — it iterates in the wrong order, from the bottom up rather than the top down. It is a 1995 class kept for compatibility. ArrayDeque is faster and correct.

Likewise, do not use LinkedList as a queue out of habit. ArrayDeque is faster for essentially every queue and stack operation, because it is a circular array rather than a chain of node objects — one allocation instead of one per element, and contiguous memory the CPU cache can actually use.

The one thing ArrayDeque will not do is hold null, because null is its "empty" signal from poll() and peek(). That is a feature, not a limitation.

PriorityQueue: most important first

Not insertion order — priority order, decided by a Comparator.

// Deliveries with the most tiffins first, because they take longest to pack.
Queue<Delivery> queue = new PriorityQueue<>(
        Comparator.comparingInt(Delivery::tiffins).reversed());

queue.offer(new Delivery(date, "Priya", 2));
queue.offer(new Delivery(date, "Arjun", 7));
queue.offer(new Delivery(date, "Kavita", 1));

queue.poll();   // Arjun, 7
queue.poll();   // Priya, 2
queue.poll();   // Kavita, 1

Two things surprise people, and both follow from it being a binary heap:

Iterating does not give you sorted order. Only poll() does.

for (Delivery d : queue) { … }        // heap order, which looks arbitrary
System.out.println(queue);            // likewise — not sorted

The heap only guarantees that the head is the smallest. If you want everything in order, poll until empty, or sort a copy.

Ties are broken arbitrarily. Two deliveries with the same count come out in no defined order. If that matters, add a tiebreaker to the comparator — the same rule as pagination in the full-stack course:

Comparator.comparingInt(Delivery::tiffins).reversed()
        .thenComparing(Delivery::date)

Cost is O(log n) to insert and to remove the head, O(1) to peek. That is what makes it the right tool for a scheduler, a top-N, or anything where you repeatedly want "the next most important".

Top-N without sorting everything

A genuinely useful trick:

// The five busiest days, from a million deliveries, without sorting a million.
PriorityQueue<Delivery> topFive = new PriorityQueue<>(
        Comparator.comparingInt(Delivery::tiffins));   // smallest at the head

for (Delivery d : allDeliveries) {
    topFive.offer(d);
    if (topFive.size() > 5) {
        topFive.poll();      // drop the smallest
    }
}

Keep the smallest at the head so the weakest candidate is the one evicted. O(n log 5) instead of O(n log n), and constant memory.

LinkedHashMap and LinkedHashSet

Not queues, but they solve the ordering problem people usually reach for a list to solve.

Map<String, Integer> counts = new LinkedHashMap<>();   // insertion order kept
Set<String> customers = new LinkedHashSet<>();         // likewise

A HashMap has no order and its iteration order can change between runs and between JVM versions. If your output needs to be stable — a report, a test assertion, anything a human reads — use the Linked variant. It costs a little memory for the linked list of entries and nothing in lookup time.

And a LinkedHashMap can be told to evict:

// An LRU cache in six lines.
Map<String, Rates> cache = new LinkedHashMap<>(16, 0.75f, true) {
    @Override
    protected boolean removeEldestEntry(Map.Entry<String, Rates> eldest) {
        return size() > 100;
    }
};

The true is access-order rather than insertion-order, so reading an entry moves it to the end. That is a least-recently-used cache, and it is worth knowing it exists before you reach for a library.

Which one

ArrayDeque appears four times, which is the point. When in doubt, it is ArrayDeque.

Check your work

Why prefer offer/poll/peek: an empty queue is normal, and a null is easier to handle than an exception.

Why not java.util.Stack: it extends Vector, is needlessly synchronized, and iterates bottom-up.

Why not LinkedList as a queue: ArrayDeque is a circular array — one allocation, cache-friendly — rather than a node per element.

Why ArrayDeque forbids null: null is the empty signal for poll and peek.

Why iterating a PriorityQueue is not sorted: it is a heap, and only the head is guaranteed.

How to get the top N cheaply: a PriorityQueue of size N with the smallest at the head, evicting as you go.

Why LinkedHashMap for output: HashMap order is unspecified and can change between runs and JVM versions.

What the true in LinkedHashMap's constructor does: access order, which with removeEldestEntry gives you an LRU cache.

Practice

1. Fill an ArrayDeque as a queue and drain it with the while ((x = poll()) != null) loop.
2. Call remove() on an empty ArrayDeque and read the exception. Then poll().
3. Use the same ArrayDeque as a stack with push/pop. Confirm the order.
4. Do the same with java.util.Stack, then iterate both and compare the order.
5. Put three deliveries in a PriorityQueue ordered by tiffins. Print the queue directly, then poll them all. Explain the difference.
6. Add two deliveries with equal tiffins and poll repeatedly across several runs. Then add a tiebreaker.
7. Implement top-5 over 100,000 random deliveries with a PriorityQueue. Time it against sorting the whole list.
8. Put ten entries in a HashMap and a LinkedHashMap and print both. Run it three times.
9. Build the LRU cache above with a limit of 3. Access an old key and confirm it survives the next eviction.
10. Try to add null to an ArrayDeque, then to a LinkedList. Explain the difference.

Next: the contract that makes HashMap and HashSet work at all.