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

Source: https://skills101.in/learn/java/java-queue-deque-priorityqueue — Skills101 free tutorial (Java Programming). Updated 2026-11-21.

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](https://skills101.in/learn/java/java-collections-list-set) 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`).

| Operation | Throws exception | Returns special value |
|---|---|---|
| add at the back | `add(e)` | `offer(e)` → `false` if full |
| remove from the front | `remove()` | `poll()` → `null` if empty |
| look at the front | `element()` | `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.

```java
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");
        }
    }
}
```

```text
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](https://skills101.in/learn-img/java/deque-ends.svg)

`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:

```java
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());
    }
}
```

```text
{[()]} -> 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](https://skills101.in/learn-img/java/heap-tree.svg)

```java
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());
    }
}
```

```text
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 operation | Time |
|---|---|
| `offer`, `poll` | O(log n) — the element moves up or down the tree |
| `peek` | O(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.

```java
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();
    }
}
```

```text
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.

```java
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());
    }
}
```

```text
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

| Need | Use |
|---|---|
| FIFO queue (BFS, tasks in order) | `ArrayDeque` |
| Stack (undo, brackets, DFS) | `ArrayDeque` with `push` / `pop` |
| Smallest or largest first | `PriorityQueue` |
| Queue shared between threads | `ArrayBlockingQueue` / `LinkedBlockingQueue` |
| Need `null` elements or a List too | `LinkedList` (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 quiz and free certificate: https://skills101.in/learn/java/java-queue-deque-priorityqueue