Queue, Deque, PriorityQueue & Comparable/Comparator

Ordering for processing

Queue<E> adds elements for ordered retrieval. The exam-relevant point is its non-throwing method pair, which returns a special value instead of an exception when the queue is empty:

- offer(e) — add to the tail (returns false if capacity-bound and full). - poll() — remove & return the head, or null if empty. - peek() — look at the head without removing, or null if empty.

(The older add/remove/element trio throws on failure instead.)

- ArrayDeque — the recommended general FIFO queue *and* the recommended stack (use it instead of the legacy java.util.Stack). As a stack: push, pop, peek. As a queue: offer, poll. - LinkedList — also implements Queue/Deque. - PriorityQueue — a heap: poll() always returns the smallest element by ordering, not the oldest. Not FIFO.

Natural order vs custom order

Two distinct interfaces define ordering, and the exam tests the difference:

- Comparable<T> — a type's natural order, defined *inside* the class: int compareTo(T other). String, Integer, etc. implement it. Collections.sort(list), TreeSet, and a no-comparator PriorityQueue all use it. - Comparator<T> — an external, swappable order: int compare(a, b). Pass one to Collections.sort(list, cmp), Arrays.sort, a TreeSet, or a PriorityQueue when you want an order *other than* natural, or when the type has no natural order.

Both return negative if the first argument should come first, zero if equal, positive otherwise. Use Integer.compare(x, y) (never x - y, which overflows) and chain with Comparator.comparing(...).thenComparing(...).

Worked example. A PriorityQueue<Event> ordered by a Comparator on each event's scheduled time, so poll() always returns the soonest event — exactly the discipline a scheduler (like the Greenhouse controller's event timeline) needs:

PriorityQueue<Event> schedule =
    new PriorityQueue<>(Comparator.comparingLong(Event::getTime));
schedule.offer(new LightOn(500));
schedule.offer(new Bell(200));
Event soonest = schedule.poll();   // the Bell (time 200) comes out first

Here the comparator extracts a long time from each event; the heap keeps the minimum on top, so poll() returns the earliest-scheduled event regardless of insertion order.