Chapter 57 of 77

Queue, Deque & PriorityQueue in Java

Think about the line at a railway ticket counter. The person who comes first is served first, and new people join at the back. Now think about a stack of plates: you always take the plate from the top, which is the one that was placed last. And in a hospital emergency room, patients are not served in arrival order at all; the most serious case goes first.

These three situations describe three very important ways of organizing data, and Java has a collection for each:

Queue          → First In, First Out (FIFO)       ticket counter
Stack (Deque)  → Last In, First Out (LIFO)        stack of plates
PriorityQueue  → highest priority comes out first  emergency room

In the Collections chapter, we met List, Set, and Map. In this chapter, we will learn the Queue and Deque interfaces and the classes ArrayDeque and PriorityQueue. These are used constantly in real programs and in coding interviews (for example, BFS uses a queue and "top K" problems use a priority queue).

The Queue Interface

A Queue holds elements waiting to be processed. In a normal queue, elements are added at the back (tail) and removed from the front (head): First In, First Out.

  remove here                    add here
      ↓                              ↓
   [ Asha | Bilal | Chetan ]  ←  Divya
    head                tail

Queue is an interface in java.util. Two common classes implement it: LinkedList (which you already know) and ArrayDeque. Here is a queue at a ticket counter:

import java.util.LinkedList;
import java.util.Queue;

class Main {
    public static void main(String[] args) {

        Queue<String> ticketQueue = new LinkedList<>();

        ticketQueue.offer("Asha");      // joins at the back
        ticketQueue.offer("Bilal");
        ticketQueue.offer("Chetan");
        System.out.println("Queue: " + ticketQueue);

        System.out.println("Next in line: " + ticketQueue.peek());   // look, don't remove

        String served = ticketQueue.poll();                         // remove from the front
        System.out.println("Served: " + served);
        System.out.println("Queue: " + ticketQueue);

        ticketQueue.offer("Divya");
        System.out.println("Queue: " + ticketQueue);
        System.out.println("Size: " + ticketQueue.size());
    }
}

Output:

Queue: [Asha, Bilal, Chetan]
Next in line: Asha
Served: Asha
Queue: [Bilal, Chetan]
Queue: [Bilal, Chetan, Divya]
Size: 3

The three main operations are:

  • offer(e): adds an element at the back.

  • peek(): returns the front element without removing it.

  • poll(): removes and returns the front element.

Two Versions of Each Operation

The Queue interface actually has two methods for each operation. They differ only in what happens when the operation fails, for example when the queue is empty:

Operation

Throws an exception

Returns a special value

Add at the back

add(e)

offer(e) (returns false if it can't add)

Remove from the front

remove()

poll() (returns null if empty)

Look at the front

element()

peek() (returns null if empty)

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

class Main {
    public static void main(String[] args) {

        Queue<Integer> queue = new ArrayDeque<>();   // empty queue

        System.out.println(queue.peek());   // null
        System.out.println(queue.poll());   // null

        try {
            queue.element();
        } catch (Exception e) {
            System.out.println("element() threw " + e.getClass().getSimpleName());
        }

        try {
            queue.remove();
        } catch (Exception e) {
            System.out.println("remove() threw " + e.getClass().getSimpleName());
        }
    }
}

Output:

null
null
element() threw NoSuchElementException
remove() threw NoSuchElementException

Most programmers use offer(), poll(), and peek(), and check for null or use isEmpty(). For the collections in this chapter, add() and offer() behave the same, because they never run out of space.

Deque: A Double-Ended Queue

A Deque (pronounced "deck") is a double-ended queue: you can add and remove elements at both the front and the back.

Deque extends Queue. The most popular implementation is ArrayDeque, which stores elements in a resizable circular array.

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

class Main {
    public static void main(String[] args) {

        Deque<Integer> deque = new ArrayDeque<>();

        deque.offerLast(20);    // [20]
        deque.offerLast(30);    // [20, 30]
        deque.offerFirst(10);   // [10, 20, 30]
        deque.offerFirst(5);    // [5, 10, 20, 30]
        System.out.println(deque);

        System.out.println("First: " + deque.peekFirst());
        System.out.println("Last: " + deque.peekLast());

        deque.pollFirst();      // removes 5
        deque.pollLast();       // removes 30
        System.out.println(deque);
    }
}

Output:

[5, 10, 20, 30]
First: 5
Last: 30
[10, 20]

The method names follow a simple pattern: offer/poll/peek + First/Last. There are also throwing versions such as addFirst(), removeLast(), and getFirst(), just like in the table above.

Using a Deque as a Stack

A stack is Last In, First Out (LIFO): the last element added is the first one removed. Think of the browser's back button: the last page you visited is the first one you go back to.

Deque has the classic stack methods built in:

  • push(e): adds to the top (the front of the deque).

  • pop(): removes and returns the top. Throws NoSuchElementException if empty.

  • peek(): returns the top without removing it, or null if empty.

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

class Main {
    public static void main(String[] args) {

        Deque<String> stack = new ArrayDeque<>();

        stack.push("Page 1");   // push adds to the top (front)
        stack.push("Page 2");
        stack.push("Page 3");
        System.out.println("Stack: " + stack);

        System.out.println("Top: " + stack.peek());
        System.out.println("Back to: " + stack.pop());
        System.out.println("Back to: " + stack.pop());
        System.out.println("Stack: " + stack);
    }
}

Output:

Stack: [Page 3, Page 2, Page 1]
Top: Page 3
Back to: Page 3
Back to: Page 2
Stack: [Page 1]

Notice that the stack prints as [Page 3, Page 2, Page 1]: the top of the stack is at the front.

Java also has an older Stack class. It still works, but it is a legacy class (it extends Vector, and its operations are synchronized, which adds overhead even in single-threaded code). The Java documentation itself recommends using Deque and ArrayDeque for stacks instead.

Interview Classic: Balanced Brackets

Checking whether brackets are balanced is one of the most common stack problems. Push every opening bracket; when you see a closing bracket, pop and check that it matches:

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

class Main {

    static boolean isBalanced(String text) {
        Deque<Character> stack = new ArrayDeque<>();

        for (char ch : text.toCharArray()) {
            if (ch == '(' || ch == '[' || ch == '{') {
                stack.push(ch);                       // remember the opening bracket
            } else if (ch == ')' || ch == ']' || ch == '}') {
                if (stack.isEmpty()) {
                    return false;                     // closing bracket with no opener
                }
                char open = stack.pop();
                if ((ch == ')' && open != '(') ||
                    (ch == ']' && open != '[') ||
                    (ch == '}' && open != '{')) {
                    return false;                     // wrong type of bracket
                }
            }
        }
        return stack.isEmpty();                       // every opener must be closed
    }

    public static void main(String[] args) {
        System.out.println(isBalanced("{[a + b] * (c - d)}"));
        System.out.println(isBalanced("([)]"));
        System.out.println(isBalanced("((x)"));
    }
}

Output:

true
false
false

In "([)]", the ) arrives when the top of the stack is [, so it fails. In "((x)", one ( is left on the stack at the end. This runs in O(n) time and uses O(n) extra space in the worst case.

PriorityQueue

A PriorityQueue always removes the element with the highest priority first. By default, the smallest element has the highest priority.

So elements come out in sorted order, no matter what order they went in:

import java.util.PriorityQueue;

class Main {
    public static void main(String[] args) {

        PriorityQueue<Integer> pq = new PriorityQueue<>();

        pq.offer(50);
        pq.offer(20);
        pq.offer(40);
        pq.offer(10);
        pq.offer(30);

        System.out.println("Printed: " + pq);        // NOT sorted order!
        System.out.println("Smallest: " + pq.peek());

        System.out.print("Polling:");
        while (!pq.isEmpty()) {
            System.out.print(" " + pq.poll());
        }
        System.out.println();
    }
}

Output:

Printed: [10, 20, 40, 50, 30]
Smallest: 10
Polling: 10 20 30 40 50

Look carefully at the first line. Printing the PriorityQueue gives [10, 20, 40, 50, 30], which is not sorted. That is because a PriorityQueue is internally a binary min-heap: a tree stored in an array, where every parent is smaller than or equal to its children. Only the top (the root) is guaranteed to be the smallest:

          10            array: [10, 20, 40, 50, 30]
        /    \
      20      40        every parent ≤ its children
     /  \
   50    30

Each poll() removes the root and then rearranges the heap so the next smallest element moves to the top. That is why polling gives the correct sorted order, while printing or looping with for-each does not.

Max-Heap and Other Orders

To get the largest element first, pass Collections.reverseOrder() to the constructor. Strings use alphabetical order by default:

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

class Main {
    public static void main(String[] args) {

        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        maxHeap.offer(40);
        maxHeap.offer(10);
        maxHeap.offer(30);
        maxHeap.offer(20);

        System.out.println("Largest: " + maxHeap.peek());
        System.out.println(maxHeap.poll() + " " + maxHeap.poll() + " " + maxHeap.poll() + " " + maxHeap.poll());

        PriorityQueue<String> names = new PriorityQueue<>();
        names.offer("Meera");
        names.offer("Arjun");
        names.offer("Zoya");
        names.offer("Kabir");

        System.out.println(names.poll() + " " + names.poll() + " " + names.poll() + " " + names.poll());
    }
}

Output:

Largest: 40
40 30 20 10
Arjun Kabir Meera Zoya

PriorityQueue works with any type that has a natural order, such as numbers and Strings. To store your own objects, like a Patient sorted by severity, Java must know how to compare them. You will learn how to do that in the Comparable & Comparator chapter, and the same PriorityQueue will work for your own classes too.

Interview Classic: K-th Largest Element

A very common question: find the k-th largest number in an array. Sorting takes O(n log n). With a min-heap of size k, we can do it in O(n log k):

import java.util.PriorityQueue;

class Main {

    // Returns the k-th largest number using a min-heap of size k
    static int kthLargest(int[] nums, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        for (int num : nums) {
            minHeap.offer(num);
            if (minHeap.size() > k) {
                minHeap.poll();          // remove the smallest, keep the k largest
            }
        }
        return minHeap.peek();           // smallest of the k largest = k-th largest
    }

    public static void main(String[] args) {
        int[] scores = {72, 95, 61, 88, 99, 45, 80};

        System.out.println("1st highest: " + kthLargest(scores, 1));
        System.out.println("2nd highest: " + kthLargest(scores, 2));
        System.out.println("3rd highest: " + kthLargest(scores, 3));
    }
}

Output:

1st highest: 99
2nd highest: 95
3rd highest: 88

The heap always keeps the k largest numbers seen so far. Whenever it grows beyond k, we remove the smallest. At the end, the smallest number in the heap (its top) is the k-th largest overall. For k = 3, the heap ends up holding 88, 95, and 99, and its top is 88.

Time Complexity

Operation

ArrayDeque

PriorityQueue

Add (offer, push, offerFirst...)

O(1) on average

O(log n)

Remove from front (poll, pop)

O(1)

O(log n)

Look at front (peek)

O(1)

O(1)

contains(e) / remove(e)

O(n)

O(n)

Which One Should You Use?

You need

Use

A FIFO queue

Queue<T> q = new ArrayDeque<>(); (or LinkedList if you need to store null)

A stack

Deque<T> stack = new ArrayDeque<>();

Add/remove at both ends

Deque<T> d = new ArrayDeque<>();

Always get the smallest (or largest) next

PriorityQueue<T>

ArrayDeque is usually faster than LinkedList for queues and stacks, because it uses an array instead of separate node objects.

Common Mistakes

  • Expecting a PriorityQueue to print in sorted order. Only poll() gives sorted order. Printing and for-each loops show the internal heap order.

  • Adding null to an ArrayDeque or PriorityQueue. Both throw NullPointerException, because poll() and peek() use null to mean "empty".

  • Calling remove(), element(), or pop() on an empty collection. These throw NoSuchElementException. Use poll()/peek() or check isEmpty() first.

  • Using the legacy Stack class in new code. Prefer ArrayDeque.

  • Forgetting that push() adds to the front. If you mix push() with offer() (which adds to the back) on the same deque, the order gets confusing. Use one style per deque.

Practice Problems

  • Reverse a string using a stack.

  • Simulate a printer queue: add 5 print jobs and process them in order.

  • Find the 3 smallest numbers in an array using a max-heap of size 3.

  • Check whether a word is a palindrome using a Deque (compare pollFirst() with pollLast()).

The Main Idea

Choose the collection by the order in which elements must come out.

Queue → first in, first out. Stack (Deque with push/pop) → last in, first out. PriorityQueue → smallest (or highest-priority) first.

For queues and stacks, ArrayDeque is the go-to class. For "always give me the best next item", use PriorityQueue.