Skills101

AdvancedJava Programming · Lesson 25 of 29 · Updated ·

Queue, Deque and PriorityQueue in Java — ArrayDeque, Heaps and Top-K

A queue is a line: the first person to join is the first to be served. This rule is called FIFO (first in, first out). A stack is a pile of plates: the last plate put on top is the first taken off, called LIFO (last in, first out). A priority queue serves the most important item first, like an emergency room. The collections lesson named these in one line each; here you learn to use them properly, because they appear in almost every coding round (BFS, bracket matching, top-K, scheduling).

1. Queue: two sets of methods

The Queue interface has two versions of each operation. One throws an exception when it cannot work; the other returns a special value (false or null).

OperationThrows exceptionReturns special value
add at the backadd(e)offer(e) → false if full
remove from the frontremove()poll() → null if empty
look at the frontelement()peek() → null if empty

In everyday code, use offer, poll and peek. An empty queue is normal (for example, no customers left), so returning null is easier to handle than catching an exception.

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Queue<String> counter = new ArrayDeque<>();
        counter.offer("Asha");
        counter.offer("Ravi");
        counter.offer("Neha");
        System.out.println("next: " + counter.peek());
        while (!counter.isEmpty()) {
            System.out.println("served " + counter.poll());
        }
        System.out.println(counter.poll());
        try {
            counter.remove();
        } catch (NoSuchElementException e) {
            System.out.println("remove() on empty queue throws");
        }
    }
}
next: Asha
served Asha
served Ravi
served Neha
null
remove() on empty queue throws

2. Deque: a queue open at both ends

A Deque (said "deck", short for double-ended queue) lets you add and remove at both the front (head) and the back (tail). That makes it a queue and a stack in one class.

A Deque has two open ends: offerFirst, pollFirst, push and pop work at the head; offerLast and pollLast work at the tail

ArrayDeque is the usual choice. It stores elements in a growing circular array, so both ends are fast. The old Stack class is synchronized (slower) and extends Vector, so the Java documentation itself recommends Deque for stacks.

As a stack, push and pop both work at the head. A classic use is checking balanced brackets:

import java.util.*;

public class Main {
    static boolean balanced(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 open = stack.pop();
                if ((c == ')' && open != '(') || (c == ']' && open != '[') || (c == '}' && open != '{')) return false;
            }
        }
        return stack.isEmpty();
    }

    public static void main(String[] args) {
        for (String s : List.of("{[()]}", "([)]", "((", "()[]{}")) {
            System.out.println(s + " -> " + balanced(s));
        }
        Deque<Integer> d = new ArrayDeque<>();
        d.offerLast(2); d.offerLast(3); d.offerFirst(1);
        System.out.println(d + " first=" + d.peekFirst() + " last=" + d.peekLast());
    }
}
{[()]} -> true
([)] -> false
(( -> false
()[]{} -> true
[1, 2, 3] first=1 last=3

One limit: ArrayDeque does not accept null, because poll uses null to mean "empty".

3. PriorityQueue: smallest first, using a heap

A PriorityQueue always gives you the smallest element (by natural order or a Comparator) from peek and poll. Inside, it is a binary min-heap stored in an array: every parent is smaller than or equal to its children. The smallest element is always at index 0, but the rest of the array is not fully sorted.

A min-heap after inserting 40, 10, 30, 5, 20: the array is 5, 10, 30, 40, 20; drawn as a tree, 5 is the root and every parent is smaller than its children

import java.util.*;

public class Main {
    public static void main(String[] args) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int x : new int[]{40, 10, 30, 5, 20}) pq.offer(x);
        System.out.println("printed: " + pq);
        System.out.println("peek: " + pq.peek());
        StringBuilder out = new StringBuilder();
        while (!pq.isEmpty()) out.append(pq.poll()).append(' ');
        System.out.println("polled: " + out.toString().trim());

        PriorityQueue<Integer> max = new PriorityQueue<>(Comparator.reverseOrder());
        max.addAll(List.of(40, 10, 30, 5, 20));
        System.out.println("max first: " + max.poll() + ", then " + max.poll());
    }
}
printed: [5, 10, 30, 40, 20]
peek: 5
polled: 5 10 20 30 40
max first: 40, then 30

Notice: printing a PriorityQueue (or looping over it with for-each) shows the heap array, not sorted order. Only repeated poll() gives sorted order. This is a favourite trick question.

PriorityQueue operationTime
offer, pollO(log n) — the element moves up or down the tree
peekO(1) — it is always at index 0
contains, remove(Object)O(n) — must search the array

Ordering your own objects

Pass a Comparator. A hospital serves the most serious patient first; for equal severity, the one who came earlier.

import java.util.*;

record Patient(String name, int severity, int arrival) { }

public class Main {
    public static void main(String[] args) {
        PriorityQueue<Patient> er = new PriorityQueue<>(
            Comparator.comparingInt(Patient::severity).reversed().thenComparingInt(Patient::arrival));
        er.offer(new Patient("Om", 2, 1));
        er.offer(new Patient("Isha", 5, 2));
        er.offer(new Patient("Ravi", 5, 3));
        er.offer(new Patient("Neha", 3, 4));
        while (!er.isEmpty()) System.out.print(er.poll().name() + " ");
        System.out.println();
    }
}
Isha Ravi Neha Om 

4. The top-K problem

"Find the 3 highest marks out of a million" is asked often. Sorting everything costs O(n log n). A better way: keep a min-heap of size k. For each mark, add it; if the heap grows beyond k, remove the smallest. At the end, the heap holds the k largest. This costs O(n log k), and memory is only k elements.

import java.util.*;

public class Main {
    public static void main(String[] args) {
        int[] marks = {67, 92, 45, 88, 73, 99, 58, 81};
        int k = 3;
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        for (int m : marks) {
            heap.offer(m);
            if (heap.size() > k) heap.poll();     // drop the smallest
        }
        List<Integer> top = new ArrayList<>(heap);
        top.sort(Comparator.reverseOrder());
        System.out.println("top " + k + ": " + top);
        System.out.println("3rd highest: " + heap.peek());
    }
}
top 3: [99, 92, 88]
3rd highest: 88

The root of the heap is the smallest of the top k, which is exactly the k-th largest — another common question.

5. Choosing the right class

NeedUse
FIFO queue (BFS, tasks in order)ArrayDeque
Stack (undo, brackets, DFS)ArrayDeque with push / pop
Smallest or largest firstPriorityQueue
Queue shared between threadsArrayBlockingQueue / LinkedBlockingQueue
Need null elements or a List tooLinkedList (slower, more memory)

Common mistakes

  • Using remove() or element() on a queue that may be empty, and getting NoSuchElementException. Use poll() / peek().
  • Printing or iterating a PriorityQueue and expecting sorted order.
  • Forgetting that PriorityQueue is a min-heap by default; for the largest first, pass Comparator.reverseOrder().
  • Using the old Stack class in new code instead of ArrayDeque.
  • Adding null to an ArrayDeque or PriorityQueue (both throw NullPointerException).
  • Sorting the whole array for top-K when a size-k heap is enough.

Quick recap

  • Queue = FIFO; prefer offer, poll, peek (they return false/null instead of throwing).
  • Deque works at both ends; ArrayDeque is the best queue and the best stack.
  • PriorityQueue is a binary min-heap: peek O(1), offer/poll O(log n), printed order is not sorted.
  • Max-heap: new PriorityQueue<>(Comparator.reverseOrder()).
  • Top-K largest: min-heap of size k, O(n log k).

Practice what you learned

📝 Quiz: Queue, Deque and PriorityQueue5 questions · instant answers & explanations · +10 XP · counts towards your free certificateTake the quiz →