Skip to content
Laviyx Learn

Try

Java course menu

Java Queue, Deque and PriorityQueue: FIFO, Stacks and Priorities

Learn Java's queue types: the Queue interface with offer, poll and peek, ArrayDeque as a FIFO queue and as a stack (push, pop), why to avoid the Stack class, PriorityQueue as a min-heap or max-heap with Comparators, and practical examples like BFS and top-k.

Intermediate13 min readUpdated
On this page

Some problems need elements processed in a particular order: the oldest first (a print queue), the newest first (undo history), or the most important first (an emergency room). Java covers all three with the Queue and Deque interfaces, and the PriorityQueue class.

Queue: first in, first out#

A queue is like a line at a counter: join at the back, leave from the front. The recommended implementation is ArrayDeque:

Java
import java.util.ArrayDeque;
import java.util.Queue;

public class Main {
    public static void main(String[] args) {
        Queue<String> printer = new ArrayDeque<>();
        printer.offer("report.pdf");
        printer.offer("photo.jpg");
        printer.offer("invoice.pdf");

        System.out.println("Next: " + printer.peek());
        while (!printer.isEmpty()) {
            System.out.println("Printing " + printer.poll());
        }
        System.out.println(printer.poll());   // empty queue: null
    }
}
Output
Next: report.pdf
Printing report.pdf
Printing photo.jpg
Printing invoice.pdf
null

Each queue operation has two forms: one returns a special value, the other throws an exception:

OperationReturns null/false on failureThrows on failure
Add at the backoffer(x)add(x)
Remove the frontpoll()remove()
Look at the frontpeek()element()

Deque as a stack: last in, first out#

A deque ("double-ended queue", pronounced "deck") allows adding and removing at both ends. ArrayDeque used with push, pop and peek is Java's recommended stack:

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

public class Main {
    public static void main(String[] args) {
        Deque<String> history = new ArrayDeque<>();
        history.push("open file");
        history.push("type text");
        history.push("bold text");

        System.out.println("Undo: " + history.pop());
        System.out.println("Undo: " + history.pop());
        System.out.println("Next undo would be: " + history.peek());
    }
}
Output
Undo: bold text
Undo: type text
Next undo would be: open file

The old java.util.Stack class still exists, but it is synchronized (slower) and extends Vector with odd extra methods. Use ArrayDeque instead.

Matching brackets with a stack#

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

public class Main {
    static boolean balanced(String text) {
        Deque<Character> open = new ArrayDeque<>();
        for (char c : text.toCharArray()) {
            if (c == '(' || c == '[' || c == '{') {
                open.push(c);
            } else if (c == ')' || c == ']' || c == '}') {
                char expected = c == ')' ? '(' : c == ']' ? '[' : '{';
                if (open.isEmpty() || open.pop() != expected) return false;
            }
        }
        return open.isEmpty();
    }

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

Both ends at once#

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

public class Main {
    public static void main(String[] args) {
        Deque<Integer> d = new ArrayDeque<>();
        d.offerLast(2);
        d.offerLast(3);
        d.offerFirst(1);
        d.offerLast(4);
        System.out.println(d);
        System.out.println(d.pollFirst() + " " + d.pollLast() + " " + d);
    }
}
Output
[1, 2, 3, 4]
1 4 [2, 3]

ArrayDeque does not allow null elements, because null is used to signal "empty".

Queues power breadth-first search, which explores a graph level by level and finds the shortest path in an unweighted graph:

Java
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.List;
import java.util.Queue;

public class Main {
    public static void main(String[] args) {
        List<List<Integer>> graph = List.of(
                List.of(1, 2), List.of(3), List.of(3, 4), List.of(5), List.of(5), List.of());

        int[] distance = new int[graph.size()];
        Arrays.fill(distance, -1);
        Queue<Integer> q = new ArrayDeque<>();
        distance[0] = 0;
        q.offer(0);

        while (!q.isEmpty()) {
            int node = q.poll();
            for (int next : graph.get(node)) {
                if (distance[next] == -1) {
                    distance[next] = distance[node] + 1;
                    q.offer(next);
                }
            }
        }
        System.out.println(Arrays.toString(distance));
    }
}
Output
[0, 1, 1, 2, 2, 3]

PriorityQueue: smallest first#

A PriorityQueue always gives you the smallest element first (by natural order), regardless of insertion order. It is a binary heap: offer and poll are O(log n), and peek is O(1):

Java
import java.util.Collections;
import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        for (int x : new int[] {30, 10, 50, 20, 40}) {
            minHeap.offer(x);
            maxHeap.offer(x);
        }

        StringBuilder asc = new StringBuilder();
        while (!minHeap.isEmpty()) asc.append(minHeap.poll()).append(' ');
        System.out.println(asc.toString().trim());
        System.out.println("largest: " + maxHeap.peek());
    }
}
Output
10 20 30 40 50
largest: 50

Printing a PriorityQueue directly shows its internal heap order, which is not sorted; only poll() returns elements in priority order.

Priorities for objects#

Pass a Comparator to decide what "most important" means:

Java
import java.util.Comparator;
import java.util.PriorityQueue;

record Patient(String name, int urgency) {}

public class Main {
    public static void main(String[] args) {
        PriorityQueue<Patient> er = new PriorityQueue<>(
                Comparator.comparingInt(Patient::urgency).reversed());   // most urgent first
        er.offer(new Patient("sprained ankle", 2));
        er.offer(new Patient("chest pain", 5));
        er.offer(new Patient("small cut", 1));
        er.offer(new Patient("high fever", 4));

        while (!er.isEmpty()) {
            Patient p = er.poll();
            System.out.println(p.urgency() + " " + p.name());
        }
    }
}
Output
5 chest pain
4 high fever
2 sprained ankle
1 small cut

A classic interview use: keep the k largest values of a stream in a min-heap of size k, removing the smallest whenever it grows past k.

Common mistakes#

Practice#

Practice exercise

Using a min-heap of size 3, find the 3 largest values in {12, 45, 7, 89, 23, 56, 34} and print them from largest to smallest.

Show solution
Java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;

public class TopThree {
    public static void main(String[] args) {
        int[] values = {12, 45, 7, 89, 23, 56, 34};
        PriorityQueue<Integer> top = new PriorityQueue<>();

        for (int v : values) {
            top.offer(v);
            if (top.size() > 3) top.poll();   // drop the smallest
        }

        List<Integer> result = new ArrayList<>();
        while (!top.isEmpty()) result.add(top.poll());
        Collections.reverse(result);
        System.out.println(result);
    }
}
Output
[89, 56, 45]

This runs in O(n log k) and keeps only k values in memory.

Key takeaway#

Finished this lesson?

Related lessons

JavaJava Collections Framework Overview: List, Set, Map and QueueAn overview of the Java Collections Framework: the Collection, List, Set, Queue and Map interfaces, their main implementations (ArrayList, LinkedList, HashSet, TreeSet, HashMap, TreeMap, ArrayDeque, PriorityQueue), immutable collections with List.of, the Collections utility class, and how to choose.Intermediate7 min readJavaJava Sorting: Comparable, Comparator, thenComparing and reversedLearn to sort in Java: natural ordering with Comparable and compareTo, custom orders with Comparator, Comparator.comparing, thenComparing, reversed and nullsFirst, sorting lists and arrays of objects, stable sorting, and sorted collections like TreeSet and TreeMap.Intermediate11 min readJavaJava ArrayList: Adding, Removing, Searching, Sorting and IteratingLearn Java ArrayList: creating lists, add, get, set and remove, size and contains, indexOf, looping, removeIf and the ConcurrentModificationException, sorting with sort and Comparator, converting between arrays and lists, and ArrayList vs LinkedList.Intermediate11 min read