Queue = FIFO line, Deque = double-ended (queue and stack), PriorityQueue = always hands you the smallest element next. ArrayDeque and PriorityQueue cover almost every need.

Two method families

Action	Throws on failure	Returns special value
Insert	`add(e)` — `IllegalStateException` if full	`offer(e)` → `false`
Remove head	`remove()` — `NoSuchElementException` if empty	`poll()` → `null`
Look at head	`element()` — `NoSuchElementException`	`peek()` → `null`

`ArrayDeque` as a queue and as a stack

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Deque<Integer> queue = new ArrayDeque<>();   // FIFO: offer at tail, poll at head
        queue.offer(1);
        queue.offer(2);
        queue.offer(3);
        System.out.println(queue.poll() + " " + queue.peek() + " " + queue);

        Deque<Integer> stack = new ArrayDeque<>();   // LIFO: push/pop at the head
        stack.push(1);
        stack.push(2);
        stack.push(3);
        System.out.println(stack.pop() + " " + stack.peek() + " " + stack);

        Deque<String> dq = new ArrayDeque<>();
        dq.offerFirst("b");
        dq.offerFirst("a");
        dq.offerLast("c");
        System.out.println(dq.pollLast() + " " + dq);
        System.out.println(new ArrayDeque<Integer>().poll());   // empty -> null
    }
}

Output

1 2 [2, 3]
3 2 [2, 1]
c [a, b]
null

Deque method	As a queue	As a stack
`offerLast` / `offer`	enqueue	—
`pollFirst` / `poll`	dequeue	—
`push` (= `addFirst`)	—	push
`pop` (= `removeFirst`)	—	pop
`peekFirst` / `peek`	front	top

`PriorityQueue` — a binary heap

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        PriorityQueue<Integer> min = new PriorityQueue<>(List.of(5, 1, 8, 3, 2));
        System.out.println("peek=" + min.peek());
        StringBuilder sb = new StringBuilder();
        while (!min.isEmpty()) sb.append(min.poll()).append(' ');
        System.out.println("min-heap order: " + sb.toString().trim());

        PriorityQueue<Integer> max = new PriorityQueue<>(Comparator.reverseOrder());
        max.addAll(List.of(5, 1, 8, 3, 2));
        System.out.println("max first: " + max.poll() + " " + max.poll());

        PriorityQueue<String> byLen = new PriorityQueue<>(
            Comparator.comparingInt(String::length).thenComparing(Comparator.naturalOrder()));
        byLen.addAll(List.of("kiwi", "fig", "banana", "date"));
        System.out.println(byLen.poll() + " " + byLen.poll() + " " + byLen.poll());
    }
}

Output

peek=1
min-heap order: 1 2 3 5 8
max first: 8 5
fig date kiwi

Operation	Cost
`offer` / `add`	O(log n) — sift up
`poll` / `remove()`	O(log n) — sift down
`peek`	O(1)
`remove(Object)` / `contains`	O(n)
Build from a collection	O(n) heapify

Top-K with a size-K min-heap

Java

import java.util.*;

public class Main {
    static List<Integer> topK(int[] nums, int k) {
        PriorityQueue<Integer> heap = new PriorityQueue<>();  // min-heap of the k largest so far
        for (int x : nums) {
            heap.offer(x);
            if (heap.size() > k) heap.poll();                 // drop the smallest
        }
        List<Integer> res = new ArrayList<>(heap);
        res.sort(Comparator.reverseOrder());
        return res;
    }

    public static void main(String[] args) {
        System.out.println(topK(new int[]{3, 1, 9, 7, 4, 8, 2}, 3));
    }
}

Output

[9, 8, 7]

O(n log k) time, O(k) space — better than sorting everything (O(n log n)) when k ≪ n.

Why prefer ArrayDeque over Stack and LinkedList?

How do you make a max-heap in Java?

Is PriorityQueue thread-safe? What about blocking queues?

Two method families

ArrayDeque as a queue and as a stack

PriorityQueue — a binary heap

Top-K with a size-K min-heap

`ArrayDeque` as a queue and as a stack

`PriorityQueue` — a binary heap