Contents

The Queue interface provides two forms of each operation: throwing methods (add, remove, element) and null-returning methods (offer, poll, peek). Prefer the null-returning forms — they signal an empty queue without an exception and are safe in polling loops:

import java.util.*; // Queue interface — two forms of each operation: // Throws exception: add(), remove(), element() // Returns null/false: offer(), poll(), peek() ← prefer these Queue<String> q = new LinkedList<>(); // LinkedList implements Queue q.offer("first"); q.offer("second"); q.offer("third"); System.out.println(q.peek()); // "first" — head, does NOT remove System.out.println(q.poll()); // "first" — removes and returns head System.out.println(q.poll()); // "second" System.out.println(q.size()); // 1 // poll on empty queue returns null (no exception) Queue<String> empty = new LinkedList<>(); System.out.println(empty.poll()); // null // empty.remove() would throw NoSuchElementException // Iterating a queue drains it — use toArray() or copy first while (!q.isEmpty()) { System.out.println(q.poll()); // "third" } // Queue summary: // offer(e) — add to tail; returns false if capacity-restricted full // poll() — remove from head; returns null if empty // peek() — inspect head; returns null if empty // add(e) — offer() but throws IllegalStateException if full // remove() — poll() but throws NoSuchElementException if empty // element() — peek() but throws NoSuchElementException if empty

ArrayDeque is a resizable circular array that implements both Queue (FIFO via offerLast/pollFirst) and Deque (double-ended). It is faster than LinkedList for most queue and stack use cases due to better cache locality and no node allocation overhead:

// ArrayDeque — resizable circular array, faster than LinkedList // Implements both Queue (FIFO) and Deque (double-ended) // As a FIFO Queue Deque<String> queue = new ArrayDeque<>(); queue.offerLast("a"); // or offer() / add() queue.offerLast("b"); queue.offerLast("c"); System.out.println(queue.pollFirst()); // "a" — FIFO // As a LIFO Stack (replace java.util.Stack which is legacy) Deque<String> stack = new ArrayDeque<>(); stack.push("first"); // same as addFirst() stack.push("second"); stack.push("third"); System.out.println(stack.pop()); // "third" — LIFO System.out.println(stack.peek()); // "second" — top of stack // Double-ended operations Deque<Integer> deque = new ArrayDeque<>(); deque.offerFirst(1); // [1] deque.offerLast(2); // [1, 2] deque.offerFirst(0); // [0, 1, 2] deque.offerLast(3); // [0, 1, 2, 3] System.out.println(deque.peekFirst()); // 0 System.out.println(deque.peekLast()); // 3 deque.pollFirst(); // removes 0 deque.pollLast(); // removes 3 System.out.println(deque); // [1, 2] // ArrayDeque does NOT allow null elements // Use ArrayDeque instead of Stack (Stack extends Vector — legacy, synchronized) Prefer ArrayDeque over LinkedList for queue/stack use cases. ArrayDeque has better cache performance and lower memory overhead. Use ArrayDeque instead of the legacy Stack class, which is synchronized and slow.

PriorityQueue is a binary min-heap — poll() always removes the smallest element (by natural order or a supplied Comparator). Iteration order is unspecified; only poll() and peek() give ordered access. It is the standard choice for top-K and task scheduling problems:

// PriorityQueue — min-heap by default (smallest element polls first) PriorityQueue<Integer> minHeap = new PriorityQueue<>(); minHeap.offer(30); minHeap.offer(10); minHeap.offer(20); System.out.println(minHeap.peek()); // 10 — minimum System.out.println(minHeap.poll()); // 10 — removes minimum System.out.println(minHeap.poll()); // 20 System.out.println(minHeap.poll()); // 30 // Max-heap — reverse natural order PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder()); maxHeap.offer(30); maxHeap.offer(10); maxHeap.offer(20); System.out.println(maxHeap.poll()); // 30 — maximum first // Custom objects — priority by some field record Task(String name, int priority) {} PriorityQueue<Task> tasks = new PriorityQueue<>( Comparator.comparingInt(Task::priority)); tasks.offer(new Task("Low", 3)); tasks.offer(new Task("High", 1)); tasks.offer(new Task("Medium", 2)); while (!tasks.isEmpty()) { System.out.println(tasks.poll().name()); // High, Medium, Low } // PriorityQueue does NOT guarantee order when iterating — only poll() is ordered for (Integer i : minHeap) { System.out.print(i + " "); // order is NOT guaranteed — use poll() } // Find k-largest elements using a min-heap of size k int[] nums = {3, 1, 4, 1, 5, 9, 2, 6, 5}; int k = 3; PriorityQueue<Integer> kLargest = new PriorityQueue<>(k); for (int n : nums) { kLargest.offer(n); if (kLargest.size() > k) kLargest.poll(); // remove smallest } System.out.println(kLargest); // [5, 6, 9] in heap order (not sorted)

BlockingQueue extends Queue with blocking operations: put() blocks when the queue is full, take() blocks when it is empty. This makes it the canonical building block for producer-consumer patterns without explicit locks or condition variables:

import java.util.concurrent.*; // BlockingQueue — thread-safe; blocks on put() when full, take() when empty // Producer-consumer pattern BlockingQueue<String> bq = new LinkedBlockingQueue<>(10); // capacity 10 // Producer thread Thread producer = new Thread(() -> { try { bq.put("task1"); // blocks if full bq.put("task2"); bq.put(null); // ILLEGAL — null not allowed in BlockingQueue } catch (InterruptedException e) { Thread.currentThread().interrupt(); } }); // Consumer thread Thread consumer = new Thread(() -> { try { String task; while ((task = bq.poll(1, TimeUnit.SECONDS)) != null) { System.out.println("Processing: " + task); } } catch (InterruptedException e) { Thread.currentThread().interrupt(); } }); // Non-blocking offer with timeout boolean accepted = bq.offer("urgent", 500, TimeUnit.MILLISECONDS); // Common implementations: // LinkedBlockingQueue — optionally bounded, linked nodes // ArrayBlockingQueue — always bounded, array-backed, fair option // PriorityBlockingQueue — unbounded, priority ordered, concurrent // SynchronousQueue — no storage; each put blocks until a take // DelayQueue — elements become available after a delay // SynchronousQueue — handoff channel (zero capacity) BlockingQueue<String> sync = new SynchronousQueue<>(); // put() blocks until another thread calls take() — perfect for direct handoff BlockingQueue implementations do NOT permit null elements — null is used as a sentinel value by poll() and peek() to signal an empty queue.

The monotone (monotonic) deque is a classic algorithmic pattern: maintain a Deque of indices in decreasing-value order to answer sliding-window maximum queries in O(n). The deque is also useful for palindrome checks and BFS traversal:

// Monotone deque — classic sliding window maximum // Find maximum in every window of size k int[] nums = {1, 3, -1, -3, 5, 3, 6, 7}; int k = 3; int[] result = new int[nums.length - k + 1]; Deque<Integer> dq = new ArrayDeque<>(); // stores indices for (int i = 0; i < nums.length; i++) { // Remove elements outside the window while (!dq.isEmpty() && dq.peekFirst() < i - k + 1) { dq.pollFirst(); } // Remove smaller elements — they can never be the max while (!dq.isEmpty() && nums[dq.peekLast()] < nums[i]) { dq.pollLast(); } dq.offerLast(i); if (i >= k - 1) { result[i - k + 1] = nums[dq.peekFirst()]; } } System.out.println(Arrays.toString(result)); // [3, 3, 5, 5, 6, 7] // Palindrome check using Deque String s = "racecar"; Deque<Character> chars = new ArrayDeque<>(); for (char c : s.toCharArray()) chars.offer(c); boolean isPalindrome = true; while (chars.size() > 1) { if (!chars.pollFirst().equals(chars.pollLast())) { isPalindrome = false; break; } } System.out.println(isPalindrome); // true // BFS using Queue // void bfs(Node root) { // Queue<Node> queue = new ArrayDeque<>(); // queue.offer(root); // while (!queue.isEmpty()) { // Node node = queue.poll(); // // process node // for (Node child : node.children) queue.offer(child); // } // }