Stacks, queues and deques

Some programs care most about which item comes out next. Press undo in an editor and your most recent change is the first to go. Send three documents to a printer and the one you sent first prints first. In a hospital emergency room, the most urgent patient is seen next, even one who arrived a minute ago. Java has a collection for each of these rules: a stack, a queue and a priority queue, plus the deque, which can work as a stack or as a queue. This lesson puts each one to work on the problems it suits.

A stack: last in, first out#

Picture a pile of plates in a kitchen cupboard. You put a clean plate on top of the pile, and when you need one you take the top plate. The plate you put down last is the first one you pick up, and the bottom plate stays where it is until every plate above it has gone.

A stack is a collection that follows the same rule. You add at the top and take from the top, and the elements underneath wait their turn. The rule is called last in, first out, or LIFO. The three stack operations have short names:

• push(x) puts x on top of the stack.
• pop() takes the top element off and returns it.
• peek() returns the top element without taking it off.

In Java you make a stack with the Deque interface and its ArrayDeque class, both in java.util. An undo history is the classic stack: every action is pushed as you make it, and undo pops the newest one.

The first line prints History: [type world, make it bold, type Hello]. A deque prints from its front to its back, and a stack made from a deque keeps its top at the front, so the newest action comes first. peek() reports Last action: type world and leaves it in place. The next two calls undo type world and then make it bold, which leaves History: [type Hello]. The third call undoes type Hello, and the fourth finds the history empty and prints Nothing to undo.

Step through it and watch the memory view under the code. It draws the deque with its front on the left, so each push adds a cell on the left and each pop takes one from there.

Key idea

A stack hands back the newest element first. On a Deque, push adds to the top, pop takes the top element off, and peek looks at it without taking it.

It prints 3, then 4 2, then [2, 1]. The first pop takes 3, the newest. Then 4 is pushed and popped straight off again, which leaves 2 on top for peek(). The last line lists what remains, top first.

Why not the Stack class?#

Java also has a class called Stack, and many people reach for it first. It dates from Java 1.0, before the Collections Framework existed, and its own documentation now recommends Deque and its classes instead. You saw the main reason in designing classes well: Stack extends Vector, an old list class, so every Stack is also a list. This program puts the same three plates on both kinds of stack:

Both stacks have blue on top, but they print in opposite orders: [red, green, blue] for the Stack, bottom first, and [blue, green, red] for the deque, top first. Then old.add(0, "gold"), a list method, slides a gold plate in under all the others. A stack should never allow that, but a Stack is a Vector, so it cannot refuse.

What a stack is good for#

Undo is one job for a stack. A stack suits any problem where the most recent item has to be dealt with first, or where items have to come back in reverse order.

Matching brackets#

Code is full of brackets that come in pairs: every ( needs a ), every [ a ] and every { a }. They must also close in the reverse of the order they opened. (a[i] + b) * 2 is fine. (a[i) + b] is not, because the ) arrives while the [ is still open. Code editors check this as you type, and with a stack you can write the check yourself:

1. 1Read the text one character at a time.
2. 2Push every opening bracket.
3. 3At a closing bracket, pop the newest opening bracket. If there was none, or the two do not belong together, the text is unbalanced.
4. 4At the end, the text is balanced only if the stack is empty. Anything left on it was opened and never closed.

It prints true, false and false. Step through the second call: ( and [ are pushed, then the ) pops [, and pair says those two do not belong together. In the third call each ) finds an opening bracket to pop, but one ( is still on the stack when the text runs out.

Two details make the code work. The stack is a Deque<Character> because a collection holds objects: push(c) boxes each char into a Character, and passing open.pop() to pair, which takes a char, unboxes it again. And in open.isEmpty() || !pair(open.pop(), c), the || only looks at its right side when the left side is false (the short-circuit rule from operators), so pop() never runs on an empty stack.

Reversing#

A stack gives elements back in the opposite order, so pushing every item and then popping them all reverses them. Push one, two, three and four, and four ends up on top, so the pops come out four, three, two, one. The same trick reverses the letters of a word or the stops of a bus route for the journey home.

The back button#

A web browser keeps a stack of the pages behind you. Opening a new page pushes the page you are leaving, and Back pops the most recent one and takes you there. Pressing Back twice takes you two pages back, in the reverse of the order you visited them.

1import java.util.ArrayDeque;
2import java.util.Deque;
3 
4public class Main {
5    public static void main(String[] args) {
6        String[] clicks = {"news", "sport", "BACK", "weather", "BACK", "BACK", "BACK"};
7        Deque<String> back = new ArrayDeque<>();
8        String current = "home";
9 
10        for (String click : clicks) {
11            if (click.equals("BACK")) {
12                // TODO: go back to the page on top of the stack, or say there is none
13            } else {
14                // TODO: remember the page you are leaving, then open the clicked one
15            }
16            System.out.println("Now on " + current);
17        }
18    }
19}

A queue: first in, first out#

A queue is the line at a counter. People join at the back and are served from the front, so whoever has waited longest goes next. You met it in the collections overview: offer adds at the back, peek looks at the front, and poll takes the front element out. The rule is first in, first out, or FIFO, the opposite of a stack.

A printer shared by an office works this way. Here each job is a record holding who sent it and how many pages it has, and the loop plays the printer, which prints one page a minute:

It prints 3 jobs waiting, next: PrintJob[owner=Ines, pages=30], using the toStringthat every record gets for free. Then the jobs come out in the order they were sent: Ines's 30 pages at minute 0, Tom's 2 pages at minute 30 and Ravi's 5 pages at minute 32, then All done at minute 37. A while (!printer.isEmpty()) loop with poll() inside is the usual way to work through a queue until nothing is left. Tom waited half an hour for two pages; a priority queue fixes that later on this page.

Two ways to ask: an exception or a special value#

Queue has a second set of methods for the same three jobs. While the queue has elements, the two sets behave the same. They differ when the job cannot be done:

The first three lines show each pair agreeing: both adds return true, peek and element both see essay.pdf, and poll and remove each take one job out. With the queue empty, they part ways. poll() and peek() return null, so the fourth line is null null, and element() throws a NoSuchElementException that stops the program on the last line. remove() would throw the same exception.

For adding, the difference only shows in a bounded queue, one with a fixed limit on its size. When it is full, add throws an IllegalStateException and offer returns false. An ArrayDeque grows whenever it needs room, so on an ArrayDeque both always succeed. Bounded queues turn up mostly in programs that run several threads at once, a topic that starts with introduction to threads.

A deque: both ends at once#

Music apps often give you two choices for a song: play it next, which puts it at the front of what is coming up, or add it to the queue, which puts it at the end. The list of songs coming up needs both ends. That is a deque, short for double-ended queue and said “deck”: a collection you can add to and take from at the front and at the back.

The Deque interface has twelve methods for its two ends. They come in the same two kinds as the queue methods: one throws when it cannot do its job, the other returns a special value.

The stack and queue methods you have used are these same methods under shorter names. push is addFirst, pop is removeFirst and peek is peekFirst, so a stack lives at the front. offer is offerLast and poll is pollFirst, so a queue joins at the back and leaves from the front. That is how one class, ArrayDeque, does both jobs.

It prints [Night Drive, Blue Hour, Paper Boats]. Night Drive was added last, but at the front, so it plays first. pollLast then removes Paper Boats from the end, and the one song left is both the first and the last: [Blue Hour] Blue Hour Blue Hour. After one more pollFirst the deque is empty, so the last line prints null null.

A palindrome check#

A palindrome reads the same forwards and backwards. In string practice you checked one with two index variables walking in from the ends. A deque does the same job without any index arithmetic: put the letters in, then take one from each end and compare, until one letter or none is left.

It prints true for “Never odd or even” and falsefor “Java”. The first loop keeps only the letters, in lower case, so the spaces and the capital N do not spoil the check. Step through the second loop and watch the deque shrink from both ends in the memory view. char first = letters.pollFirst(); unboxes the Character that pollFirst returns. That is safe here because the loop only runs while two or more letters are left. On an empty deque pollFirst returns null, and unboxing null throws a NullPointerException.

Key idea

A deque adds and removes at both ends. Use only its front and it is a stack. Add at the back and take from the front and it is a queue.

PriorityQueue: the smallest comes out first#

Think back to the emergency room. Patients are not seen in the order they arrive: each one is checked for how urgent the case is, and the most urgent goes next. A priority queue works like that. Every pollhands out the element that comes first in some order, whatever order the elements went in. Java's PriorityQueue hands out the smallest element first.

Here the elements are the days left before each of five homework deadlines, and the queue answers the question that matters: which one is due soonest?

It prints Most urgent: 1 and then 1 2 3 5 8, sorted, though the numbers went in as 5, 1, 8, 3 and 2. peek() shows the smallest element without removing it, and each poll()removes the smallest one left. “Smallest” means first in the elements' natural order, the one their compareTo method defines. A PriorityQueue is a Queue, so offer, poll and peek mean what they always mean. Only the rule for which element waits at the front has changed.

The first line is [1, 2, 8, 5, 3], neither sorted nor in the order the numbers went in, and yet the polls still come out sorted. Both facts come from the way a PriorityQueue stores its elements.

Inside a PriorityQueue: the heap#

Keeping the elements fully sorted would mean shifting many of them on almost every offer. A PriorityQueue does much less work: it keeps its elements in an arrangement called a binary heap. Picture a tree drawn upside down. One element sits at the top, the root. Below each element hang at most two more, its children, and the element above a child is its parent. The heap keeps one rule: no element is larger than its children. Follow any path down from the root and the numbers never get smaller, so the root is always the smallest of all.

Java keeps this tree in an ordinary array, filled row by row: the root at index 0, its two children at 1 and 2, their children at 3, 4, 5 and 6, and so on. Simple arithmetic finds the neighbours of the element at index i:

• its children are at 2 * i + 1 and 2 * i + 2;
• its parent is at (i - 1) / 2, in Java's whole-number division, so the parent of index 4 is (4 - 1) / 2, which is 1.

Printing a PriorityQueue, or walking it with a for-each loop, goes through that array from index 0 to the end. So what you see is the heap, which promises only that the first element is the smallest. The memory view under Deadlines.java draws the same array. Here is the queue from the Predict as a tree and as its array. Offer and poll some numbers and watch every step:

Offering: add at the end, then sift up#

1. 1The new element goes into the next free slot of the array. In the tree, that is the next free place in the bottom row, which fills from left to right.
2. 2If it is smaller than its parent, the two swap places. Then it is compared with its new parent in the same way.
3. 3It stops when its parent is smaller or equal, or when it reaches the root.

Moving an element up like this is called sifting up. Offer 0 in the lab and watch it climb to the root. Each swap lifts it one row, and a heap has few rows: 10 rows hold a thousand elements, and 20 rows hold a million. So even in a queue of a million, an offer makes at most 19 swaps.

Polling: take the root, then sift down#

1. 1The root, at index 0, is the smallest element. It comes out, and it is what poll returns.
2. 2The last element of the array moves into the empty root.
3. 3It is compared with the smaller of its children. If it is larger, the two swap places, and the same happens one row lower.
4. 4It stops when it is no larger than its children, or when it has no children.

This is sifting down. Poll the lab's queue until it is empty and read the bottom line: the numbers come out in sorted order, though the array is only ever kept as a heap.

Key idea

A PriorityQueue keeps a heap, not a sorted list. The smallest element is always at index 0, so peek and poll give the right answer, but printing the queue or looping over it shows the array in heap order.

Other orders with a Comparator#

The natural order is not always the one you want. Pass a Comparator to the constructor and the queue hands out whatever comes first by that comparator. These are the comparators from Comparable, Comparator and sorting.

Back to the printer, where Tom's two pages waited half an hour behind Ines's thirty. If the printer always takes the shortest job waiting, short jobs stop getting stuck behind long ones. Only the line that creates the queue changes:

Now Tom's job prints at minute 0 and Ravi's at minute 2, and Ines's pages still finish at minute 37. Before, the three jobs spent 62 minutes waiting between them; now they spend 9. The loop did not change at all, because printer was declared as a Queue and both classes keep that promise.

For the opposite of the natural order, Comparator.reverseOrder() is a ready-made comparator, and reversed() turns around any comparator you build:

It prints 95 88, the two highest scores, and Ines Ravi, the owners of the two biggest jobs.

A priority queue can also pick the largest few items out of a long list without sorting all of it. Keep a queue of at most three scores: offer each score, and whenever the queue holds four, poll the smallest. The weakest of the best three always waits at the front, ready to be dropped.

1import java.util.PriorityQueue;
2 
3public class Main {
4    public static void main(String[] args) {
5        int[] scores = {72, 95, 61, 88, 79, 99, 54, 83};
6        PriorityQueue<Integer> best = new PriorityQueue<>();
7 
8        // TODO: offer each score, and poll whenever best holds more than three
9 
10        while (!best.isEmpty()) {
11            System.out.println(best.poll());
12        }
13    }
14}

Costs, and choosing between them#

Once a collection holds thousands of elements, the work each operation does starts to matter. Here is that work, counted in steps rather than seconds:

One detail hides in the first row. Now and then an ArrayDeque's array fills up, and it copies every element into a bigger array, as an ArrayList does. That happens rarely enough that, averaged over many operations, the cost of each one stays the same. The documentation calls this amortized constant time.

Which one to use#

For the first three rows, create an ArrayDeque. Declare the variable as the interface whose methods you call, Deque or Queue, so the rest of the program only depends on the rule it needs.

Further reading#

• The Deque interface in the Java SE 25 API documentation, with its stack and queue method tables
• ArrayDeque in the Java SE 25 API documentation
• PriorityQueue in the Java SE 25 API documentation
• Storing elements in stacks and queues, on dev.java