SyntaxPilot
Courses/Java/Lesson 33

Java · Lesson 33 of 51 · 11 min

Queue, Deque, PriorityQueue, Stack

queued

These are the notes for Java episode 33. Lists, sets and maps don't care who came first, but a ticket counter, an undo button and a hospital emergency room do, each in a different way. We serve a long line with ArrayList.remove(0) and watch it crawl, then invent the queue (first in, first out) on a circular array, the stack (last in, first out) for undo, the deque (both ends), and the priority queue (most important first) with the heap inside it. Every example was run with javac 21.

The problem: serving a line with a list

At a railway ticket counter, the front person is served, then everyone steps forward. With an ArrayList, that's remove(0):

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        List<Integer> line = new ArrayList<>();
        for (int i = 0; i < 150_000; i++) line.add(i);
        long t = System.nanoTime();
        while (!line.isEmpty()) line.remove(0);          // serve the first person
        System.out.println("ArrayList remove(0): " + (System.nanoTime() - t) / 1_000_000 + " ms");

        ArrayDeque<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < 150_000; i++) queue.offer(i);
        t = System.nanoTime();
        while (!queue.isEmpty()) queue.poll();
        System.out.println("ArrayDeque poll():   " + (System.nanoTime() - t) / 1_000_000 + " ms");
    }
}

Output:

ArrayList remove(0): 889 ms
ArrayDeque poll():   3 ms

(Times vary by machine; the gap does not.) An ArrayList is an array: removing index 0 shifts every other item one place left. n removals × n shifts = O(n²).

The fix: a circular array (ArrayDeque)

At a bank with a token display In Java
People sit in numbered seats; nobody moves items stay where they are in an array
"Now serving seat 7": only the display changes a head index moves forward
Freed seats at the start are reused the array wraps around: a circular array
Serving is instant, however long the line ArrayDeque: O(1) at both ends

Queue: first in, first out (FIFO)

Queue<E> is the interface; ArrayDeque is the class to use.

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

public class Main {
    public static void main(String[] args) {
        Queue<String> counter = new ArrayDeque<>();
        counter.offer("Asha");
        counter.offer("Ravi");
        counter.offer("Meena");
        System.out.println(counter.peek() + " is next, line: " + counter);
        System.out.println("Served: " + counter.poll());
        System.out.println("Served: " + counter.poll());
        System.out.println("Left: " + counter + ", size " + counter.size());
    }
}

Output:

Asha is next, line: [Asha, Ravi, Meena]
Served: Asha
Served: Ravi
Left: [Meena], size 1

Two flavours of every operation

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

public class Main {
    public static void main(String[] args) {
        Queue<String> counter = new ArrayDeque<>();
        System.out.println(counter.poll());      // empty: null
        System.out.println(counter.peek());      // empty: null
        System.out.println(counter.remove());    // empty: ?
    }
}

Output:

null
null
Exception in thread "main" java.util.NoSuchElementException
    at java.base/java.util.ArrayDeque.removeFirst(ArrayDeque.java:361)
    at java.base/java.util.ArrayDeque.remove(ArrayDeque.java:522)
    at Main.main(Main.java:9)
Action Returns a special value Throws an exception
add at the back offer(e) → false if full add(e)
remove the front poll() → null if empty remove() → NoSuchElementException
look at the front peek() → null if empty element() → NoSuchElementException

Pick one style and check isEmpty() before taking.

Stack: last in, first out (LIFO)

A pile of plates: you push a plate on top and pop the top one. Undo works the same way: the last change is undone first.

Why not the old Stack class?

import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Stack<String> undo = new Stack<>();
        undo.push("type Hello");
        undo.push("bold");
        undo.push("delete line");
        System.out.println("Undo: " + undo.pop());
        undo.add(0, "sneaky");                   // Stack is a Vector: any index works
        System.out.println(undo + " " + undo.get(0));
        undo.clear();
        undo.pop();
    }
}

Output:

Undo: delete line
[sneaky, type Hello, bold] sneaky
Exception in thread "main" java.util.EmptyStackException
    at java.base/java.util.Stack.peek(Stack.java:103)
    at java.base/java.util.Stack.pop(Stack.java:85)
    at Main.main(Main.java:13)

java.util.Stack (1996) extends Vector, so it also has add(index, e), get(index) and more: anyone can break LIFO. Its methods are synchronized (slower), and an empty pop() throws EmptyStackException. The Java documentation recommends Deque instead.

A stack with ArrayDeque

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

public class Main {
    public static void main(String[] args) {
        Deque<String> undo = new ArrayDeque<>();
        undo.push("type Hello");
        undo.push("bold");
        undo.push("delete line");
        System.out.println(undo + " top: " + undo.peek());
        System.out.println("Undo: " + undo.pop());
        System.out.println("Undo: " + undo.pop());
        System.out.println("Left: " + undo);
    }
}

Output:

[delete line, bold, type Hello] top: delete line
Undo: delete line
Undo: bold
Left: [type Hello]
Stack method Meaning
push(e) add on top
pop() remove the top (throws NoSuchElementException if empty)
peek() look at the top (null if empty)

A real use: checking brackets

Every opening bracket is pushed; every closing bracket must match the one popped from the top; at the end the stack must be empty. Compilers and editors do exactly this.

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

public class Main {
    static boolean balanced(String s) {
        Deque<Character> st = new ArrayDeque<>();
        for (char c : s.toCharArray()) {
            if (c == '(' || c == '[' || c == '{') st.push(c);
            else if (c == ')' || c == ']' || c == '}') {
                if (st.isEmpty()) return false;
                char open = st.pop();
                if ((c == ')' && open != '(') || (c == ']' && open != '[')
                        || (c == '}' && open != '{')) return false;
            }
        }
        return st.isEmpty();
    }
    public static void main(String[] args) {
        for (String s : new String[] { "{a[i] = (b + c);}", "(a + b]", "((x)" }) {
            System.out.println(s + " -> " + balanced(s));
        }
    }
}

Output:

{a[i] = (b + c);} -> true
(a + b] -> false
((x) -> false

Deque: a double-ended queue

ArrayDeque was a queue and a stack because it implements Deque: add and remove at both ends.

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

public class Main {
    public static void main(String[] args) {
        Deque<String> coach = new ArrayDeque<>();
        coach.offerLast("Ravi");
        coach.offerLast("Meena");
        coach.offerFirst("Asha");        // senior citizen: front of the line
        coach.offerLast("Kabir");
        System.out.println(coach);
        System.out.println(coach.pollFirst() + " boards, " + coach.pollLast() + " leaves");
        System.out.println(coach.peekFirst() + " " + coach.peekLast() + " " + coach);
    }
}

Output:

[Asha, Ravi, Meena, Kabir]
Asha boards, Kabir leaves
Ravi Meena [Ravi, Meena]
Front Back
offerFirst(e) / addFirst(e) / push(e) offerLast(e) / addLast(e) / offer(e)
pollFirst() / removeFirst() / pop() / poll() pollLast() / removeLast()
peekFirst() / peek() peekLast()

PriorityQueue: most important first

In an emergency room, arrival order is the wrong rule:

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

public class Main {
    public static void main(String[] args) {
        Queue<Integer> er = new ArrayDeque<>();   // severity: 1 = most serious
        er.offer(4);   // sprained ankle
        er.offer(1);   // heart attack
        er.offer(3);   // high fever
        er.offer(2);   // broken arm
        while (!er.isEmpty()) System.out.print(er.poll() + " ");
        System.out.println();
    }
}

Output:

4 1 3 2

A heart attack (severity 1) waits behind a sprained ankle (4). A PriorityQueue always hands out the smallest item first:

import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) {
        PriorityQueue<Integer> er = new PriorityQueue<>();   // severity: 1 = most serious
        er.offer(4);   // sprained ankle
        er.offer(2);   // broken arm
        er.offer(5);   // small cut
        er.offer(1);   // heart attack
        er.offer(3);   // high fever
        System.out.println("Inside: " + er + ", next: " + er.peek());
        while (!er.isEmpty()) System.out.print(er.poll() + " ");
        System.out.println();
    }
}

Output:

Inside: [1, 2, 5, 4, 3], next: 1
1 2 3 4 5

poll gives 1, 2, 3, 4, 5, but printing the queue shows [1, 2, 5, 4, 3]: it is not sorted. Only the front is guaranteed.

The heap inside

A PriorityQueue is a binary min-heap stored in an array:

            1            index 0
          /   \
         2     5         index 1, 2
        / \
       4   3             index 3, 4        array: [1, 2, 5, 4, 3]
  • Heap rule: every parent ≤ its children, so the smallest is at the top. Siblings are in no particular order.
  • No pointers: the children of index i are at 2i + 1 and 2i + 2; the parent is at (i - 1) / 2.
  • poll: take the root, move the last item to the top, then sift down (swap with the smaller child until the rule holds). [1, 2, 5, 4, 3] → [2, 3, 5, 4].
  • offer: add at the end, then sift up (swap with the parent while smaller).
  • The tree is log n levels tall: offer and poll are O(log n), peek is O(1).

Largest first: a max-heap

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

public class Main {
    public static void main(String[] args) {
        PriorityQueue<Integer> bids = new PriorityQueue<>(Collections.reverseOrder());
        for (int b : new int[] { 500, 1200, 800, 1500, 300 }) bids.offer(b);
        System.out.print("Highest bids: ");
        for (int i = 0; i < 3; i++) System.out.print(bids.poll() + " ");
        System.out.println();
    }
}

Output:

Highest bids: 1500 1200 800

Objects need an order

import java.util.PriorityQueue;

class Patient {
    String name;
    int severity;
    Patient(String name, int severity) { this.name = name; this.severity = severity; }
}

public class Main {
    public static void main(String[] args) {
        PriorityQueue<Patient> er = new PriorityQueue<>();
        er.offer(new Patient("Ravi", 4));
        er.offer(new Patient("Asha", 1));
        System.out.println(er.poll().name);
    }
}

Output:

Exception in thread "main" java.lang.ClassCastException: class Patient cannot be cast to class java.lang.Comparable (Patient is in unnamed module of loader 'app'; java.lang.Comparable is in module java.base of loader 'bootstrap')
    at java.base/java.util.PriorityQueue.siftUpComparable(PriorityQueue.java:643)
    at java.base/java.util.PriorityQueue.siftUp(PriorityQueue.java:639)
    at java.base/java.util.PriorityQueue.offer(PriorityQueue.java:330)
    at Main.main(Main.java:12)

The heap must compare items. Patient has no natural order, so offering one throws ClassCastException (the same error TreeSet gave in episode 31). Episode 34 fixes it with Comparable or a Comparator passed to the constructor.

ArrayDeque refuses null

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

public class Main {
    public static void main(String[] args) {
        Queue<String> counter = new ArrayDeque<>();
        counter.offer("Asha");
        counter.offer(null);
        System.out.println(counter);
    }
}

Output:

Exception in thread "main" java.lang.NullPointerException
    at java.base/java.util.ArrayDeque.addLast(ArrayDeque.java:302)
    at java.base/java.util.ArrayDeque.offerLast(ArrayDeque.java:351)
    at java.base/java.util.ArrayDeque.offer(ArrayDeque.java:507)
    at Main.main(Main.java:8)

poll() uses null to mean "empty", so ArrayDeque (and PriorityQueue) reject null elements.

Which one?

Need Use Methods Cost
First in, first out Queue<E> q = new ArrayDeque<>() offer, poll, peek O(1)
Last in, first out Deque<E> s = new ArrayDeque<>() push, pop, peek O(1)
Both ends Deque<E> d = new ArrayDeque<>() offerFirst, pollLast, ... O(1)
Most important first PriorityQueue<E> offer, poll, peek O(log n) / O(1) peek

LinkedList also implements Queue and Deque (and allows null), but ArrayDeque is faster and uses less memory.

Common mistakes (and the real error messages)

Mistake What you see Why Fix
list.remove(0) as a queue no error; 150,000 removals are slow every item shifts ArrayDeque.poll()
queue.remove() on an empty queue java.util.NoSuchElementException remove throws when empty poll() + null check, or isEmpty()
new Stack<>() and pop() when empty java.util.EmptyStackException old Vector-based class ArrayDeque + isEmpty()
printing a PriorityQueue to see its order no error; [1, 2, 5, 4, 3] a heap, not a sorted list poll in a loop
new PriorityQueue<Patient>() then offer ClassCastException: class Patient cannot be cast to class java.lang.Comparable can't compare Patients Comparable / Comparator (episode 34)
queue.offer(null) on an ArrayDeque java.lang.NullPointerException null means "empty" don't store null

Mini project: browser back and forward

Two stacks: visiting a page pushes the current one onto back and clears forward; Back moves the current page to forward.

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

public class Main {
    static Deque<String> back = new ArrayDeque<>(), forward = new ArrayDeque<>();
    static String current = "home";

    static void visit(String page) { back.push(current); current = page; forward.clear(); }
    static void goBack()    { if (!back.isEmpty())    { forward.push(current); current = back.pop(); } }
    static void goForward() { if (!forward.isEmpty()) { back.push(current); current = forward.pop(); } }

    public static void main(String[] args) {
        visit("java"); visit("collections"); visit("queues");
        goBack(); goBack();
        System.out.println("Now: " + current + ", back " + back + ", forward " + forward);
        goForward();
        visit("heaps");
        System.out.println("Now: " + current + ", back " + back + ", forward " + forward);
    }
}

Output:

Now: java, back [home], forward [collections, queues]
Now: heaps, back [collections, java, home], forward []

Practice

  1. Reverse the word "syntax" using a stack.
  2. Simulate a printer queue of 5 jobs, printing each as it's served.
  3. Find the 3 largest numbers in {4, 19, 7, 42, 15, 8} with a PriorityQueue.
  4. Check whether "([]{()})" and "(]" are balanced (reuse the bracket checker).
Solutions
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Deque<Character> st = new ArrayDeque<>();
        for (char c : "syntax".toCharArray()) st.push(c);
        StringBuilder sb = new StringBuilder();
        while (!st.isEmpty()) sb.append(st.pop());
        System.out.println(sb);

        Queue<String> printer = new ArrayDeque<>(List.of("job1", "job2", "job3", "job4", "job5"));
        while (!printer.isEmpty()) System.out.print("printing " + printer.poll() + "; ");
        System.out.println();

        PriorityQueue<Integer> top = new PriorityQueue<>(Collections.reverseOrder());
        for (int x : new int[] { 4, 19, 7, 42, 15, 8 }) top.offer(x);
        System.out.println(top.poll() + " " + top.poll() + " " + top.poll());
    }
}

Output:

xatnys
printing job1; printing job2; printing job3; printing job4; printing job5; 
42 19 15

4. "([]{()})" → true, "(]" → false.

Quick quiz

Deque<Integer> d = new ArrayDeque<>();
d.push(1);
d.push(2);
d.offer(3);
System.out.println(d.pop() + " " + d.pollLast() + " " + d);

A) 1 3 [2] B) 2 3 [1] C) 3 1 [2] D) 2 1 [3]

Answer

B. push adds at the front, offer at the back: [2, 1, 3]. pop takes the front (2), pollLast the back (3).

2 3 [1]

Interview questions

  1. Queue vs Stack? FIFO (first in, first out) vs LIFO (last in, first out).
  2. Why prefer ArrayDeque over Stack? Stack extends Vector: synchronized, exposes index access that breaks LIFO, and is legacy. ArrayDeque is faster and does only what a deque should.
  3. ArrayDeque vs LinkedList as a queue? ArrayDeque: a circular array, better cache use, less memory, no nulls. LinkedList: node per element, allows null.
  4. poll vs remove? On an empty queue poll returns null; remove throws NoSuchElementException.
  5. How is PriorityQueue implemented? A binary heap in an array; children of i at 2i + 1, 2i + 2; offer/poll O(log n), peek O(1).
  6. Is a PriorityQueue sorted? No. Only the head is guaranteed to be the smallest; iteration order is heap order.
  7. How do you make a max-heap? new PriorityQueue<>(Collections.reverseOrder()) or a reversed Comparator.
  8. Give real uses of a stack. Undo, browser back, bracket matching, function call stack, expression evaluation, DFS.
  9. Give real uses of a priority queue. Scheduling, Dijkstra's shortest path, top-k problems, merging sorted lists.

Glossary

Term Meaning Example
Queue A line: first in, first out ticket counter
FIFO First in, first out offer then poll
offer / poll / peek Join the back / take the front / look at the front q.poll()
NoSuchElementException Thrown by remove/element on an empty queue q.remove()
Circular array An array whose end wraps around to its start inside ArrayDeque
Head index The position of the front item "now serving seat 7"
ArrayDeque A resizable circular-array deque new ArrayDeque<>()
Stack A pile: last in, first out undo history
LIFO Last in, first out plates
push / pop Add on top / remove the top s.push("bold")
java.util.Stack Legacy Vector-based stack; avoid EmptyStackException
Deque Double-ended queue: add/remove at both ends offerFirst, pollLast
PriorityQueue Hands out the smallest (highest-priority) item first emergency room
Heap (binary min-heap) A tree where every parent ≤ its children, stored in an array [1, 2, 5, 4, 3]
Sift down / sift up Swapping an item down/up until the heap rule holds after poll / offer
Max-heap Largest on top Collections.reverseOrder()
O(log n) Grows by one step each time n doubles heap height
Balanced brackets Every opener closed by the matching closer, in order {a[i]}

Summary

  • ArrayList.remove(0) shifts every item: O(n) per removal.
  • ArrayDeque is a circular array, O(1) at both ends: a queue (offer, poll, peek), a stack (push, pop, peek) and a deque.
  • Empty queue: poll/peek → null; remove/element → NoSuchElementException. No null elements.
  • Avoid the legacy Stack class.
  • PriorityQueue is a binary heap: poll gives the smallest, O(log n); its printed order is not sorted; Collections.reverseOrder() for largest first.
  • Objects in a PriorityQueue need an order: Comparable vs Comparator (episode 34).