Java Queue and Deque: ArrayDeque, PriorityQueue, and Blocking Queues

Queue models a FIFO (first-in, first-out) buffer; Deque (double-ended queue) allows addition and removal at both ends, making it suitable for both FIFO queues and LIFO stacks. ArrayDeque is the go-to general-purpose implementation: faster than LinkedList for most use cases. PriorityQueue orders elements by natural ordering or a comparator. For concurrent code, BlockingQueue implementations like LinkedBlockingQueue are indispensable.

Share

Contents

Queue API: offer, poll, peek

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:

Java
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: Stack and Queue

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:

Java
// 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: Heap-based Ordering

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:

Java
// 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 for Concurrency

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:

Java
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.

Deque Patterns: Sliding Window, Monotone 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:

Java
// 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);
//     }
// }

Related articles

All Java articles →
Java PriorityQueue: Heaps & Priority-Based ProcessingJava PriorityQueue: min-heap internals, max-heap with Comparator, offer/poll/peek, time complexity, top-K elements, task scheduling, and Dijkstra's algorithm patterns.Java BlockingQueue: Linked, Array and SynchronousQueueBlockingQueue in Java: LinkedBlockingQueue, ArrayBlockingQueue, SynchronousQueue, PriorityBlockingQueue, DelayQueue, and producer-consumer patterns.Java CopyOnWriteArrayList and Concurrent CollectionsJava CopyOnWriteArrayList, ConcurrentHashMap, and concurrent collections. Covers snapshot iterators, ConcurrentSkipListMap, ConcurrentLinkedQueue, and when to use each.ArrayList vs LinkedList: When to Use EachArrayList vs LinkedList in Java: time complexity comparison, memory layout, when to use each, and why ArrayList wins most of the time.