11.4 Queue, Deque, and PriorityQueue

While List is an ordered collection managed by index, Queue and Deque restrict the direction of data insertion and removal. They are fundamental data structures in algorithms and system design.

1. Queue - FIFO

First In, First Out— the first element added is the first one removed, like a waiting line at a bank.

Input → [C] [B] [A] → Output
           ^Input      ^Output

Queue Interface Key Methods

Method	Behavior	On Failure
offer(e)	Add element	Returns false
poll()	Remove and return front	Returns null
peek()	View front (no removal)	Returns null
add(e)	Add element	Throws exception
remove()	Remove and return front	Throws exception

import java.util.LinkedList;
import java.util.Queue;

Queue<String> queue = new LinkedList<>();

// Add to back
queue.offer("First");
queue.offer("Second");
queue.offer("Third");

System.out.println(queue.peek());   // "First" (no removal)
System.out.println(queue.poll());   // "First" (removed)
System.out.println(queue.poll());   // "Second"
System.out.println(queue);          // [Third]
System.out.println(queue.poll());   // "Third"
System.out.println(queue.poll());   // null (empty queue)

Practical Example: BFS (Breadth-First Search)

Queue is the core data structure behind BFS (Breadth-First Search) algorithms.

import java.util.*;

public class BFSExample {
    // Graph: each node and its connected neighbors
    static Map<Integer, List<Integer>> graph = new HashMap<>();

    static {
        graph.put(1, Arrays.asList(2, 3));
        graph.put(2, Arrays.asList(4, 5));
        graph.put(3, Arrays.asList(6));
        graph.put(4, Collections.emptyList());
        graph.put(5, Collections.emptyList());
        graph.put(6, Collections.emptyList());
    }

    static void bfs(int start) {
        Queue<Integer> queue = new LinkedList<>();
        Set<Integer> visited = new HashSet<>();

        queue.offer(start);
        visited.add(start);

        while (!queue.isEmpty()) {
            int node = queue.poll();
            System.out.print(node + " ");

            for (int neighbor : graph.get(node)) {
                if (!visited.contains(neighbor)) {
                    queue.offer(neighbor);
                    visited.add(neighbor);
                }
            }
        }
    }

    public static void main(String[] args) {
        bfs(1); // Output: 1 2 3 4 5 6
    }
}

---

2. Deque - Double-Ended Queue

Double Ended Queue— supports adding and removing at both ends(front and rear). It combines the functionality of both Stack and Queue.

     ^Add to front    ^Add to rear
[A] [B] [C] [D]
^Remove from front   ^Remove from rear

import java.util.ArrayDeque;
import java.util.Deque;

Deque<String> deque = new ArrayDeque<>();

// Add to rear (Queue style)
deque.offerLast("B");
deque.offerLast("C");

// Add to front (Stack style)
deque.offerFirst("A");

System.out.println(deque); // [A, B, C]

System.out.println(deque.pollFirst());  // "A" (remove from front)
System.out.println(deque.pollLast());   // "C" (remove from rear)
System.out.println(deque.peekFirst());  // "B" (view front, no removal)

Using Deque as a Stack

Java's Stack class is a legacy class. Using ArrayDeque as a stack is the modern recommended approach.

Deque<Integer> stack = new ArrayDeque<>();

stack.push(1); // same as offerFirst
stack.push(2);
stack.push(3);

System.out.println(stack.pop());  // 3 (LIFO - Last In First Out)
System.out.println(stack.pop());  // 2
System.out.println(stack.peek()); // 1 (no removal)

Practical Example: Bracket Validation (Stack Usage)

public static boolean isValidBracket(String s) {
    Deque<Character> stack = new ArrayDeque<>();

    for (char c : s.toCharArray()) {
        if (c == '(' || c == '{' || c == '[') {
            stack.push(c);
        } else {
            if (stack.isEmpty()) return false;
            char top = stack.pop();
            if (c == ')' && top != '(') return false;
            if (c == '}' && top != '{') return false;
            if (c == ']' && top != '[') return false;
        }
    }

    return stack.isEmpty();
}

System.out.println(isValidBracket("({[]})"));  // true
System.out.println(isValidBracket("([)]"));    // false
System.out.println(isValidBracket("{[}"));     // false

---

3. PriorityQueue

While a regular Queue is FIFO, PriorityQueue returns the highest-priority element first. Internally it is implemented using a heap data structure.

import java.util.PriorityQueue;

// Default: ascending order (smallest value comes first)
PriorityQueue<Integer> pq = new PriorityQueue<>();

pq.offer(30);
pq.offer(10);
pq.offer(20);

System.out.println(pq.poll()); // 10 (smallest)
System.out.println(pq.poll()); // 20
System.out.println(pq.poll()); // 30

Custom Priority with Comparator

// Descending order (largest value first)
PriorityQueue<Integer> descPq = new PriorityQueue<>(Comparator.reverseOrder());
descPq.offer(10);
descPq.offer(30);
descPq.offer(20);
System.out.println(descPq.poll()); // 30

// Custom priority for objects
record Task(String name, int priority) {}

PriorityQueue<Task> taskQueue = new PriorityQueue<>(
    Comparator.comparingInt(Task::priority) // lower priority number = higher urgency
);

taskQueue.offer(new Task("Normal Task",   3));
taskQueue.offer(new Task("Urgent Task",   1));
taskQueue.offer(new Task("Important Task",2));

while (!taskQueue.isEmpty()) {
    System.out.println(taskQueue.poll().name());
}
// Output:
// Urgent Task
// Important Task
// Normal Task

---

Pro Tips

Data structure selection guide:

Use Case	Best Choice
General FIFO queue	ArrayDeque (faster than LinkedList)
Stack (LIFO)	ArrayDeque (avoid the Stack class)
Insert/remove at both ends	ArrayDeque
Priority-based processing	PriorityQueue

ArrayDeque is generally faster than LinkedList for queue use cases. Being array-backed, it has better cache locality and no per-node object allocation overhead. Much existing code uses LinkedList as a Queue — prefer ArrayDeque for new code.