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.