The Project | About Us | Contribute | Donations | License
HOME My courses Completed
◄ Previous
◄

Stack

Next ►
►

In the previous lesson you saw that swapping pollFirst for pollLast on a single line turned a breadth-first traversal into a depth-first one. That line contains the whole difference between a queue and a stack: the queue serves whoever has been waiting longest, the stack serves the last one to arrive.

A stack is LIFO: Last In, First Out. It is the structure of a pile of plates, of a heap of papers in a tray, of the "undo" button of any editor. And it is, above all, the structure the Java virtual machine itself runs on: every time you call a method, the JVM pushes a frame with its local variables, and when the method finishes it pops it. That mechanism —the call stack— explains the StackOverflowError you have probably already seen when getting a recursion wrong in 03-03.

This lesson has a peculiarity: the class Java ships under the name Stack is discouraged, and you will see exactly why with a demonstration that surprises. The correct way to use a stack in modern Java is Deque, the interface you already know. You will finish by implementing your own stack with an array to understand the structure from the inside, solving two classic problems —balanced brackets and a history with undo and redo— and adding to BiblioTech the stack that lets the last catalogue operation be cancelled.

Contents

  1. LIFO: the semantics of a stack
  2. What a stack is really for
  3. The JVM's call stack and StackOverflowError
  4. The legacy Stack class
  5. Why Stack is discouraged
  6. Deque as a stack: the official recommendation
  7. Comparison table of the three options
  8. Implementing your own stack with an array
  9. Practical case: balanced brackets
  10. Practical case: a history with undo and redo
  11. From recursion to iteration with an explicit stack
  12. Applying it to BiblioTech
  13. Common Mistakes and Tips
  14. Exercises

  1. LIFO: the semantics of a stack

A stack is a collection where elements come in and go out at the same end, called the top.

flowchart TB
    P["push / pop / peek"] --> C["TOP: modification"]
    C --> B["withdrawal"]
    B --> A["registration"]
    A --> F["BOTTOM (the first one in,<br/>the last one out)"]

Its three fundamental operations:

Operation What it does
push(e) Places an element on the top
pop() Removes and returns the element on the top
peek() Inspects the top without removing it

The behaviour in a sequence:

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

Deque<String> stack = new ArrayDeque<>();

stack.push("add:978-0000000001");
stack.push("add:978-0000000002");
stack.push("drop:978-0000000001");

System.out.println(stack.peek());   // drop:978-0000000001  (the last one in)
System.out.println(stack.pop());    // drop:978-0000000001
System.out.println(stack.pop());    // add:978-0000000002
System.out.println(stack.size());   // 1

The exit order is exactly the reverse of the entry order. And that property —"it reverses the order"— is the key to nearly all its applications: undoing a sequence of actions is redoing them backwards, evaluating a nested expression is closing whatever was opened last, and returning from a call is picking up the one immediately before.

Compare the module's three policies:

Policy Who goes out first Metaphor Structure
FIFO (queue) The one who has waited longest Supermarket queue Queue / Deque
LIFO (stack) The last to arrive Pile of plates Deque
Priority The most urgent A hospital's emergency department PriorityQueue

  1. What a stack is really for

Four families of applications, and all four turn up constantly in real programming.

1. Undo. Every user action is pushed; undoing is popping the last one and reverting it. If you also push the undone actions onto a second stack, you get redo for free. You will implement it in section 10.

2. Expression evaluation and parsing. Any nested structure —brackets, braces, HTML tags, code blocks— is validated and processed with a stack: every opening is pushed and every closing must match the top. Compilers, including Java's, use stacks to parse source code. That is section 9.

3. Depth-first search (DFS). As you saw in 05-07, replacing the queue with a stack turns a breadth-first traversal into a depth-first one. The stack keeps track of "where I was" while the algorithm descends a branch.

4. The JVM's call stack. It is not an application you program: it is how the language works. And it deserves its own section.

  1. The JVM's call stack and StackOverflowError

Every thread in a Java application has its own call stack. Every time a method is invoked, the JVM pushes a stack frame containing:

  • The method's parameters.
  • Its local variables.
  • The return address: which instruction to go back to when it finishes.

When the method finishes, its frame is popped and execution continues where the caller left off.

public class Trace {
    public static void main(String[] args) {
        System.out.println(calculateFine(20, 15, 0.25));
    }
    static double calculateFine(int days, int term, double rate) {
        return applyCap(daysLate(days, term) * rate);
    }
    static int daysLate(int days, int term) { return Math.max(0, days - term); }
    static double applyCap(double fine) { return Math.min(fine, 20.0); }
}
flowchart TB
    subgraph stack["Call stack at the moment of executing daysLate"]
        F3["daysLate(20, 15)<br/>← TOP"]
        F2["calculateFine(20, 15, 0.25)"]
        F1["main(args)<br/>← BOTTOM"]
    end
    F3 --> F2 --> F1

When daysLate returns 5, its frame is popped and execution goes back to calculateFine, which then pushes the frame for applyCap. It is exactly a stack: the last thing pushed is the first thing removed.

And now the error that connects with 03-03. A thread's stack has a limited size (typically 512 KB or 1 MB). If you push too many frames —normally because of a recursion with no base case or one that is too deep—, it runs out:

static int countForever(int n) {
    return countForever(n + 1);      // never stops: each call pushes a frame
}
// Exception in thread "main" java.lang.StackOverflowError

StackOverflowError is an Error, not an Exception: it signals a failure of the runtime environment, not a condition your program should handle. Its two typical causes:

  • Recursion with no base case, or with an unreachable base case. That is a bug: fix the algorithm.
  • Correct recursion but too deep for the stack's size. At around 10,000 levels it usually fires. The solution is to turn the recursion into iteration with an explicit stack, which is exactly what you will do in section 11.

The difference between the call stack and a stack you create is substantial: the first lives in a per-thread reserved memory area of fixed size; the second is a normal object on the heap, which grows for as long as there is memory. Hence a recursion a million levels deep blows up while its iterative equivalent with ArrayDeque works without trouble. Memory, the collector and the -Xss that adjusts the stack size are subjects for module 10-07.

  1. The legacy Stack class

Java has shipped since version 1.0 a class literally called Stack:

import java.util.Stack;

Stack<String> stack = new Stack<>();
stack.push("add:978-0000000001");
stack.push("drop:978-0000000002");

System.out.println(stack.peek());     // drop:978-0000000002
System.out.println(stack.pop());      // drop:978-0000000002
System.out.println(stack.empty());    // false
System.out.println(stack.search("add:978-0000000001"));   // 1

Its API:

Method What it does If it is empty
push(e) Pushes —
pop() Pops and returns EmptyStackException
peek() Inspects the top EmptyStackException
empty() Is it empty? —
search(o) Distance from the top (1 for the top), or -1 —

Two striking details already in this table. empty() instead of isEmpty() (although the latter also exists, inherited). And search returns a 1-based position, not 0-based, which breaks the convention of all the rest of Java.

About EmptyStackException: it is a RuntimeException thrown when you pop or peek on an empty stack. How to catch it is module 6; here it is enough to check isEmpty() first.

  1. Why Stack is discouraged

The JDK's official documentation says it plainly: "A more complete and consistent set of LIFO stack operations is provided by the Deque interface, which should be used in preference to this class". There are three reasons, and the third is spectacular.

Reason 1: it extends Vector

public class Stack<E> extends Vector<E> { ... }

Vector is a list with access by index. By inheriting from it, Stack exposes the whole API of a list, breaking the very semantics of a stack:

Stack<String> stack = new Stack<>();
stack.push("A");
stack.push("B");
stack.push("C");

// All of this COMPILES and works on a "stack":
stack.get(0);              // access by index
stack.add(1, "X");         // insert in the middle
stack.remove(0);           // remove from the bottom
stack.set(0, "Z");         // modify the bottom

A stack that lets you touch the bottom is not a stack: it is a list with three extra methods. And there is no structural guarantee left to protect. It is also a textbook example of the misuse of inheritance, exactly the mistake you studied in 03-05: Stack is not a Vector; a stack uses internal storage. It should have been composition.

Reason 2: it is synchronised

Vector synchronises all its methods, so Stack does too. That means every push and every pop acquires and releases a lock, even in a single-threaded program where it is absolutely useless.

And the cost does not buy real safety: method-by-method synchronisation does not make compound sequences atomic. This code still has a race condition:

if (!stack.isEmpty()) {        // another thread can empty it right here
    String x = stack.pop();    // EmptyStackException
}

It is exactly the same story as Hashtable and Vector from 05-05: Java 1.0 global synchronisation, which is expensive and does not solve the problem. For real concurrency, module 8.

Reason 3: the iterator traverses the opposite way to what you expect

This is the most surprising one, and it deserves to be seen running.

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

Stack<String> stack = new Stack<>();
stack.push("first");
stack.push("second");
stack.push("third");       // the TOP

System.out.println("Stack toString: " + stack);
System.out.print("Stack for-each: ");
for (String s : stack) { System.out.print(s + " "); }

Deque<String> deque = new ArrayDeque<>();
deque.push("first");
deque.push("second");
deque.push("third");       // the TOP

System.out.println("\nDeque toString: " + deque);
System.out.print("Deque for-each: ");
for (String s : deque) { System.out.print(s + " "); }

System.out.println("\nStack.pop(): " + stack.pop());
System.out.println("Deque.pop(): " + deque.pop());
Stack toString: [first, second, third]
Stack for-each: first second third
Deque toString: [third, second, first]
Deque for-each: third second first
Stack.pop(): third
Deque.pop(): third

Stack traverses from the bottom to the top: the reverse of the order in which the elements will come out. Since it inherits Vector's iterator, it walks the internal array from position 0 onwards, and in Stack position 0 is the bottom. So pop() returns "third" but the iterator starts with "first".

ArrayDeque does the right thing: it traverses from the top, in the same order the elements would come out.

It is a serious inconsistency, because writing a loop that "processes the stack in order" produces the opposite of the expected result, with no warning at all.

flowchart TB
    subgraph S["Stack: iterator from BOTTOM to TOP"]
        direction TB
        S1["first (bottom) ← starts here"]
        S2["second"]
        S3["third (top) ← comes out first with pop"]
        S1 --> S2 --> S3
    end
    subgraph D["ArrayDeque: iterator from TOP to BOTTOM"]
        direction TB
        D3["third (top) ← starts here, and comes out first"]
        D2["second"]
        D1["first (bottom)"]
        D3 --> D2 --> D1
    end

The verdict

Stack is not formally marked as deprecated —that would break too much old code— but it must not be used in new code. You will only use it if you come across it in a legacy project.

  1. Deque as a stack: the official recommendation

Deque<String> stack = new ArrayDeque<>();

stack.push("add:978-0000000001");     // = addFirst
stack.push("drop:978-0000000002");

System.out.println(stack.peek());     // = peekFirst. null if it is empty
System.out.println(stack.pop());      // = removeFirst. NoSuchElementException if empty
System.out.println(stack.isEmpty());
System.out.println(stack.size());

The three stack methods are aliases for operations on the Deque's head:

Stack method Equivalent to Behaviour if it is empty
push(e) addFirst(e) —
pop() removeFirst() NoSuchElementException
peek() peekFirst() Returns null

Notice the asymmetry in the last column, which has to be kept in mind: pop() throws an exception but peek() returns null. If you want consistency, you have the two complete families from 05-07: pollFirst() returns null instead of throwing, and getFirst() throws instead of returning null.

A safe pattern for consuming a whole stack:

// Option 1: check first
while (!stack.isEmpty()) {
    process(stack.pop());
}

// Option 2: the idiom from 05-07, with no prior check
String op;
while ((op = stack.pollFirst()) != null) {
    process(op);
}

Why is the top the head of the Deque and not the tail? For performance: in an ArrayDeque, inserting and extracting at the head is O(1) thanks to the circular array, just as at the back. And push/pop on the head let the iterator traverse in the exit order, which is what fixes Stack's defect.

Recommended declaration:

Deque<String> stack = new ArrayDeque<>();

Not ArrayDeque<String> stack, and not Stack<String> stack. The Deque interface documents the intent and lets you change the implementation.

  1. Comparison table of the three options

Aspect Stack ArrayDeque as a stack LinkedList as a stack
Internal structure Vector (synchronised array) Circular array Linked nodes
push / pop O(1), with a lock O(1) with no lock O(1)
Synchronised Yes (a useless cost) No No
Iterator order Bottom → top (wrong) Top → bottom (right) Top → bottom
Exposes a list API Yes (get, add(i,e)) No Yes (it is a List)
Memory per element ~4-8 bytes ~4-8 bytes ~28 bytes
Cache locality Good Excellent Poor
Allows null Yes No Yes
On pop when empty EmptyStackException NoSuchElementException NoSuchElementException
Recommended No Yes Only if you need null or List

Conclusion: Deque<X> stack = new ArrayDeque<>(). It is the right answer unless you need to store null (then LinkedList) or you are in legacy code that already uses Stack.

  1. Implementing your own stack with an array

Implementing a stack by hand is a short exercise that clears up the structure once and for all. All you need is an array and an index.

package com.nexussoftware.bibliotech.service;

import java.util.Arrays;
import java.util.EmptyStackException;

/**
 * A stack of strings implemented on top of an array, for teaching purposes.
 * It is, in essence, what ArrayDeque and Stack do internally.
 */
public class ArrayStack {

    private static final int INITIAL_CAPACITY = 10;

    private String[] elements;
    private int      top;       // index of the NEXT free position = number of elements

    public ArrayStack() {
        this(INITIAL_CAPACITY);
    }

    public ArrayStack(int initialCapacity) {
        this.elements = new String[Math.max(initialCapacity, 1)];
        this.top = 0;
    }

    /** Pushes. Amortised O(1): it only copies when the array fills up. */
    public void push(String element) {
        if (top == elements.length) {
            // MULTIPLICATIVE growth (x2), just like ArrayList (05-03):
            // it is what makes the average cost per push constant.
            elements = Arrays.copyOf(elements, elements.length * 2);
        }
        elements[top] = element;
        top++;
    }

    /** Pops. O(1). */
    public String pop() {
        if (isEmpty()) {
            // Module 6 teaches how to handle this; here we only signal it.
            throw new EmptyStackException();
        }
        top--;
        String element = elements[top];
        elements[top] = null;        // ESSENTIAL: without it, the object cannot be
                                     // collected while the stack lives (a memory leak).
        return element;
    }

    /** Inspects the top without removing it. O(1). */
    public String peek() {
        if (isEmpty()) { throw new EmptyStackException(); }
        return elements[top - 1];        // top points at the NEXT free position
    }

    /** A safe version: null instead of an exception. */
    public String peekOrNull() {
        return isEmpty() ? null : elements[top - 1];
    }

    public boolean isEmpty() { return top == 0; }
    public int     size()    { return top; }

    public void clear() {
        Arrays.fill(elements, 0, top, null);     // releases every reference
        top = 0;
    }

    /** Traverses from the TOP to the BOTTOM: the exit order, as it should be. */
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("[");
        for (int i = top - 1; i >= 0; i--) {     // backwards: from the top to the bottom
            sb.append(elements[i]);
            if (i > 0) { sb.append(", "); }
        }
        return sb.append("]").toString();
    }
}

Usage:

ArrayStack stack = new ArrayStack(2);     // a small capacity to force growth
stack.push("add:978-0000000001");
stack.push("add:978-0000000002");
stack.push("drop:978-0000000001");        // here the array doubles

System.out.println(stack);                // [drop:978-0000000001, add:..002, add:..001]
System.out.println("Top:       " + stack.peek());
System.out.println("Popped:    " + stack.pop());
System.out.println("Remaining: " + stack.size());

Three details of this implementation deserve attention, because they are exactly the ones that appear in the JDK's real code:

  1. top points at the next free position, so it coincides with the number of elements and peek() has to look at top - 1. The alternative —having it point at the last element and be -1 when empty— also works, but forces more adjustments.
  2. elements[top] = null in pop. Without that line, the array would keep referring to an object that is no longer part of the stack, preventing the collector from freeing it: a silent memory leak. It is the same care you took in the ArrayCatalog of 05-01 and that ArrayList applies in its remove.
  3. Growth is multiplicative, which gives amortised O(1) cost for the same reason as in ArrayList (05-03).

Compare it with what you gain by using ArrayDeque: generics, null checking, a correct iterator, descendingIterator, contains, removeIf, toArray, and twenty-five years of testing. Your own implementation is for learning, not for production.

  1. Practical case: balanced brackets

It is the canonical stack problem and it turns up in any parser. Given a string with (, [ and {, check whether they are correctly opened and closed.

The idea: every opening symbol is pushed. Every closing symbol must match the one on the top; if it does, it is popped. At the end the stack must be empty.

package com.nexussoftware.bibliotech.service;

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

public final class ExpressionValidator {

    private ExpressionValidator() { }

    /** Each closing symbol, with its matching opening one. */
    private static final Map<Character, Character> PAIRS =
        Map.of(')', '(', ']', '[', '}', '{');

    public static boolean isBalanced(String expression) {
        if (expression == null) { return true; }
        Deque<Character> stack = new ArrayDeque<>();

        for (char c : expression.toCharArray()) {
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);                      // an opening: it is pushed
            } else if (PAIRS.containsKey(c)) {
                // a closing: the top MUST be its matching opening
                if (stack.isEmpty() || stack.pop() != PAIRS.get(c)) {
                    return false;
                }
            }
            // any other character is ignored
        }
        // If any opening is left unclosed, the stack is not empty
        return stack.isEmpty();
    }

    /** A version that also reports WHERE the problem is. */
    public static String diagnose(String expression) {
        if (expression == null) { return "OK (null string)"; }
        Deque<Character> symbols   = new ArrayDeque<>();
        Deque<Integer>   positions = new ArrayDeque<>();   // a parallel stack of positions

        for (int i = 0; i < expression.length(); i++) {
            char c = expression.charAt(i);
            if (c == '(' || c == '[' || c == '{') {
                symbols.push(c);
                positions.push(i);
            } else if (PAIRS.containsKey(c)) {
                if (symbols.isEmpty()) {
                    return String.format("Close '%c' with no opening at position %d", c, i);
                }
                char expected = PAIRS.get(c);
                char opened   = symbols.pop();
                int  openedAt = positions.pop();
                if (opened != expected) {
                    return String.format(
                        "Expected to close '%c' (opened at %d) but found '%c' at %d",
                        opened, openedAt, c, i);
                }
            }
        }
        if (!symbols.isEmpty()) {
            return String.format("Missing close for '%c' opened at position %d",
                                 symbols.peek(), positions.peek());
        }
        return "OK";
    }

    public static void main(String[] args) {
        String[] cases = {
            "(title AND author)",
            "((title OR isbn) AND (year > 2000))",
            "[type=Book] AND {rate<0.30}",
            "(title AND author",
            "title AND author)",
            "([type=Book)]",
            ""
        };
        for (String expr : cases) {
            System.out.printf("%-38s %-5s  %s%n",
                    "\"" + expr + "\"",
                    isBalanced(expr) ? "OK" : "BAD",
                    diagnose(expr));
        }
    }
}
"(title AND author)"                   OK     OK
"((title OR isbn) AND (year > 2000))" OK     OK
"[type=Book] AND {rate<0.30}"          OK     OK
"(title AND author"                    BAD    Missing close for '(' opened at position 0
"title AND author)"                    BAD    Close ')' with no opening at position 16
"([type=Book)]"                        BAD    Expected to close '[' (opened at 1) but found ')' at 11
""                                     OK     OK

Why only a stack works. Correct nesting requires the last symbol opened to be the first one closed: that is LIFO, literally. With a simple counter, ([)] would pass validation —there are two openings and two closings— but it is badly nested. The stack detects it because it remembers what was opened and in what order.

Notice too the technique of the two parallel stacks in diagnose: one holds the symbols and the other their positions, and both are pushed and popped together. It is a common device when you need to carry extra information for each level; the alternative, in modern Java, would be a stack of a record Opening(char symbol, int position).

  1. Practical case: a history with undo and redo

The second classic pattern: two stacks, one for undo and one for redo.

flowchart LR
    A["New action"] --> D["UNDO stack"]
    D -->|undo| R["REDO stack"]
    R -->|redo| D
    A -.->|"a new action<br/>CLEARS the redo stack"| X["redo: empty"]

The mechanics:

  • A new action: it is pushed onto undo and the redo stack is cleared (it no longer makes sense to redo a future that has changed).
  • Undo: it is popped from undo, reverted and pushed onto redo.
  • Redo: it is popped from redo, reapplied and pushed onto undo.
package com.nexussoftware.bibliotech.service;

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

/** Browsing history with undo and redo, using two stacks. */
public class BrowsingHistory {

    private final Deque<String> back    = new ArrayDeque<>();
    private final Deque<String> forward = new ArrayDeque<>();
    private String current;

    public BrowsingHistory(String initialPage) {
        this.current = initialPage;
    }

    /** Navigating to a new page invalidates the whole "forward". */
    public void visit(String page) {
        if (page == null || page.equals(current)) { return; }
        back.push(current);
        current = page;
        forward.clear();       // there is no future left to redo
    }

    /** Undo: the current one moves to "forward" and the previous one is restored. */
    public String back() {
        if (back.isEmpty()) { return current; }     // nothing to undo
        forward.push(current);
        current = back.pop();
        return current;
    }

    /** Redo: the current one goes back to "back" and the next one is restored. */
    public String forward() {
        if (forward.isEmpty()) { return current; }
        back.push(current);
        current = forward.pop();
        return current;
    }

    public String  current()        { return current; }
    public boolean canGoBack()      { return !back.isEmpty(); }
    public boolean canGoForward()   { return !forward.isEmpty(); }

    /**
     * The visible history, from the most recent to the oldest.
     * ArrayDeque's iterator already traverses from the top to the bottom, which is
     * exactly the order we want. With Stack it would have to be reversed.
     */
    public List<String> backHistory() {
        return new ArrayList<>(back);
    }

    public String statusBar() {
        return String.format("%s %s %s  |  %s",
                canGoBack()    ? "<" : "-",
                current,
                canGoForward() ? ">" : "-",
                back.isEmpty() ? "(start)" : "back: " + back.peek());
    }
}

Usage:

BrowsingHistory h = new BrowsingHistory("catalogue");
h.visit("catalogue/books");
h.visit("catalogue/books/978-0000000001");
h.visit("loans/marta-ruiz");

System.out.println(h.statusBar());
System.out.println("Back -> " + h.back());
System.out.println("Back -> " + h.back());
System.out.println("Forward -> " + h.forward());
System.out.println("History: " + h.backHistory());

h.visit("reports/fines");                // a NEW page: the "forward" is lost
System.out.println("Can go forward: " + h.canGoForward());
< loans/marta-ruiz -  |  back: catalogue/books/978-0000000001
Back -> catalogue/books/978-0000000001
Back -> catalogue/books
Forward -> catalogue/books/978-0000000001
History: [catalogue/books, catalogue]
Can go forward: false

This is exactly the behaviour of the "back" and "forward" buttons of any browser, and of "undo/redo" in any editor. And notice the detail in backHistory(): ArrayDeque's iterator already returns the list in the right order —from the most recent to the oldest—, something that with Stack would have to be reversed by hand for the reason you saw in section 5.

  1. From recursion to iteration with an explicit stack

Every recursive function can be turned into an iterative one using a stack, because recursion is nothing more than the implicit use of the JVM's call stack. Making that stack explicit removes the risk of StackOverflowError, because the explicit stack lives on the heap.

A concrete example: walking a tree of catalogue categories and gathering every reference.

package com.nexussoftware.bibliotech.service;

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

/** A catalogue category that can contain subcategories. */
class Category {
    private final String name;
    private final List<Category> subcategories = new ArrayList<>();
    private final List<String>   references    = new ArrayList<>();

    Category(String name) { this.name = name; }

    Category addSub(Category c) { subcategories.add(c); return this; }
    Category addRef(String r)   { references.add(r);    return this; }

    String getName()                 { return name; }
    List<Category> getSubcategories(){ return subcategories; }
    List<String>   getReferences()   { return references; }
}

public final class CategoryTraversal {

    private CategoryTraversal() { }

    /**
     * The RECURSIVE version. Clear and short, but each level pushes a frame
     * onto the JVM's stack: with a very deep tree, StackOverflowError.
     */
    public static List<String> recursive(Category root) {
        List<String> result = new ArrayList<>();
        collect(root, result);
        return result;
    }

    private static void collect(Category c, List<String> accumulator) {
        if (c == null) { return; }
        accumulator.addAll(c.getReferences());
        for (Category sub : c.getSubcategories()) {
            collect(sub, accumulator);             // recursive call
        }
    }

    /**
     * The ITERATIVE version with an EXPLICIT stack. It does exactly the same,
     * but the stack lives on the heap: it copes with trees of any depth.
     */
    public static List<String> iterative(Category root) {
        List<String> result = new ArrayList<>();
        if (root == null) { return result; }

        Deque<Category> stack = new ArrayDeque<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            Category current = stack.pop();         // LIFO -> DEPTH-first traversal
            result.addAll(current.getReferences());

            // We push the subcategories IN REVERSE ORDER so that the first one
            // is processed first: the stack reverses the order, so reversing
            // it when pushing leaves it as in the recursive version.
            List<Category> subs = current.getSubcategories();
            for (int i = subs.size() - 1; i >= 0; i--) {
                stack.push(subs.get(i));
            }
        }
        return result;
    }

    public static void main(String[] args) {
        Category root = new Category("Technical");
        Category java = new Category("Java")
                .addRef("978-0000000001")
                .addRef("REV-2024-03");
        Category design = new Category("Design")
                .addRef("978-0000000002")
                .addSub(new Category("Refactoring")
                        .addRef("978-0000000003")
                        .addRef("DVD-0007"));
        root.addSub(java).addSub(design);

        System.out.println("Recursive: " + recursive(root));
        System.out.println("Iterative: " + iterative(root));
        System.out.println("Equal:     " + recursive(root).equals(iterative(root)));
    }
}
Recursive: [978-0000000001, REV-2024-03, 978-0000000002, 978-0000000003, DVD-0007]
Iterative: [978-0000000001, REV-2024-03, 978-0000000002, 978-0000000003, DVD-0007]
Equal:     true

Two important observations:

The reverse-order trick when pushing. Since the stack reverses, pushing the subcategories from left to right would process them from right to left. Pushing them backwards compensates for that reversal and reproduces exactly the order of the recursive version. It is a detail that is often forgotten and produces traversals that are correct but in an unexpected order.

When to do this conversion. The recursive version is more readable and should be the default option. Convert to iterative only when the depth could be large —data structures coming from outside, very deeply nested directory trees, graphs with thousands of levels— or when you need to control the traversal (pause it, resume it, limit it).

And compare with 05-07: if in iterative you swapped the stack for a queue (pollFirst instead of pop), you would have a breadth-first traversal. The same code shape, two algorithms.

  1. Applying it to BiblioTech

The catalogue's undo stack, which allows the last registration or removal to be cancelled.

First, we model the operation. We use a record (04-07) because it is immutable data, and an enum for the type:

package com.nexussoftware.bibliotech.domain;

/** A reversible operation on the catalogue. */
public record CatalogOperation(Type type, Material material, int day) {

    public enum Type {
        ADD("Material added"),
        REMOVE("Material removed");

        private final String description;
        Type(String description) { this.description = description; }
        public String getDescription() { return description; }

        /** The opposite operation: what has to be done to undo this one. */
        public Type inverse() {
            return (this == ADD) ? REMOVE : ADD;
        }
    }

    public CatalogOperation {
        if (type == null)     { type = Type.ADD; }
        if (day  < 0)         { day = 0; }
    }

    @Override
    public String toString() {
        return String.format("%s: '%s' (%s) on day %d",
                type.getDescription(), material.getTitle(), material.getReference(), day);
    }
}

And the catalogue with a reversible history:

package com.nexussoftware.bibliotech.service;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import com.nexussoftware.bibliotech.domain.Material;
import com.nexussoftware.bibliotech.domain.CatalogOperation;

/**
 * Catalogue with an undo and redo stack.
 *
 * Deque<CatalogOperation> on top of ArrayDeque: push/pop in O(1), an iterator
 * that traverses from the most recent to the oldest (what we want in order to
 * show the history) and without Stack's useless synchronisation.
 */
public class CatalogWithHistory {

    private static final int MAX_HISTORY = 50;

    private final Map<String, Material> byReference = new HashMap<>();
    private final Deque<CatalogOperation> undo = new ArrayDeque<>();
    private final Deque<CatalogOperation> redo = new ArrayDeque<>();

    /** Registration: records the operation on the undo stack. */
    public boolean register(Material m, int day) {
        if (m == null || byReference.containsKey(m.getReference())) { return false; }
        byReference.put(m.getReference(), m);
        recordOperation(new CatalogOperation(CatalogOperation.Type.ADD, m, day));
        return true;
    }

    /** Removal: likewise. */
    public boolean deregister(String reference, int day) {
        Material m = byReference.remove(reference);
        if (m == null) { return false; }
        recordOperation(new CatalogOperation(CatalogOperation.Type.REMOVE, m, day));
        return true;
    }

    private void recordOperation(CatalogOperation op) {
        undo.push(op);
        redo.clear();                      // a new operation invalidates the "redo"
        // We cap the history discarding at the BOTTOM: only a Deque allows this in O(1)
        if (undo.size() > MAX_HISTORY) {
            undo.pollLast();
        }
    }

    /** Cancels the last operation. Returns null if there was none. */
    public CatalogOperation undo() {
        CatalogOperation op = undo.poll();          // poll: null if it is empty
        if (op == null) { return null; }
        applyInverse(op);
        redo.push(op);
        return op;
    }

    /** Reapplies the last undone operation. */
    public CatalogOperation redo() {
        CatalogOperation op = redo.poll();
        if (op == null) { return null; }
        apply(op);
        undo.push(op);
        return op;
    }

    private void apply(CatalogOperation op) {
        switch (op.type()) {           // switch over an enum, with no default: exhaustive (04-07)
            case ADD    -> byReference.put(op.material().getReference(), op.material());
            case REMOVE -> byReference.remove(op.material().getReference());
        }
    }

    private void applyInverse(CatalogOperation op) {
        switch (op.type().inverse()) {
            case ADD    -> byReference.put(op.material().getReference(), op.material());
            case REMOVE -> byReference.remove(op.material().getReference());
        }
    }

    /** Undoes the last N operations. */
    public int undoSeveral(int howMany) {
        int done = 0;
        for (int i = 0; i < howMany && undo() != null; i++) { done++; }
        return done;
    }

    /** History from the most recent to the oldest: ArrayDeque's iterator order. */
    public List<CatalogOperation> history() {
        return new ArrayList<>(undo);
    }

    public CatalogOperation lastOperation() { return undo.peek(); }
    public boolean canUndo()                { return !undo.isEmpty(); }
    public boolean canRedo()                { return !redo.isEmpty(); }
    public int     size()                   { return byReference.size(); }
    public Material find(String reference)  { return byReference.get(reference); }
}

Usage:

CatalogWithHistory catalog = new CatalogWithHistory();

Material effectiveJava = new Book("Effective Java",  "Joshua Bloch",  "978-0000000001", 2018);
Material patterns      = new Book("Design Patterns", "Erich Gamma",   "978-0000000002", 1994);
Material refactoring   = new Book("Refactoring",     "Martin Fowler", "978-0000000003", 1999);
Material magazine      = new Magazine("Java Magazine", "REV-2024-03", 42, "Monthly");

catalog.register(effectiveJava, 100);
catalog.register(patterns,      101);
catalog.register(refactoring,   102);
catalog.register(magazine,      103);
catalog.deregister("978-0000000002", 105);      // removal of Design Patterns

System.out.println("Materials: " + catalog.size());
System.out.println("Last operation: " + catalog.lastOperation());

System.out.println("\n--- Undoing ---");
System.out.println("Undone: " + catalog.undo());
System.out.println("Materials: " + catalog.size()
                   + "  (Design Patterns is back: " + (catalog.find("978-0000000002") != null) + ")");

System.out.println("\n--- Redoing ---");
System.out.println("Redone: " + catalog.redo());
System.out.println("Materials: " + catalog.size());

System.out.println("\n--- Undoing three operations ---");
System.out.println("Operations undone: " + catalog.undoSeveral(3));
System.out.println("Materials: " + catalog.size());

System.out.println("\n--- Pending history (most recent first) ---");
catalog.history().forEach(op -> System.out.println("  " + op));
Materials: 3
Last operation: Material removed: 'Design Patterns' (978-0000000002) on day 105

--- Undoing ---
Undone: Material removed: 'Design Patterns' (978-0000000002) on day 105
Materials: 4  (Design Patterns is back: true)

--- Redoing ---
Redone: Material removed: 'Design Patterns' (978-0000000002) on day 105
Materials: 3

--- Undoing three operations ---
Operations undone: 3
Materials: 2

--- Pending history (most recent first) ---
  Material added: 'Design Patterns' (978-0000000002) on day 101
  Material added: 'Effective Java' (978-0000000001) on day 100

Three design decisions worth pointing out. recordOperation caps the history discarding at the bottom with pollLast(): that is O(1) only because a Deque opens both ends —with a pure stack you would have to empty it and rebuild it—. The switch over the enum has no default, so if tomorrow you add an operation type the compiler will take you to the two places that need updating (04-07). And history() takes advantage of ArrayDeque's iterator traversing from the top to the bottom, handing back the list in the order the user expects.

Common Mistakes and Tips

Using java.util.Stack in new code. It extends Vector, it is needlessly synchronised, it exposes a list API on a stack and its iterator traverses from the bottom to the top, the opposite of how the elements come out. Use Deque<X> stack = new ArrayDeque<>().

Traversing a Stack with a for-each expecting the exit order. It gives the reverse order. With ArrayDeque the iterator does go from the top to the bottom.

pop() on an empty stack. It throws NoSuchElementException on ArrayDeque and EmptyStackException on Stack. Check isEmpty() first, or use pollFirst(), which returns null.

Confusing the asymmetry of push/pop/peek in Deque. pop() throws an exception, but peek() returns null. If you want consistency, use the complete families: pollFirst/peekFirst (they return null) or removeFirst/getFirst (they throw).

Inserting null into an ArrayDeque. NullPointerException, just as with queues: null is reserved as the "empty" signal.

Forgetting to null out the freed cell when implementing your own stack. The array keeps referring to the popped object and prevents it being collected: a memory leak.

Forgetting to clear the redo stack when recording a new action. Redoing a future that no longer exists produces inconsistent states. It is the most frequent mistake when implementing undo/redo.

Forgetting to reverse the order when pushing children in a depth-first traversal. The stack reverses, so pushing in natural order processes them backwards. Push them in reverse order if you want to reproduce the recursive version's order.

Confusing the call stack with a data stack. The first is per-thread reserved memory, of fixed size, and exhausting it produces StackOverflowError. The second is a heap object and grows for as long as there is memory. That is why converting a deep recursion into iteration with ArrayDeque solves the problem.

Tip: if the problem mentions "the last one", "undo", "nested" or "go back", it is a stack. Just as "in order of arrival" meant a queue and "no repeats" meant a Set, the wording usually tells you the structure.

Tip: Deque is the most profitable interface in the Framework. With a single implementation —ArrayDeque— you get a FIFO queue, a LIFO stack and a double-ended queue, all in O(1) and with the best cache locality.

Exercises

Exercise 1: an undo stack for loans

Extend BiblioTech with ReversibleLoanManager to maintain a stack of the last loan and return operations, allowing them to be cancelled:

  • Create a record LoanOperation(Type type, Loan loan, int day) with enum Type { LOAN, RETURN }.
  • void lend(Loan l, int day) and void returnItem(Loan l, int day), which record the operation.
  • LoanOperation undo(): reverts the last one (an undone loan returns the material; an undone return marks it as on loan again).
  • List<LoanOperation> latest(int howMany): without emptying the stack.
  • int undoAfter(int day): undoes every operation later than that day.
  • Cap the history at 20 operations, discarding the oldest.

Exercise 2: Stack versus ArrayDeque

Write StackComparison with a main that demonstrates, printing and explaining each point:

  1. That Stack and ArrayDeque give the same result with push/pop/peek.
  2. That their iterators and their toString traverse in opposite orders, and why.
  3. That Stack allows list operations that break the stack semantics (get(0), add(1, x), remove(0)), and that ArrayDeque does not offer them.
  4. That Stack.search returns a 1-based position.
  5. An illustrative measurement of a million push/pop operations on both, with the warning about JMH.

Exercise 3: a reverse Polish notation evaluator

Reverse Polish notation (RPN) places the operator after its operands: 3 4 + is 3 + 4, and 5 1 2 + 4 * + 3 - is 5 + ((1+2)*4) - 3 = 14. Its great virtue is that it needs no brackets and is evaluated with a single stack.

Write RpnEvaluator with:

  • double evaluate(String expression): walks the symbols separated by spaces; if it is a number it pushes it, and if it is an operator (+, -, *, /) it pops two operands, operates and pushes the result. At the end exactly one value must be left.
  • Handling of invalid cases without custom exceptions (module 6): return Double.NaN and print a warning.
  • String trace(String expression): shows the state of the stack after each symbol.

Apply it to a BiblioTech fine: "15 0.25 * 20 min" is not standard RPN, so use "20 15 - 0.25 *" to compute the fine for a book returned on day 20 with a 15-day term.

Solutions

Solution 1

package com.nexussoftware.bibliotech.service;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
import com.nexussoftware.bibliotech.domain.Loan;

/** A reversible operation on a loan. */
record LoanOperation(Type type, Loan loan, int day) {

    enum Type { LOAN, RETURN }

    @Override
    public String toString() {
        return String.format("%-11s %s (%s) day %d", type, loan.getReference(),
                loan.getMaterial().getTitle(), day);
    }
}

public class ReversibleLoanManager {

    private static final int MAX_HISTORY = 20;

    private final Deque<LoanOperation> history = new ArrayDeque<>();

    private void recordOperation(LoanOperation op) {
        history.push(op);
        // Capping at the BOTTOM in O(1): only possible with a Deque, not with a pure stack
        if (history.size() > MAX_HISTORY) {
            history.pollLast();
        }
    }

    public void lend(Loan l, int day) {
        if (l == null) { return; }
        l.getMaterial().lend();
        recordOperation(new LoanOperation(LoanOperation.Type.LOAN, l, day));
    }

    public void returnItem(Loan l, int day) {
        if (l == null) { return; }
        l.registerReturn(day);
        recordOperation(new LoanOperation(LoanOperation.Type.RETURN, l, day));
    }

    /** Reverts the last operation. poll returns null if there is none. */
    public LoanOperation undo() {
        LoanOperation op = history.poll();
        if (op == null) { return null; }

        // An exhaustive switch over the enum, with no default (04-07): if tomorrow we add
        // an operation type, the compiler will bring us here.
        switch (op.type()) {
            case LOAN   -> op.loan().getMaterial().returnItem();  // undo lending
            case RETURN -> op.loan().getMaterial().lend();        // undo returning
        }
        return op;
    }

    /**
     * The last N WITHOUT emptying the stack.
     * ArrayDeque's iterator goes from the top to the bottom: exactly the order we want.
     */
    public List<LoanOperation> latest(int howMany) {
        List<LoanOperation> result = new ArrayList<>();
        int n = 0;
        for (LoanOperation op : history) {
            if (n++ >= howMany) { break; }
            result.add(op);
        }
        return result;
    }

    /**
     * Undoes everything later than 'day'. peek() inspects without taking out, so we can
     * decide whether it is worth undoing before committing.
     */
    public int undoAfter(int day) {
        int undone = 0;
        while (!history.isEmpty() && history.peek().day() > day) {
            undo();
            undone++;
        }
        return undone;
    }

    public LoanOperation last()          { return history.peek(); }
    public boolean canUndo()             { return !history.isEmpty(); }
    public int     operationsOnStack()   { return history.size(); }
}

A test:

Employee marta = new Employee("Marta Ruiz", "EMP-001");
Material effectiveJava = new Book("Effective Java", "Joshua Bloch", "978-0000000001", 2018);
Material patterns      = new Book("Design Patterns", "Erich Gamma", "978-0000000002", 1994);

ReversibleLoanManager g = new ReversibleLoanManager();
Loan l1 = new Loan(effectiveJava, marta, 100);
Loan l2 = new Loan(patterns,      marta, 105);

g.lend(l1, 100);
g.lend(l2, 105);
g.returnItem(l1, 118);

System.out.println("Last: " + g.last());
System.out.println("Effective Java available: " + effectiveJava.isAvailable());  // true

System.out.println("Undone: " + g.undo());
System.out.println("Effective Java available: " + effectiveJava.isAvailable());  // false

System.out.println("Undone up to day 100: " + g.undoAfter(100));
System.out.println("Operations on the stack: " + g.operationsOnStack());

The key point is peek() in undoAfter: it lets you inspect the top without taking it out, decide whether it should be undone and only then commit. Without peek, you would have to take the element out to look at it and push it back if it did not apply, which would also leave the stack in an incorrect transient state. It is the exact reason why a stack's three operations are push, pop and peek.

Solution 2

package com.nexussoftware.bibliotech.presentation;

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

public class StackComparison {

    public static void main(String[] args) {
        sameResult();
        oppositeOrders();
        stackBreaksSemantics();
        searchIsOneBased();
        performance();
    }

    static void sameResult() {
        System.out.println("=== 1. push/pop/peek give the same thing ===");
        Stack<String> stack = new Stack<>();
        Deque<String> deque = new ArrayDeque<>();
        for (String s : new String[]{ "registration", "withdrawal", "amendment" }) {
            stack.push(s);
            deque.push(s);
        }
        System.out.println("Stack peek: " + stack.peek() + " | Deque peek: " + deque.peek());
        System.out.println("Stack pop:  " + stack.pop()  + " | Deque pop:  " + deque.pop());
        System.out.println("Both return the TOP: correct LIFO in both.\n");
    }

    static void oppositeOrders() {
        System.out.println("=== 2. Iterators in OPPOSITE orders ===");
        Stack<String> stack = new Stack<>();
        Deque<String> deque = new ArrayDeque<>();
        for (String s : new String[]{ "first", "second", "third" }) {
            stack.push(s);
            deque.push(s);
        }

        System.out.println("Stack toString: " + stack);   // [first, second, third]
        System.out.println("Deque toString: " + deque);   // [third, second, first]

        System.out.print("Stack for-each: ");
        for (String s : stack) { System.out.print(s + " "); }
        System.out.print("  <- from the BOTTOM to the top: the reverse of how they will come out");

        System.out.print("\nDeque for-each: ");
        for (String s : deque) { System.out.print(s + " "); }
        System.out.print("  <- from the TOP to the bottom: the exit order");

        System.out.println("\n\nCause: Stack inherits Vector's iterator, which walks the");
        System.out.println("array from index 0 onwards, and in Stack index 0 is the BOTTOM.");
        System.out.println("Consequence: a loop that 'processes the stack in order' does the opposite.\n");
    }

    static void stackBreaksSemantics() {
        System.out.println("=== 3. Stack exposes a list API ===");
        Stack<String> stack = new Stack<>();
        stack.push("A"); stack.push("B"); stack.push("C");

        System.out.println("Initial stack:   " + stack);
        System.out.println("stack.get(0):    " + stack.get(0) + "   <- access to the BOTTOM");
        stack.add(1, "X");
        System.out.println("stack.add(1,X):  " + stack + "   <- insertion in the MIDDLE");
        stack.remove(0);
        System.out.println("stack.remove(0): " + stack + "   <- deletion from the BOTTOM");
        stack.set(0, "Z");
        System.out.println("stack.set(0,Z):  " + stack + "   <- modification of the BOTTOM");

        System.out.println("None of these operations exists on Deque: the interface");
        System.out.println("only offers the ends, and that restriction IS the guarantee.");
        System.out.println("Cause: 'class Stack extends Vector' is bad inheritance (03-05):");
        System.out.println("a stack USES storage, it IS NOT a vector.\n");
    }

    static void searchIsOneBased() {
        System.out.println("=== 4. Stack.search is 1-based ===");
        Stack<String> stack = new Stack<>();
        stack.push("bottom"); stack.push("middle"); stack.push("top");

        System.out.println("search('top'):    " + stack.search("top")
                           + "   <- 1, not 0: it breaks the convention of all of Java");
        System.out.println("search('bottom'): " + stack.search("bottom"));
        System.out.println("search('none'):   " + stack.search("none") + "   <- -1 if absent");
        System.out.println("Deque has no search: use contains (O(n)) if you need it.\n");
    }

    static void performance() {
        System.out.println("=== 5. Illustrative performance ===");
        System.out.println("WARNING: this is not a rigorous benchmark. The JIT, the collector");
        System.out.println("and dead-code elimination distort these figures.");
        System.out.println("To measure seriously, JMH (05-04).\n");

        final int N = 1_000_000;

        for (int i = 0; i < 3; i++) { cycle(new Stack<>(), 10_000); }   // warm-up
        for (int i = 0; i < 3; i++) { cycle(new ArrayDeque<>(), 10_000); }

        long tStack = cycle(new Stack<>(), N);
        long tDeque = cycle(new ArrayDeque<>(), N);

        System.out.printf("Stack       %d push+pop: %5d ms%n", N, tStack);
        System.out.printf("ArrayDeque  %d push+pop: %5d ms%n", N, tDeque);
        System.out.println("The difference comes above all from Vector's synchronisation,");
        System.out.println("which acquires and releases a lock on EVERY operation, serving");
        System.out.println("no purpose at all in a single-threaded program.");
    }

    static long cycle(Deque<Integer> stack, int n) {
        long t = System.nanoTime();
        for (int i = 0; i < n; i++) { stack.push(i); }
        while (!stack.isEmpty()) { stack.pop(); }
        return (System.nanoTime() - t) / 1_000_000;
    }

    static long cycle(Stack<Integer> stack, int n) {
        long t = System.nanoTime();
        for (int i = 0; i < n; i++) { stack.push(i); }
        while (!stack.isEmpty()) { stack.pop(); }
        return (System.nanoTime() - t) / 1_000_000;
    }
}

Part 2 is the most important in the exercise. Stack and ArrayDeque do the same thing with pop, but traverse in reverse, and that inconsistency produces no visible error: it simply gives the wrong results. It is the most compelling argument against Stack, even more than the synchronisation.

Part 3 shows the underlying design problem: extends Vector hands Stack forty methods that contradict its own semantics. It is the canonical example of why 03-05 insisted on asking "is it a?" before inheriting. The right answer was composition.

Solution 3

package com.nexussoftware.bibliotech.service;

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

/**
 * An evaluator for expressions in reverse Polish notation (RPN).
 *
 * In RPN the operator comes AFTER its operands, which removes the
 * brackets and allows evaluation with a single stack:
 *   "3 4 +"             = 3 + 4          = 7
 *   "5 1 2 + 4 * + 3 -" = 5 + (1+2)*4 -3 = 14
 */
public final class RpnEvaluator {

    private RpnEvaluator() { }

    private static final Set<String> OPERATORS = Set.of("+", "-", "*", "/");

    public static double evaluate(String expression) {
        if (expression == null || expression.isBlank()) {
            System.out.println("WARNING: empty expression");
            return Double.NaN;
        }

        Deque<Double> stack = new ArrayDeque<>();

        for (String symbol : expression.trim().split("\\s+")) {
            if (OPERATORS.contains(symbol)) {
                if (stack.size() < 2) {
                    System.out.println("WARNING: missing operands for '" + symbol + "'");
                    return Double.NaN;
                }
                // ORDER MATTERS: the first one out is the RIGHT operand,
                // because it was the last one pushed. Reversing it breaks '-' and '/'.
                double right = stack.pop();
                double left  = stack.pop();
                Double result = operate(left, right, symbol);
                if (result == null) { return Double.NaN; }
                stack.push(result);
            } else {
                Double number = toNumber(symbol);
                if (number == null) {
                    System.out.println("WARNING: unrecognised symbol -> '" + symbol + "'");
                    return Double.NaN;
                }
                stack.push(number);
            }
        }

        if (stack.size() != 1) {
            System.out.println("WARNING: malformed expression, "
                               + stack.size() + " values left on the stack");
            return Double.NaN;
        }
        return stack.pop();
    }

    private static Double operate(double a, double b, String op) {
        switch (op) {
            case "+": return a + b;
            case "-": return a - b;
            case "*": return a * b;
            case "/":
                if (b == 0) {
                    // Module 6 will teach how to signal this with a custom exception
                    System.out.println("WARNING: division by zero");
                    return null;
                }
                return a / b;
            default:  return null;
        }
    }

    /** Conversion with no try/catch: we check the format first (module 6 will do it better). */
    private static Double toNumber(String s) {
        if (!s.matches("-?\\d+(\\.\\d+)?")) { return null; }
        return Double.valueOf(s);
    }

    /** Shows the state of the stack after each symbol. */
    public static String trace(String expression) {
        StringBuilder sb = new StringBuilder();
        Deque<Double> stack = new ArrayDeque<>();

        sb.append(String.format("%-8s %s%n", "SYMBOL", "STACK (top first)"));
        for (String symbol : expression.trim().split("\\s+")) {
            if (OPERATORS.contains(symbol) && stack.size() >= 2) {
                double right = stack.pop();
                double left  = stack.pop();
                Double r = operate(left, right, symbol);
                stack.push(r == null ? Double.NaN : r);
            } else {
                Double n = toNumber(symbol);
                if (n != null) { stack.push(n); }
            }
            // ArrayDeque's iterator goes from the top to the bottom: the useful order
            sb.append(String.format("%-8s %s%n", symbol, stack));
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        System.out.println("3 4 +               = " + evaluate("3 4 +"));
        System.out.println("5 1 2 + 4 * + 3 -   = " + evaluate("5 1 2 + 4 * + 3 -"));

        // A BiblioTech fine: a book returned on day 20 with a 15-day term,
        // rate 0.25 EUR/day. In RPN: (20 - 15) * 0.25
        System.out.println("20 15 - 0.25 *      = " + evaluate("20 15 - 0.25 *")
                           + " EUR of fine");

        System.out.println("\n--- Invalid cases ---");
        System.out.println("Result: " + evaluate("3 +"));
        System.out.println("Result: " + evaluate("3 4 5 +"));
        System.out.println("Result: " + evaluate("3 0 /"));
        System.out.println("Result: " + evaluate("3 4 %"));

        System.out.println("\n--- Trace of '5 1 2 + 4 * + 3 -' ---");
        System.out.print(trace("5 1 2 + 4 * + 3 -"));
    }
}
3 4 +               = 7.0
5 1 2 + 4 * + 3 -   = 14.0
20 15 - 0.25 *      = 1.25 EUR of fine

--- Invalid cases ---
WARNING: missing operands for '+'
Result: NaN
WARNING: malformed expression, 2 values left on the stack
Result: NaN
WARNING: division by zero
Result: NaN
WARNING: unrecognised symbol -> '%'
Result: NaN

--- Trace of '5 1 2 + 4 * + 3 -' ---
SYMBOL   STACK (top first)
5        [5.0]
1        [1.0, 5.0]
2        [2.0, 1.0, 5.0]
+        [3.0, 5.0]
4        [4.0, 3.0, 5.0]
*        [12.0, 5.0]
+        [17.0]
3        [3.0, 17.0]
-        [14.0]

The trace shows the essence of the structure: the stack holds the partial results still to be combined, and each operator consumes exactly the last two. Being LIFO is what guarantees that the right operands are combined: when the + at position 4 arrives, the two values on the top (2.0 and 1.0) are precisely the ones it belongs to, and the 5.0 at the bottom waits patiently for its turn.

Two details that usually cause trouble. The order of the operands: the first one out of the stack is the right operand, because it was the last one pushed; reversing it would give correct results for + and * but wrong ones for - and /, which is the kind of bug that takes hours to show up. And the final check that exactly one value is left: if there are extras, the expression was malformed even though every individual operation worked.

This is also, in essence, how the JVM itself works: its bytecode is a stack machine, where iadd pops two integers and pushes their sum. Evaluating 20 15 - 0.25 * with an ArrayDeque is, conceptually, the same as what the virtual machine does when running calculateFine.

Conclusion

You now master the module's third access policy. You know that a stack is LIFO: elements come in and go out at the top with push, pop and peek, and that its essential property —reversing the order— is what makes it ideal for undoing, for parsing nested structures, for depth-first traversal and for the execution of programs themselves.

You understand the JVM's call stack: every invocation pushes a frame with parameters, local variables and a return address, and every return pops it. With that you have closed the circle opened in 03-03: StackOverflowError is the exhaustion of that stack, it has a fixed size per thread and it is an Error, not an exception you should handle; its causes are a recursion with no base case —a bug— or a correct but too deep recursion —which is solved with an explicit stack on the heap—.

You know the Stack class and, above all, why you must not use it: it extends Vector, which is textbook bad inheritance (a stack uses storage, it is not a vector) and hands it the whole API of a list, allowing get(0), add(1, x) and remove(0) on a supposed stack; it is synchronised at a cost that does not buy real safety; and —the most treacherous defect— its iterator traverses from the bottom to the top, exactly the reverse of the order in which the elements will come out, producing wrong results with no warning at all. Its 1-based search completes the picture.

The right answer is Deque<X> stack = new ArrayDeque<>(): push, pop and peek as aliases for operations on the head, O(1) with no locks, the best cache locality, and an iterator that traverses in the exit order. You are clear about the asymmetry of pop() (it throws) versus peek() (it returns null) and the complete families of 05-07 for choosing whichever behaviour you want.

You have implemented your own stack with an array and an index, understanding from the inside why top points at the next free position, why the cell has to be set to null on popping —a memory leak— and why multiplicative growth gives amortised O(1) cost. And you have solved the two canonical problems: balanced brackets, where the stack detects the bad nesting a simple counter would let through, and undo/redo with two stacks, including the detail almost everybody forgets —a new action must clear the redo stack—. And you know how to turn a recursion into iteration with an explicit stack, with the trick of pushing the children in reverse order to preserve the traversal order.

BiblioTech now has a CatalogWithHistory with a Deque<CatalogOperation> that allows the last registration or removal to be cancelled, redone, several undone at once and the history consulted in the right order, with the history capped by discarding at the bottom in O(1) —something only a Deque allows—.

In the next lesson, Sorting and Searching Collections, you close the module by gathering up all the threads. You will come back to Comparable and its complete contract —the sign of the result, antisymmetry, transitivity, consistency with equals and what exactly breaks in a TreeSet when it is not—, including the classic mistake of subtracting integers and overflowing. You will pick up Comparator from 04-06 with comparing, thenComparing, reversed, nullsFirst, comparingInt and why the last one avoids autoboxing. You will see the four sorting strategies —Collections.sort, List.sort, Arrays.sort and the collections that stay sorted by themselves—, what it means for a sort to be stable and why it matters when sorting by successive criteria, and which algorithms Java really uses: TimSort for objects and dual-pivot quicksort for primitives. Then, searching: linear versus binary versus a map key, with the interpretation of the negative value binarySearch returns, and the Collections utilities still to be met. And at the end, the module's balance sheet: what BiblioTech is capable of now, what is still fragile and why module 6 is the inevitable next step.

◄ Previous
◄
Next ►
►

Java Programming Course

Module 1: Introduction to Java

Module 2: Control Flow

Module 3: Object-Oriented Programming

Module 4: Advanced Object-Oriented Programming

Module 5: Data Structures and Collections

Module 6: Exception Handling

Module 7: File Input/Output

Module 8: Multithreading and Concurrency

Module 9: Networking

Module 10: Advanced Topics

Module 11: Java Frameworks and Libraries

Module 12: Building Real-World Applications

The Project | About Us | Contribute | Donations | License
© Copyright 2026. All rights reserved