Queues, Stacks & Deques

Some problems care about the order in which items are processed: first come, first served (a queue), last in, first out (a stack), or most urgent first (a priority queue). Java's Deque and PriorityQueue cover all three efficiently.

A queue: first in, first out

JAVA

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

public class Main {
    public static void main(String[] args) {
        Queue<String> support = new ArrayDeque<>();
        support.offer("ticket-1");
        support.offer("ticket-2");
        support.offer("ticket-3");
        System.out.println("Next: " + support.peek());
        while (!support.isEmpty()) {
            System.out.println("Handling " + support.poll());
        }
        System.out.println(support.poll());
    }
}

Output

Next: ticket-1
Handling ticket-1
Handling ticket-2
Handling ticket-3
null

offer adds to the back, poll removes from the front and peek looks without removing. poll and peek return null on an empty queue; the alternatives add, remove and element throw exceptions instead.

A stack: last in, first out

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("home");
        history.push("products");
        history.push("mug");
        System.out.println("Back to: " + history.pop());
        System.out.println("Back to: " + history.pop());
        System.out.println("Current top: " + history.peek());
    }
}

Output

Back to: mug
Back to: products
Current top: home

push and pop work at the front of a Deque. Prefer ArrayDeque to the old Stack class, which is synchronised and slower.

Checking brackets with a stack

JAVA

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

public class Main {
    static boolean balanced(String s) {
        Deque<Character> open = new ArrayDeque<>();
        for (char c : s.toCharArray()) {
            switch (c) {
                case '(', '[', '{' -> open.push(c);
                case ')' -> { if (open.isEmpty() || open.pop() != '(') return false; }
                case ']' -> { if (open.isEmpty() || open.pop() != '[') return false; }
                case '}' -> { if (open.isEmpty() || open.pop() != '{') return false; }
                default -> { }
            }
        }
        return open.isEmpty();
    }

    public static void main(String[] args) {
        System.out.println(balanced("{a[b(c)d]e}"));
        System.out.println(balanced("(a[b)c]"));
        System.out.println(balanced("(("));
    }
}

Output

true
false
false

Deque: both ends

JAVA

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

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

Output

[1, 2, 3, 4]
1 4
[2, 3]

A double-ended queue supports adding and removing at both ends, so one class serves as queue, stack, or sliding window.

PriorityQueue: most important first

JAVA

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

record Task(String name, int priority) {}

public class Main {
    public static void main(String[] args) {
        PriorityQueue<Task> tasks = new PriorityQueue<>(Comparator.comparingInt(Task::priority));
        tasks.add(new Task("Reply to email", 3));
        tasks.add(new Task("Fix outage", 1));
        tasks.add(new Task("Update docs", 5));
        tasks.add(new Task("Review PR", 2));
        while (!tasks.isEmpty()) {
            System.out.println(tasks.poll());
        }
    }
}

Output

Task[name=Fix outage, priority=1]
Task[name=Review PR, priority=2]
Task[name=Reply to email, priority=3]
Task[name=Update docs, priority=5]

A PriorityQueue always hands out the smallest element (by natural order or a comparator) next. It's backed by a heap: adding and polling are fast, but iterating over it does not give sorted order — only poll does.

Collections at a glance

Need	Use
Ordered list, access by index	`ArrayList`
Unique items, fast lookup	`HashSet` (sorted: `TreeSet`)
Key → value lookup	`HashMap` (sorted: `TreeMap`)
FIFO queue or LIFO stack	`ArrayDeque`
Always take the smallest/largest next	`PriorityQueue`
Shared between threads	`ConcurrentHashMap`, `ConcurrentLinkedQueue`, `BlockingQueue` (lesson 52)

Try it yourself

Simulate a print queue where urgent jobs jump ahead.

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

record Job(String doc, boolean urgent, int order) {}

public class Main {
    public static void main(String[] args) {
        PriorityQueue<Job> queue = new PriorityQueue<>(
            Comparator.comparing((Job j) -> !j.urgent()).thenComparingInt(Job::order));
        String[] docs = {"report.pdf", "invoice.pdf", "photo.png", "contract.pdf"};
        boolean[] urgent = {false, true, false, true};
        for (int i = 0; i < docs.length; i++) queue.add(new Job(docs[i], urgent[i], i));
        while (!queue.isEmpty()) System.out.println("Printing " + queue.poll().doc());
    }
}

Edit the code, copy it into Main.java and run java Main.java (Java 25+). How to set up Java

Output

Printing invoice.pdf
Printing contract.pdf
Printing report.pdf
Printing photo.png

PreviousSorting & Comparators NextLambdas