The labs on this site need JavaScript to run. The same content is written out below.

Learn › Java › Collections

Stack, queue, priority queue

Insertion order and removal order

Even when you insert the same five numbers in the same order, the order in which they come out depends on the data structure. A stack returns the most recently inserted value first, a queue returns the earliest inserted value first, and a priority queue returns the smallest value first.

Checked against real execution · Checked against the real ArrayDeque and PriorityQueue on JDK 21

Concepts in this lab

Stack, queue, deque

A stack takes out the most recently added item first (LIFO), a queue takes out the earliest added item first (FIFO), and a deque lets you add and remove items at both ends. In Java, ArrayDeque is the recommended implementation for both stacks and queues.

Heap and priority queue

A heap is a complete binary tree in which each parent node is always less than or equal to its child nodes (a min-heap) or greater than or equal to them (a max-heap). It lets you see the smallest (or largest) value in O(1) and remove it in O(log n), so it is used to implement a priority queue. Java's PriorityQueue is implemented with a heap. It shares only its name with the heap that is a memory area of the JVM.

Time complexity (big-O notation)

This notation shows how fast the number of operations of an algorithm grows as the input size n grows. O(1) means constant regardless of size, O(log n) means only one more step when the size doubles, O(n) means proportional to the size, and O(n²) means proportional to the square of the size. It is the basis for judging which approach holds up as the amount of data grows.

Try these

• Default settings — A priority queue. The smallest value comes out first, regardless of the insertion order.
• Stack — The 9, which was inserted last, comes out first.
• Queue — The values come out in insertion order.
• Descending order into a priority queue — On every insertion, the new value moves all the way up to the top.

Running with the default settings

1. offer(5): The value is placed at the end of the array and then moves up, swapping places with its parent while it is smaller than the parent. It is the first value, so it stays at the top.
2. offer(2): The value is placed at the end of the array and then moves up, swapping places with its parent while it is smaller than the parent. It moved up 1 level and reached the top (the place of the smallest value).
3. offer(8): The value is placed at the end of the array and then moves up, swapping places with its parent while it is smaller than the parent. It is not smaller than its parent, so it stays where it is.
4. offer(1): The value is placed at the end of the array and then moves up, swapping places with its parent while it is smaller than the parent. It moved up 2 levels and reached the top (the place of the smallest value).
5. offer(9): The value is placed at the end of the array and then moves up, swapping places with its parent while it is smaller than the parent. It is not smaller than its parent, so it stays where it is.
6. poll(): Removes the smallest value, 1, from the top. The last value in the array is moved to the empty top and then moves down, swapping places with the smaller of its two children (it moved down 2 levels).
7. poll(): Removes the smallest value, 2, from the top. The last value in the array is moved to the empty top and then moves down, swapping places with the smaller of its two children (it moved down 1 level).
8. poll(): Removes the smallest value, 5, from the top. If any values remain, the last value in the array is moved to the empty top. This time no swap was needed.
9. poll(): Removes the smallest value, 8, from the top. If any values remain, the last value in the array is moved to the empty top. This time no swap was needed.
10. poll(): Removes the smallest value, 9, from the top. If any values remain, the last value in the array is moved to the empty top. This time no swap was needed.

Result of this run

• A priority queue returns the smallest value first, regardless of the insertion order. The internal array is not fully sorted. It keeps only the condition that a parent is less than or equal to its children (a heap). That is why the top is always the minimum value.
• Insertion and removal swap places only as many times as the height of the tree, so they are O(log n). This is much cheaper than sorting everything every time. A priority queue is used for task scheduling, finding the top N items, and shortest-path algorithms.

Code

PriorityQueue<Integer> pq = new PriorityQueue<>();   // smaller values first
for (int x : List.of(5, 2, 8, 1, 9)) pq.offer(x);

while (!pq.isEmpty()) System.out.print(pq.poll() + " ");

Assumptions of this model

The removal order and the changes to the internal array of the priority queue were checked by running the real ArrayDeque and PriorityQueue on JDK 21 on this PC (the internal array matched after every insertion and after every removal). By default, PriorityQueue returns the smallest value first, and you can change the ordering by supplying a Comparator.

Previous lab: Kinds of Set and Map · Next lab: Removing during iteration