Working with Queue and Deque
1. Understanding Queue Interface
| Method | Throws on Failure | Returns Special Value |
|---|---|---|
| Insert | add(e) | offer(e) |
| Remove | remove() | poll() |
| Examine | element() | peek() |
2. Using PriorityQueue
Example: Priority queue
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(5); pq.offer(1); pq.offer(3);
pq.poll(); // 1 (min-heap)
PriorityQueue<Task> byPriority =
new PriorityQueue<>(Comparator.comparingInt(Task::priority).reversed());| Property | Detail |
|---|---|
| Order | Natural or comparator (min-heap) |
| Iteration | NOT in priority order |
| Complexity | offer/poll O(log n), peek O(1) |
3. Using ArrayDeque
| Property | Detail |
|---|---|
| Backing | Resizable circular array |
| Null | Not allowed |
| Use | Default Deque/Stack/Queue choice |
| Faster than | Stack and LinkedList |
4. Using LinkedList as Queue
| Aspect | Detail |
|---|---|
| Implements | List, Deque, Queue |
| Allows null | Yes |
| Recommended over | Less than ArrayDeque (slower) |
5. Using offer(), poll(), peek() Methods
| Method | Empty/Full Behavior |
|---|---|
offer(e) | Returns false if cannot insert |
poll() | Returns null if empty |
peek() | Returns null if empty |
6. Understanding Deque Interface
| Operation | First-end | Last-end |
|---|---|---|
| Insert (throws) | addFirst | addLast |
| Insert (returns) | offerFirst | offerLast |
| Remove (throws) | removeFirst | removeLast |
| Remove (returns) | pollFirst | pollLast |
| Examine | peekFirst | peekLast |
7. Using addFirst(), addLast() Methods
| Method | Throws |
|---|---|
addFirst(e) | IllegalStateException if capacity-restricted & full |
addLast(e) | Same |
8. Using removeFirst(), removeLast() Methods
| Method | Throws |
|---|---|
removeFirst() | NoSuchElementException if empty |
removeLast() | NoSuchElementException if empty |
9. Using Deque as Stack
| Stack Op | Deque Equivalent |
|---|---|
push(e) | addFirst(e) |
pop() | removeFirst() |
peek() | peekFirst() |
10. Using Deque as Queue
| Queue Op | Deque Equivalent |
|---|---|
offer(e) | offerLast(e) |
poll() | pollFirst() |
peek() | peekFirst() |