AtticOverview
FIFO, LIFO, and priority queue implementations, method families, and quick selection guide
Java's Queue<E> and Deque<E> structure elements around head and tail access. They provide multiple concrete implementations and parallel method families to handle boundary conditions cleanly.
Queue<E> (Core FIFO & Priority Contract)
├── ArrayDeque ──────➔ Contiguous circular array (Default FIFO Queue & LIFO Stack)
├── LinkedList ──────➔ Doubly-linked nodes (Use for nulls or O(1) node removal)
├── PriorityQueue ───➔ Dynamic binary heap (Min/Max priority ordering)
└── BlockingQueue ───➔ Thread-safe concurrent queues (Producer-Consumer pipelines)Queue Implementations: When to Use Which
| Implementation | Underlying Structure | Head / Tail Ops | When to Use (Best For) | When to Avoid |
|---|---|---|---|---|
ArrayDeque | Circular dynamic array | O(1) | Default choice for FIFO queues, LIFO stacks, and sliding windows | Need priority sorting or multi-thread safety |
LinkedList | Doubly-linked discrete nodes | O(1) | Strictly require storing null or need O(1) node removal via external reference | General queues/stacks (high GC churn, poor CPU cache locality) |
PriorityQueue | Dynamic binary heap array | O(log n) | Priority scheduling, top-K selection, continuous min/max | Need strict FIFO arrival order |
BlockingQueue | Thread-safe concurrent buffer | O(1) | Multi-threaded producer-consumer queues (ArrayBlockingQueue, etc.) | Single-threaded apps (locking overhead) |
Quick Decision Rule:
├── Need Priority / Sorted Order? ─➔ PriorityQueue
├── Multi-threaded Producers? ────➔ BlockingQueue
└── Standard FIFO Queue or Stack? ─➔ ArrayDeque (almost always better than LinkedList)Method Types: Why Dual Methods and When to Use Which
Queue operations encounter two normal boundary conditions:
- Full queues (capacity limit reached on bounded queues)
- Empty queues (reading from an empty queue)
To avoid forcing costly try/catch exceptions for standard flow control, Java defines two parallel method families for every operation:
| Core Operation | Safe Method (Returns Value) | Strict Method (Throws Exception) | Return Type | When to Use Which |
|---|---|---|---|---|
| Insert / Enqueue | offer(e) ➔ returns false if full | add(e) ➔ throws IllegalStateException | boolean | Use offer for bounded buffers; use add if a full queue indicates an illegal state |
| Remove / Dequeue | poll() ➔ returns null if empty | remove() ➔ throws NoSuchElementException | E | Use poll for consumer loops (while (!q.isEmpty())); use remove when head must exist |
| Examine / Inspect | peek() ➔ returns null if empty | element() ➔ throws NoSuchElementException | E | Use peek to safely inspect; use element when an empty queue is a critical bug |
Quick Rule: Always default to the Safe Family (offer, poll, peek) for normal control
flow and consumer loops. Reserve the Strict Family (add, remove, element) strictly for
asserting state invariants where unexpected capacity or emptiness indicates a program bug.
Queue & Deque Toolkit Reference
The primary operational methods across Queue<E> and Deque<E>:
| Method | Parameters | Return Type | Role / Interface | Failure Behavior |
|---|---|---|---|---|
offer(e) | (E e) | boolean | Queue (Enqueue) | Returns false if capacity full |
poll() | none | E | Queue (Dequeue) | Returns null if queue empty |
peek() | none | E | Queue (Inspect) | Returns null if queue empty |
add(e) | (E e) | boolean | Queue (Strict insert) | Throws IllegalStateException if full |
remove() | none | E | Queue (Strict remove) | Throws NoSuchElementException if empty |
element() | none | E | Queue (Strict inspect) | Throws NoSuchElementException if empty |
offerFirst(e) | (E e) | boolean | Deque (Head insert) | Returns false if capacity full |
offerLast(e) | (E e) | boolean | Deque (Tail insert) | Returns false if capacity full |
pollFirst() | none | E | Deque (Head remove) | Returns null if empty |
pollLast() | none | E | Deque (Tail remove) | Returns null if empty |
peekFirst() | none | E | Deque (Head inspect) | Returns null if empty |
peekLast() | none | E | Deque (Tail inspect) | Returns null if empty |
push(e) | (E e) | void | Deque (LIFO Stack push) | Inserts at head (addFirst) |
pop() | none | E | Deque (LIFO Stack pop) | Removes from head (removeFirst); throws if empty |
isEmpty() | none | boolean | Collection | true if size is 0 |
size() | none | int | Collection | Total active elements |
Detailed Guides
Queue Contract
Dual-method architecture, parallel throwing vs sentinel families, and Deque symmetry
ArrayDeque
Circular ring buffer mechanics, Stack and Queue personas, and sliding window patterns
LinkedList Queue
Doubly-linked FIFO queue and Deque, heap node allocation overhead, and cache locality trade-offs
PriorityQueue
Binary min/max-heap mechanics, siftUp/siftDown algorithms, custom Comparators, and top-K patterns