Stack Class

A stack is a collection in which the last element added is the first one removed: last-in, first-out (LIFO), like a stack of plates. Stacks model anything that must be undone or completed in reverse order: undo history, nested brackets, function calls, and backtracking through a maze. Java has a legacy java.util.Stack class, and a modern replacement, the Deque interface with ArrayDeque. This lesson explains both, and why new code should use the second.

The Stack Concept

        push("C")        pop() → "C"
            │               ▲
            ▼               │
         ┌─────┐  ◄── top
         │  C  │
         ├─────┤
         │  B  │
         ├─────┤
         │  A  │  ◄── bottom
         └─────┘

All operations happen at the top:

The java.util.Stack Class

import java.util.Stack;

Stack<String> history = new Stack<>();
history.push("home");
history.push("courses");
history.push("java");

System.out.println(history.peek());    // java
System.out.println(history.pop());     // java
System.out.println(history.pop());     // courses
System.out.println(history.empty());   // false: "home" remains

Stack methods

Stack<String> st = new Stack<>();
st.push("a");
st.push("b");
st.push("c");

System.out.println(st);              // [a, b, c]   bottom → top
System.out.println(st.search("a"));  // 3: third from the top
new Stack<String>().pop();           // EmptyStackException

EmptyStackException is unchecked. Check empty() before popping when an empty stack is possible.

Why Stack Is a Legacy Class

Stack dates from Java 1.0. It extends Vector, an early growable array, and that design causes problems:

1. It is not a pure stack. Because it inherits every Vector and List method, code can read or change elements anywhere, breaking the LIFO discipline:

Stack<String> st = new Stack<>();
st.push("a");
st.push("b");
st.add(0, "sneaky");          // inserts at the bottom
st.remove(1);                 // removes from the middle
System.out.println(st.get(0));   // reads the bottom directly

A data structure that is supposed to guarantee "only the top is accessible" cannot enforce it.

2. Every method is synchronized. Vector locks the object on every call to make it thread-safe. In single-threaded code, which is the vast majority of stack usage, this adds overhead for no benefit, and for real concurrent code, per-method locking is usually not the right kind of safety anyway.

3. Iteration order is bottom to top. A for-each loop over a Stack starts at the bottom, which is the opposite of the order in which elements would be popped:

for (String s : st) System.out.print(s);   // "abc" for pushes a, b, c

The Java documentation itself states that the Deque interface provides a more complete and consistent set of LIFO stack operations, which should be used in preference to Stack.

The Modern Stack: Deque and ArrayDeque

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

Deque<String> stack = new ArrayDeque<>();
stack.push("a");
stack.push("b");
stack.push("c");

System.out.println(stack);          // [c, b, a]   top first
System.out.println(stack.peek());   // c
System.out.println(stack.pop());    // c

Deque's push, pop, and peek operate on the head of the deque, which serves as the top of the stack.

Note the difference in peek(): ArrayDeque.peek() returns null on an empty stack rather than throwing, which allows while (stack.peek() != null) loops. pollFirst() similarly removes the top or returns null.

For stacks shared between threads, use a concurrent structure such as ConcurrentLinkedDeque, or ArrayDeque guarded by explicit locking.

How a Stack Grows

Both Stack and ArrayDeque keep elements in an internal array that is enlarged when full. push, pop, and peek are therefore O(1) (amortized for push). Because only the top is touched, a stack never needs to shift elements.

Where Stacks Appear

The call stack

The JVM itself uses a stack to run methods. Each method call pushes a frame holding its parameters and local variables; returning pops it. That is why deeply recursive code fails with StackOverflowError, and why a stack trace lists the most recent call first.

Reversing

Pushing items and popping them returns them in reverse order:

Deque<Character> chars = new ArrayDeque<>();
for (char c : "stack".toCharArray()) chars.push(c);
StringBuilder reversed = new StringBuilder();
while (!chars.isEmpty()) reversed.append(chars.pop());
System.out.println(reversed);   // kcats

Undo

Each action is pushed; undo pops the most recent one. A second stack holds undone actions for redo.

Evaluating expressions

Calculators and compilers use stacks to evaluate expressions. In postfix notation (3 4 + 2 *), each number is pushed, and each operator pops two operands and pushes the result:

static int evalPostfix(String expr) {
    Deque<Integer> st = new ArrayDeque<>();
    for (String tok : expr.split(" ")) {
        switch (tok) {
            case "+" -> st.push(st.pop() + st.pop());
            case "*" -> st.push(st.pop() * st.pop());
            case "-" -> { int b = st.pop(), a = st.pop(); st.push(a - b); }
            case "/" -> { int b = st.pop(), a = st.pop(); st.push(a / b); }
            default -> st.push(Integer.parseInt(tok));
        }
    }
    return st.pop();
}

System.out.println(evalPostfix("3 4 + 2 *"));   // 14

For - and /, the order of operands matters, so the second value popped is the left operand.

Depth-first search and backtracking

Exploring a maze, a file tree, or a graph depth-first uses a stack (explicitly, or implicitly through recursion) to remember where to return after reaching a dead end.

Practical Example: Bracket Checker

Code editors highlight unbalanced brackets. Every opening bracket is pushed; every closing bracket must match the most recently opened one, which is exactly what the top of a stack holds.

import java.util.*;

public class Brackets {
    static String check(String code) {
        Deque<Character> open = new ArrayDeque<>();
        Deque<Integer> positions = new ArrayDeque<>();
        Map<Character, Character> pairs = Map.of(')', '(', ']', '[', '}', '{');

        for (int i = 0; i < code.length(); i++) {
            char c = code.charAt(i);
            if (c == '(' || c == '[' || c == '{') {
                open.push(c);
                positions.push(i);
            } else if (pairs.containsKey(c)) {
                if (open.isEmpty()) {
                    return "Unexpected '" + c + "' at position " + i;
                }
                char top = open.pop();
                int at = positions.pop();
                if (top != pairs.get(c)) {
                    return "'" + top + "' at position " + at + " closed by '" + c + "' at position " + i;
                }
            }
        }
        return open.isEmpty() ? "Balanced" : "Unclosed '" + open.peek() + "' at position " + positions.peek();
    }

    public static void main(String[] args) {
        String[] samples = {
            "if (a[i] > max) { max = a[i]; }",
            "list.get(0]",
            "for (int x : xs) { print(x); ",
            "total = sum(a)) * 2"
        };
        for (String s : samples) {
            System.out.printf("%-32s -> %s%n", s, check(s));
        }
    }
}

Output:

if (a[i] > max) { max = a[i]; }  -> Balanced
list.get(0]                      -> '(' at position 8 closed by ']' at position 10
for (int x : xs) { print(x);     -> Unclosed '{' at position 17
total = sum(a)) * 2              -> Unexpected ')' at position 14

The algorithm detects all three kinds of error:

• Mismatch. A closing bracket that does not pair with the top of the stack, such as ( closed by ].
• Unexpected close. A closing bracket arrives while the stack is empty.
• Unclosed. Brackets remain on the stack after the whole input has been read.

A second stack records each opening bracket's position, so error messages can point to it. Because the top of the stack is always the innermost unclosed bracket, nesting of any depth is handled correctly. Both stacks are ArrayDeques, following the modern recommendation; the logic would be identical with java.util.Stack.