Skip to content
Tutorials Center
My learning

Topics

Lesson 88 of 201 ยท Collections

Queues, Deques and PriorityQueue

Learn Java queues - offer, poll and peek, ArrayDeque as a stack and a queue, PriorityQueue with comparators, top-k problems, and the mistakes to avoid.

Lists let you reach any element by index. Many programs don't need that. They need to process things in a particular order: print jobs in the order they arrived, the most urgent ticket first, the most recent undo step first. Collections that are built around "add here, take from there" are called queues, and Java has three you'll use all the time.

  • A queue is first-in, first-out (FIFO): like a line at a bakery.
  • A stack is last-in, first-out (LIFO): like a pile of plates. In Java you get one from a deque (double-ended queue, pronounced "deck"), which can add and remove at both ends.
  • A priority queue always hands out the smallest (or most important) element next, whatever order things arrived in.

This lesson covers the Queue and Deque interfaces, ArrayDeque as both a queue and a stack, PriorityQueue with custom priorities, and classic problems like bracket matching and top-k.

The Queue interface: two flavors of every method

Queue has three basic operations, and each comes in two versions: one that throws an exception when it can't do its job, and one that returns a special value (false or null) instead.

Operation Throws on failure Returns a special value
Insert at the tail add(e) offer(e) returns false
Remove the head remove() poll() returns null
Look at the head element() peek() returns null

For the unbounded queues in this lesson, add and offer behave the same (they always succeed). The difference matters for capacity-limited queues, such as an ArrayBlockingQueue, where a full queue makes offer return false. On the removing side, poll and peek are the everyday choice, because "the queue is empty" is usually a normal situation, not an error.

Java A FIFO queue of print jobs

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

A common loop shape is while ((job = queue.poll()) != null) { ... }, which takes and checks in one step. It works precisely because ArrayDeque refuses to store null, so null can only mean "empty".

Deque: a double-ended queue

Deque extends Queue with the same operations at both ends:

Head (first) Tail (last)
Insert offerFirst(e) / addFirst(e) / push(e) offerLast(e) / addLast(e) / offer(e)
Remove pollFirst() / removeFirst() / pop() / poll() pollLast() / removeLast()
Examine peekFirst() / getFirst() / peek() peekLast() / getLast()

Once again the offer/poll/peek names return special values, and the add/remove/get names throw. The two main implementations are ArrayDeque (a resizable circular array) and LinkedList. Use ArrayDeque: it's faster and uses less memory. LinkedList is only worth choosing if you need to store null or remove from the middle through an iterator (see LinkedList).

ArrayDeque as a stack

The stack methods push, pop and peek all work at the head of the deque:

Java An undo history as a stack

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

The printed deque shows the top of the stack first, because push adds at the head. You may also see the class java.util.Stack in older code. It's a legacy class built on synchronized Vector, and even its own documentation recommends Deque instead; Legacy Collections explains why.

A classic stack problem is checking that brackets are balanced. Every opening bracket is pushed; every closing bracket must match the most recent unmatched opener, which is exactly what the top of the stack holds:

Java Balanced brackets with a stack

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

poll() on a deque removes from the head, the same end push uses, so here it acts as a pop that returns null instead of throwing.

Using both ends: a sliding window

Some algorithms add at one end and remove at both. A neat example is the sliding window maximum: for every window of k consecutive numbers, report the largest. Keeping a deque of indexes whose values are in decreasing order gives the answer in O(n) total, instead of rescanning each window:

Java Maximum of every window of three

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

Each index enters and leaves the deque at most once, which is why the whole pass is linear. The same "queue of things to visit" idea powers breadth-first search in graphs (Graphs, Recursion and Backtracking).

ArrayDeque rules

  • No null elements. offer(null) throws NullPointerException, because null is how poll and peek say "empty".
  • No index access. There's no get(i). If you need indexes as well as both ends, an ArrayList might fit better.
  • Fast ends. Adding and removing at either end is amortized O(1). contains and remove(Object) scan the whole deque.
  • Not thread-safe. For producer-consumer queues between threads, use a BlockingQueue such as LinkedBlockingQueue (Concurrent Collections).

ArrayDeque has three constructors: new ArrayDeque<>() (a small default capacity), new ArrayDeque<>(int numElements) and new ArrayDeque<>(Collection<? extends E> c). The int is only a hint for the initial size, so passing the expected element count avoids some array growing; the deque still expands as needed. The collection constructor copies the elements in the collection's iteration order.

PriorityQueue: smallest first

A PriorityQueue doesn't care about arrival order. Every poll() returns the smallest remaining element according to its natural ordering or a Comparator. Internally it's a binary heap: a tree stored in an array where every parent is smaller than its children. That gives:

Operation Cost
offer, poll O(log n)
peek O(1)
contains, remove(Object) O(n)
Java Polling comes out sorted, printing does not

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

Printing a PriorityQueue, looping over it with for-each, or streaming it shows the internal heap order, which is only partly sorted. The smallest element is always first, but the rest are not in order. To see the elements sorted, poll them one by one, or copy them into a list and sort it.

Custom priorities

Most real priority queues hold objects. Give the queue a Comparator that ranks them (see Sorting with Comparable and Comparator for building comparators):

Java A support desk that handles urgent tickets first

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

PriorityQueue is not stable: elements with equal priority come out in no guaranteed order. That's why the comparator adds an arrival counter as a tie-breaker. Whenever "first come, first served among equals" matters, include a sequence number like this.

Another trap: the heap only arranges an element when it's added. If you change a field that the comparator uses while the object is inside the queue, the heap doesn't notice and can return elements in the wrong order. To change a priority, remove the element, update it (or create a new record), and offer it again.

Top-k with a small heap

"Find the 3 largest values among millions" doesn't require sorting everything. Keep a min-heap of size k: its smallest element is the weakest of your current top k. For each new value, add it, and if the heap grows past k, drop the smallest. At the end, the heap holds the k largest values. That's O(n log k) time and O(k) memory:

Java The three most viewed pages

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

The heap's comparator is "smallest views first" even though we want the largest pages: the min-heap's job is to throw out losers cheaply. The same pattern finds the k nearest points, the k most frequent words, or the k cheapest flights.

Choosing a queue

You need Use
FIFO queue ArrayDeque (as Queue)
Stack (LIFO) ArrayDeque (as Deque, with push/pop)
Both ends ArrayDeque
Always the smallest or most urgent next PriorityQueue
Queue shared between threads LinkedBlockingQueue, ArrayBlockingQueue, PriorityBlockingQueue
Queue that must hold null LinkedList (rarely a good idea)

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does this print? Deque<Integer> d = new ArrayDeque<>(); d.push(1); d.push(2); d.offer(3); IO.println(d.pop());

    push adds at the head, so the deque is [2, 1] after two pushes; offer adds 3 at the tail, giving [2, 1, 3]. pop removes the head, which is 2.
  2. 2. Which method returns null instead of throwing when the queue is empty?

    poll and peek return null on an empty queue. remove, element and pop throw NoSuchElementException.
  3. 3. A PriorityQueue<Integer> holds 5, 1, 4, 2, 3. Which statement is true?

    A PriorityQueue guarantees only that the head is the smallest element. Its iteration and toString follow the internal heap layout.
  4. 4. To find the 10 largest numbers in a huge stream with a PriorityQueue, which setup is best?

    The min-heap keeps only the current top 10 and evicts the smallest of them each time, which takes O(n log 10) time and O(10) memory.
  5. 5. What happens on new ArrayDeque<String>().offer(null)?

    ArrayDeque rejects null elements, because poll and peek use null to signal an empty deque.

Summary

  • Queue methods come in pairs: add/remove/element throw, offer/poll/peek return false or null.
  • Deque adds the same operations at both ends; push, pop and peek treat its head as the top of a stack.
  • ArrayDeque is the default choice for queues, stacks and double-ended work; it rejects null and has no index access.
  • PriorityQueue is a binary heap: poll always returns the smallest element by natural order or comparator, in O(log n).
  • Printing or iterating a PriorityQueue doesn't show sorted order, ties come out in no fixed order, and changing an element's priority in place breaks the heap.
  • A min-heap capped at k elements solves top-k problems in O(n log k).

Next: Sorting with Comparable and Comparator, where you'll write the comparison rules that TreeSet, PriorityQueue and List.sort depend on.