Skip to content

Intermediate · The collections framework · topic 35 of 60 · 25 min

Queues, stacks and priority queues

Explanation

A Queue processes elements first-in, first-out (FIFO) with offer, poll and peek. ArrayDeque works as both a fast queue and a stack (push, pop, peek; last-in, first-out). PriorityQueue always gives the smallest element first (a min-heap) or the most important one with a Comparator. Choose collections by how you will use them.

Queue: first in, first out

A queue serves items in arrival order, like a token system at a clinic. In Java, Queue is an interface; ArrayDeque is the usual implementation. offer adds at the tail, poll removes from the head (null when empty), and peek looks at the head without removing it.

java
Queue<String> tokens = new ArrayDeque<>();
tokens.offer("T1");
tokens.offer("T2");
tokens.offer("T3");
System.out.println(tokens.peek());   // T1 (still there)
System.out.println(tokens.poll());   // T1 (removed)
System.out.println(tokens);          // [T2, T3]

Queue also has add, remove and element, which THROW an exception when they fail (for example remove on an empty queue), while offer, poll and peek return false or null instead.

Stack with ArrayDeque

java
Deque<String> undo = new ArrayDeque<>();
undo.push("typed 'Hello'");
undo.push("made bold");
undo.push("deleted line");
System.out.println(undo.pop());      // deleted line (last in, first out)
System.out.println(undo.peek());     // made bold
Deque ("deck", double-ended queue) supports both ends.

The old java.util.Stack class extends Vector, is synchronised (slower) and is considered legacy. The Javadoc itself recommends Deque/ArrayDeque for stacks.

PriorityQueue: most important first

java
PriorityQueue<Integer> pq = new PriorityQueue<>(List.of(40, 10, 30, 20));
System.out.println(pq.poll());   // 10 (smallest first: a min-heap)
System.out.println(pq.poll());   // 20

record Patient(String name, int severity) {}       // 1 = most critical
PriorityQueue<Patient> er = new PriorityQueue<>(Comparator.comparingInt(Patient::severity));
er.offer(new Patient("Asha", 3));
er.offer(new Patient("Ravi", 1));
er.offer(new Patient("Om", 2));
System.out.println(er.poll().name());   // Ravi (most critical)
Careful: Printing a PriorityQueue or looping over it does NOT show sorted order; only poll() returns elements in priority order. The internal array is a heap, which is only partly ordered. Also, PriorityQueue offer and poll take O(log n), and peek is O(1).

Utility methods and choosing a collection

Collections offers helpers: Collections.max, min, frequency, reverse, shuffle, unmodifiableList and nCopies. To choose a collection, ask how you will USE it.

NeedUse
Ordered list, access by indexArrayList
Unique items, fast containsHashSet (LinkedHashSet for order, TreeSet for sorted)
Lookup by keyHashMap (LinkedHashMap / TreeMap for order)
FIFO queue or LIFO stackArrayDeque
Always take the smallest / highest priorityPriorityQueue
Many threads at onceConcurrentHashMap, BlockingQueue (module 9)
Think of it like this: A queue is the line at a railway ticket counter. A stack is a pile of plates in a canteen: the last plate put on top is the first taken. A priority queue is a hospital emergency room: the most critical patient is seen first, whoever arrived earlier.
Tip: When an interview problem says "process in order of arrival" think Queue; "undo" or "matching brackets" think stack; "always the next smallest/largest" or "top k" think PriorityQueue.

Need help?

Stuck on a word or an idea? Search this course, or every course, and jump straight to the explanation or a worked question.

Try:

Watch the lesson

Queues, stacks and priority queues · 1/6

Queues and stacks

In this lesson you will use queues, stacks and priority queues.

Prefer a video by a teacher? Find free videos on “java queue deque arraydeque priorityqueue stack tutorial” on YouTube ↗

In real life: Hospital emergency triage

An emergency department's system queues patients by severity (1 = critical, 5 = minor) using a PriorityQueue, with arrival time as a tie-break so equally severe patients are seen in order.

java
record Arrival(String name, int severity, int arrivedMin) {}
PriorityQueue<Arrival> triage = new PriorityQueue<>(
        Comparator.comparingInt(Arrival::severity).thenComparingInt(Arrival::arrivedMin));
triage.offer(new Arrival("Asha", 3, 5));
triage.offer(new Arrival("Ravi", 1, 9));
triage.offer(new Arrival("Om", 3, 2));
while (!triage.isEmpty()) System.out.println(triage.poll().name());   // Ravi, Om, Asha

Practice (0/3 done)

Task 1 · Question

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

Task 2 · Code · Javascript

The same stack algorithm in JavaScript, which runs here: write isBalanced(s) that returns true when every (, [ and { is closed in the right order, using an array as a stack.

Task 3 · Practice

Simulate a clinic: patients arrive as records Patient(name, severity, arrival). Use a PriorityQueue with a comparator (severity, then arrival) and print the order in which they are seen. Then use an ArrayDeque as a simple FIFO queue for the pharmacy counter and print its order.

Quick quiz

Question 1

1.Which removes and returns the head of a Queue, or null if it is empty?

Question 2

2.A PriorityQueue<Integer> created with no comparator gives…

Question 3

3.Which class should implement a stack in modern Java?

Question 4

4.Which order does a stack follow?

Read more (free)

Open a question to see the answer and why. The first ones are this topic's own quiz, so try the quiz above before you peek.

Which removes and returns the head of a Queue, or null if it is empty?

Answer: poll()

poll returns null when empty; remove throws.

A PriorityQueue<Integer> created with no comparator gives…

Answer: The smallest first

The default is a min-heap by natural order.

Which class should implement a stack in modern Java?

Answer: ArrayDeque

ArrayDeque is recommended over Stack.

Which order does a stack follow?

Answer: LIFO

Last in, first out.

Which is the best tool for a large FIFO queue in Python?Related

Answer: collections.deque with append and popleft

deque adds and removes at both ends in O(1). list.pop(0) shifts every item, which is O(n).

From Stacks and queues

std::priority_queue<int> pq; after pushing 4, 9 and 2, what is pq.top()?Related

Answer: 9

By default priority_queue is a max-heap.

From set, stack, queue, deque and priority_queue

Why push (priority, counter, item) instead of (priority, item)?Related

Answer: Equal priorities then compare the counter, so items are never compared and arrival order is kept

Without the counter, a tie compares the items, which may raise TypeError or give an unwanted order.

From Heaps and priority queues

A circular queue has capacity 4, head = 3 and count = 2. Which slot does the next enqueue use?Related

Answer: 1

(3 + 2) % 4 = 1. The items sit in slots 3 and 0; the next one goes in slot 1.

From Queues and deques

Pass the quiz (60% or more) or mark this topic as done when you are ready.

Your progress is saved on this device only.

Next: Lambdas and functional interfaces →

Next steps

  1. This is the last topic of “The collections framework”. The module exam comes next.
  2. Module 7 exam: The collections framework · 12 questions · 25 min, without help. 5 topics of this module still to finish first.
  3. Then the next module, Lambdas, streams and files. 60 topics left in the course before the final exam.

← Previous: Sorting with Comparable and Comparator