Collections Queue — PriorityQueue, ArrayDeque, and BlockingQueue Implementations

In this tutorial, you will learn about Collections Queue. We cover key concepts, practical examples, and best practices to help you master this topic.

Java Queue and Deque interfaces represent collections for holding elements prior to processing, with FIFO, priority, and LIFO semantics. Queues are fundamental to producer-consumer patterns, task scheduling, and breadth-first search — wherever elements must be processed in a specific order.

What You'll Learn

• Queue interface: FIFO processing
• PriorityQueue: element ordering by priority
• ArrayDeque: double-ended queue (stack + queue)
• BlockingQueue: thread-safe producer-consumer

Why It Matters

Queues decouple producers from consumers — one part of the system adds tasks, another processes them. Choosing the right queue type affects throughput, ordering guarantees, and Thread Safety.

Real-World Use

Thread pools use BlockingQueue to hold waiting tasks. Web servers queue incoming requests. Dijkstra's algorithm uses PriorityQueue. Undo/redo operations use Deque as a stack.

The Queue Interface

Queue<String> queue = new LinkedList<>();
queue.offer("First");
queue.offer("Second");
queue.offer("Third");

String head = queue.peek();  // "First" (retrieve but not remove)
String processed = queue.poll(); // "First" (retrieve and remove)
int size = queue.size();     // 2

// Alternative throwing methods:
queue.element(); // throws NoSuchElementException if empty
queue.remove();  // throws NoSuchElementException if empty

PriorityQueue

Elements are ordered by priority (natural order or Comparator):

Queue<Integer> pq = new PriorityQueue<>();
pq.offer(5);
pq.offer(1);
pq.offer(3);
pq.offer(7);

while (!pq.isEmpty()) {
    System.out.print(pq.poll() + " ");
}
// Output: 1 3 5 7

Custom Priority

Queue<Task> tasks = new PriorityQueue<>(
    Comparator.comparingInt(Task::priority).reversed()
);

Min-Heap Behavior

PriorityQueue is a min-heap — the smallest element (according to ordering) is always at the head. To get max-heap behavior, use Comparator.reverseOrder().

Performance

• O(log n) for offer() and poll()
• O(1) for peek()
• O(n) for remove(Object) and contains()

The Deque Interface

Deque (double-ended queue) supports insertion/removal at both ends:

Deque<String> deque = new ArrayDeque<>();
deque.addFirst("First");
deque.addLast("Last");
deque.offerFirst("New First");
deque.offerLast("New Last");

String first = deque.getFirst();  // "New First"
String last = deque.getLast();    // "New Last"
deque.removeFirst();
deque.removeLast();

ArrayDeque as Stack

Deque<String> stack = new ArrayDeque<>();
stack.push("Bottom");
stack.push("Middle");
stack.push("Top");

String top = stack.peek();  // "Top"
String popped = stack.pop(); // "Top" (LIFO)

ArrayDeque is faster than Stack (legacy class) and faster than LinkedList as a stack or queue because it uses a circular array.

ArrayDeque as Queue

Deque<String> queue = new ArrayDeque<>();
queue.add("First");    // adds to end
queue.add("Second");
queue.add("Third");

String first = queue.remove(); // removes from front (FIFO)

BlockingQueue (Concurrent)

BlockingQueue extends Queue with thread-safe blocking operations:

BlockingQueue<String> queue = new LinkedBlockingQueue<>(100);

// Producer thread
queue.put("item"); // blocks if full

// Consumer thread
String item = queue.take(); // blocks if empty

Implementations

Producer-Consumer Example

BlockingQueue<Integer> queue = new ArrayBlockingQueue<>(10);

// Producer
Runnable producer = () -> {
    try {
        for (int i = 0; i < 100; i++) {
            queue.put(i);
            Thread.sleep(50);
        }
    } catch (InterruptedException e) {
        Thread.currentThread().interrupt();
    }
};

// Consumer
Runnable consumer = () -> {
    try {
        while (true) {
            Integer item = queue.take();
            System.out.println("Processed: " + item);
        }
    } catch (InterruptedException e) {
        Thread.currentThread().interrupt();
    }
};

Queue Implementations Summary

Common Mistakes

1. Using PriorityQueue with mutable elements that change ordering. The heap property is not maintained if an element's priority changes after insertion.
2. Using LinkedList as a queue in multi-threaded code. LinkedList is not thread-safe. Use ConcurrentLinkedQueue or LinkedBlockingQueue.
3. Forgetting that PriorityQueue Iterator does not guarantee order. Only poll(), peek(), and remove() respect the priority order.
4. Using Stack class instead of ArrayDeque. Stack extends Vector and is legacy. ArrayDeque is faster and more complete.
5. Calling add() on a full BlockingQueue. add() throws IllegalStateException when the queue is full. Use offer(), put(), or offer(timeout).

Practice Questions

1. What is the difference between Queue and Deque?
Queue allows insertion at one end and removal at the other (FIFO). Deque allows insertion and removal at both ends (FIFO and LIFO).

2. How does PriorityQueue determine element ordering?
By natural ordering (Comparable) or a provided Comparator. The head is the smallest element.

3. What does take() do on a BlockingQueue?
Retrieves and removes the head, waiting (blocking) if necessary until an element becomes available.

4. Why is ArrayDeque preferred over Stack?
ArrayDeque is faster (no synchronization), supports both stack and queue operations, and is not a legacy class.

5. What happens when you offer an element to a full ArrayBlockingQueue?
offer() returns false. put() blocks until space is available. add() throws IllegalStateException.

Challenge Question:
Implement a simple thread-safe task scheduler using PriorityBlockingQueue. Tasks implement Comparable based on scheduled time. A worker thread polls the queue and executes tasks when their scheduled time arrives. Support scheduling with a delay and periodic tasks.

FAQ

Mini Project

Write a program QueueDemo.java that:

1. Creates a PriorityQueue of emergency room patients ordered by severity (highest first)
2. Processes patients in priority order and prints the treatment order
3. Creates an ArrayDeque and uses it as both a stack (undo operations) and a queue (print job queue)
4. Implements a simple producer-consumer with ArrayBlockingQueue (capacity 5), two producer threads and one consumer thread, running for 10 iterations
5. Measures offer() vs add() behavior on a full bounded queue
6. Demonstrates DelayQueue with delayed tasks that become available after a specified delay

What's Next

Collections enable type-safe storage, but even better is making them work with any type. Lesson 27 introduces generics — type parameters, wildcards, bounded type parameters, type erasure, and the PECS principle.