5.4 Queue & Deque Implementations: PriorityQueue vs ArrayDeque

← Back to Chapter 5: Collections Framework

Queues model sequences prioritized for processing prior to execution.

---

1. Queue vs Deque Interface Contracts

Method	Throws Exception on Failure	Returns Special Value (false / null)
Insert	add(e)	offer(e)
Remove	remove()	poll()
Examine	element()	peek()

A Deque (Double-Ended Queue) extends Queue, adding symmetrical methods on both boundaries: addFirst/addLast, pollFirst/pollLast, peekFirst/peekLast.

---

2. ArrayDeque: High-Performance Resizing Circular Array

• Backed by an array Object[] elements with head and tail pointers that wrap around modulo the array length.
• Null Forbidden: Does not permit null elements (returns null from poll() as an empty indicator).
• Stack & Queue Superiority: Faster than Stack (no synchronized locks) and faster than LinkedList (no node objects, superb CPU cache locality).

Deque<String> stack = new ArrayDeque<>();
stack.push("Frame1"); // LIFO push
stack.push("Frame2");
String top = stack.pop(); // Returns "Frame2"

---

3. PriorityQueue: Binary Min-Heap

• Elements are ordered according to natural ordering or an explicit Comparator.
• The head of the queue is always the minimum element according to the comparator.
• Internal structure: Complete binary tree stored inside Object[] queue.
  • Left child of index k: 2k + 1
  • Right child of index k: 2k + 2
  • Parent of index k: (k - 1) >>> 1
• Complexity:
  • offer(): O(log n) (sift-up)
  • poll(): O(log n) (sift-down)
  • peek(): O(1)