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.

Queue Interface Key Methods

Method	Action	On Failure
offer(e)	Add element	Returns false
poll()	Remove and return front	Returns null
peek()	View front (no removal)	Returns null

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

queue.offer("First");
queue.offer("Second");
queue.offer("Third");

System.out.println(queue.peek());   // "First" (not removed)
System.out.println(queue.poll());   // "First" (removed)
System.out.println(queue.poll());   // "Second"
System.out.println(queue);          // [Third]

Real-World Example: BFS (Breadth-First Search)

static void bfs(int start, Map<Integer, List<Integer>> graph) {
    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);
            }
        }
    }
}

---

2. Deque - Double-Ended Queue

Double Ended Queue — supports insertion and removal from both ends. Encompasses both Stack and Queue behavior.

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

deque.offerLast("B");   // Add to rear
deque.offerLast("C");
deque.offerFirst("A");  // Add to front

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

System.out.println(deque.pollFirst()); // "A"
System.out.println(deque.pollLast());  // "C"

Using Deque as a Stack

The legacy Stack class is outdated. ArrayDeque is the modern recommended Stack.

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

stack.push(1);
stack.push(2);
stack.push(3);

System.out.println(stack.pop());  // 3 (LIFO)
System.out.println(stack.pop());  // 2
System.out.println(stack.peek()); // 1 (not removed)

Real-World Example: Bracket Validation

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

---

3. PriorityQueue

Elements are removed in priority order (smallest first by default), not FIFO. Internally implemented as a heap.

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(30); pq.offer(10); pq.offer(20);
System.out.println(pq.poll()); // 10 (smallest first)
System.out.println(pq.poll()); // 20
System.out.println(pq.poll()); // 30

// Descending order
PriorityQueue<Integer> descPq = new PriorityQueue<>(Comparator.reverseOrder());

// Custom priority with records
record Task(String name, int priority) {}
PriorityQueue<Task> taskQueue = new PriorityQueue<>(
    Comparator.comparingInt(Task::priority)
);
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());
// Urgent task, Important task, Normal task

---

Pro Tip

Data structure selection guide:

Situation	Choice
General FIFO queue	ArrayDeque (faster than LinkedList)
Stack (LIFO)	ArrayDeque (avoid legacy Stack class)
Both-end insert/remove	ArrayDeque
Priority-based processing	PriorityQueue

ArrayDeque is generally faster than LinkedList due to better cache locality from its internal array. Prefer ArrayDeque in new code.