library
intermediatePriorityQueue & Deque
Use priority-based and double-ended queue implementations for scheduling, BFS, and stack/queue patterns.
PriorityQueue and Deque are Queue implementations with different ordering guarantees:
PriorityQueue = hospital ER triage (most urgent patient seen first, not first-come-first-served). Deque = a double-door hallway (enter/exit from either end).
Key Concepts
1
PriorityQueue: a min-heap by default. Elements are ordered by natural ordering (Comparable) or a Comparator. poll() always returns the smallest element. NOT FIFO — it's priority-ordered.
2
Time complexity: offer/poll O(log n), peek O(1). Not synchronized.
3
Key: PriorityQueue does NOT guarantee sorted iteration order — only peek/poll return the minimum. Iterating may visit elements in any order.
4
Deque (Double-Ended Queue): allows insertion and removal at both ends. Two implementations:
- ArrayDeque: resizable array, faster than LinkedList for both stack and queue use
- LinkedList: doubly-linked list, implements both List and Deque
5
Use ArrayDeque as:
- Stack: push/pop/peek (LIFO) — faster than java.util.Stack
- Queue: offer/poll/peek (FIFO) — faster than LinkedList
- Deque: offerFirst/offerLast, pollFirst/pollLast
6
ArrayDeque doesn't allow null elements. LinkedList does, but nulls cause ambiguity (poll returns null for both 'empty' and 'null element').