Queue and Deque: PriorityQueue, ArrayDeque

Queue models a collection designed for holding elements before processing, typically in first-in-first-out (FIFO) order: elements are added at the tail with offer() and removed from the head with poll(). Deque ("double-ended queue") extends this idea, allowing efficient insertion and removal at both ends, which makes it flexible enough to act as a queue, a stack, or both.

Why it matters

Queues and stacks are how programs hold work that is waiting to be done: tasks for a thread pool, nodes still to visit in a graph search, operations that can be undone. ArrayDeque is the right class for both a stack and a plain queue, and PriorityQueue is the standard tool whenever the next item should be the smallest or the most urgent and not the oldest.

Queue Basics and Method Pairs

Queue offers two parallel sets of methods: one set throws an exception on failure (add(), remove(), element()), and one set returns a special value instead (offer(), poll(), peek()). The value-returning versions are generally preferred in everyday code, because they avoid unexpected exceptions when a queue is empty or full — poll() returns null instead of throwing when the queue is empty.

PriorityQueue — Ordering by Priority, Not Insertion

PriorityQueue does not preserve FIFO order; instead, it always returns the smallest element first according to natural ordering (via Comparable) or a supplied Comparator. Internally it is backed by a binary heap, giving O(log n) for offer() and poll(), and O(1) for peek() at the head. It does not permit null elements, since nulls cannot be compared. PriorityQueue is the standard tool for scheduling problems and "find the next most important item" logic.

Deque and ArrayDeque as a Modern Stack

Deque supports addFirst()/addLast(), removeFirst()/removeLast(), and peekFirst()/peekLast(), all in O(1) time on ArrayDeque, which is backed by a resizable circular array. Because a stack is just a deque used at one end (push()/pop()/peek() all operate on the head), the official Java documentation recommends ArrayDeque over the old Stack class: it is faster (no synchronization overhead), has no legacy baggage, and does not allow null elements, which catches bugs earlier than the historically permissive Stack class.

• Queue: FIFO by default; exception-throwing and value-returning method pairs.
• PriorityQueue: heap-based, O(log n) offer/poll, orders by Comparable or Comparator, no nulls.
• ArrayDeque: O(1) at both ends, preferred replacement for both Stack and LinkedList-as-queue.

Time complexity

Example

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.PriorityQueue;
import java.util.Queue;

public class QueueDeckDemo {
    public static void main(String[] args) {
        Queue<Integer> pq = new PriorityQueue<>();
        pq.offer(30);
        pq.offer(10);
        pq.offer(20);
        System.out.print("PriorityQueue polling order: ");
        while (!pq.isEmpty()) {
            System.out.print(pq.poll() + " "); // always smallest first: 10, 20, 30
        }
        System.out.println();

        Deque<String> stack = new ArrayDeque<>();
        stack.push("first");
        stack.push("second");
        stack.push("third");
        System.out.println("Stack pop (LIFO): " + stack.pop()); // "third"

        Deque<String> queue = new ArrayDeque<>();
        queue.offer("first");
        queue.offer("second");
        System.out.println("Deque poll (FIFO): " + queue.poll()); // "first"
    }
}

PriorityQueue polling order: 10 20 30
Stack pop (LIFO): third
Deque poll (FIFO): first

Where this is used

Breadth-first search uses a queue of nodes still to visit, and depth-first search uses a stack; both are normally an ArrayDeque. A PriorityQueue is behind Dijkstra's shortest-path algorithm, schedulers that run the earliest-due job first, and the common interview task of finding the top k items of a large collection.

Exercise

Use an ArrayDeque as a stack to check whether the brackets in a string are balanced. Each closing bracket must match the most recent opening bracket that is still open.

Expected output: true then false

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

public class Brackets {

    static boolean balanced(String text) {
        Deque<Character> stack = new ArrayDeque<>();

        // TODO: push each opening bracket
        // TODO: for each closing bracket, pop and check that it matches

        return false; // TODO: balanced only if nothing is left open
    }

    public static void main(String[] args) {
        System.out.println(balanced("{[()]}"));
        System.out.println(balanced("([)]"));
    }
}

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

public class Brackets {

    static boolean balanced(String text) {
        Deque<Character> stack = new ArrayDeque<>();

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

    public static void main(String[] args) {
        System.out.println(balanced("{[()]}")); // true
        System.out.println(balanced("([)]"));   // false
    }
}

Quick quiz

Interview questions