Stack — The Data Structures Atlas

Category: Linear

The problem

Some problems are naturally "undo the most recent thing first": matching a closing bracket to whichever opening bracket is still unmatched, backtracking out of the last decision made, unwinding nested function calls. None of that is indexed access or ordered traversal — it's strictly last-in-first-out.

The solution

Restrict access to one end only: you can only look at, add to, or remove from the top. That single restriction is what makes every operation trivial and O(1) — there's never a question of which element to touch, it's always the one on top. This module reuses the same doubling-array growth strategy as Dynamic Array: push is amortized O(1).

flowchart TB
    subgraph Stack
        direction TB
        C["C  ← top"]
        B["B"]
        A["A  ← bottom"]
    end

Operation	Cost	Why
`push`	O(1) amortized	same doubling-array trick as Dynamic Array
`pop` / `peek`	O(1)	always the last index, nothing to search

Classic example

classic/Stack is array-backed (no java.util.Stack/ArrayDeque), exposing only push, pop, peek, size, isEmpty — pop/peek on an empty stack throw EmptyStackException, matching the JDK's own convention for this exact failure mode. StackTest covers LIFO ordering, both empty-stack failure cases, and growth past the initial capacity.

Applied example: legacy COBOL copybook bracket validation

applied/CopybookBracketValidator is the textbook "balanced brackets" stack exercise pointed at a real problem: tooling built during a legacy bank's mainframe-to-microservices modernization needs to validate that parentheses in PICTURE clauses and COMPUTE expressions are balanced before an automated parser attempts to translate the line — a malformed copybook line should fail loudly here, not produce a silently wrong translation downstream. Every opening bracket is pushed; every closing bracket must match whatever's on top, and the stack must be empty again at end of line. CopybookBracketValidatorTest covers balanced lines, an unexpected closing bracket, a mismatched bracket type, and an unclosed bracket at end of line.

Benchmark

./gradlew :linear:stack:jmh

Real run (JMH 1.37, JDK 26.0.2, 2 warmup + 3 measurement iterations, 1 fork):

Benchmark	size=100	size=10,000	size=1,000,000
`push` (total for N pushes)	619 ns	71,850 ns	35.5 ms
`peek`	2.39 ns	1.79 ns	2.36 ns

peek stays flat regardless of size — O(1), confirmed. push's total cost scales with size the same amortized-O(1)-per-element way Dynamic Array's append does, since it's the same growth strategy underneath.

When not to use it

Need to look at or remove anything other than the most-recently-added element? A stack can't do that at all by design — see Queue / Deque for FIFO/both-ends access, or Linked List for splicing anywhere.
Recursive algorithms are implicitly using the call stack as a stack already; an explicit stack is mainly useful when you need to convert recursion to iteration (deep nesting that would otherwise blow the call stack) or when the LIFO order itself is the point, like here.

Test coverage

100% instruction coverage, 100% branch coverage (JaCoCo). Reproduce it yourself:

./gradlew :linear:stack:jacocoTestReport

Report at linear/stack/build/reports/jacoco/test/html/index.html.

Unit tests

src/test/java/com/datastructures/linear/stack/classic/StackTest.java

package com.datastructures.linear.stack.classic;

import org.junit.jupiter.api.Test;

import java.util.EmptyStackException;

import static org.assertj.core.api.Assertions.assertThat;
import static org.assertj.core.api.Assertions.assertThatThrownBy;

class StackTest {

    @Test
    void startsEmpty() {
        Stack<String> stack = new Stack<>();

        assertThat(stack.isEmpty()).isTrue();
        assertThat(stack.size()).isZero();
    }

    @Test
    void pushMakesTheStackNonEmptyAndPeekableWithoutRemoving() {
        Stack<String> stack = new Stack<>();

        stack.push("a");

        assertThat(stack.isEmpty()).isFalse();
        assertThat(stack.peek()).isEqualTo("a");
        assertThat(stack.size()).isEqualTo(1);
    }

    @Test
    void popReturnsElementsInLastInFirstOutOrder() {
        Stack<String> stack = new Stack<>();
        stack.push("a");
        stack.push("b");
        stack.push("c");

        assertThat(stack.pop()).isEqualTo("c");
        assertThat(stack.pop()).isEqualTo("b");
        assertThat(stack.pop()).isEqualTo("a");
        assertThat(stack.isEmpty()).isTrue();
    }

    @Test
    void popOnAnEmptyStackThrows() {
        Stack<String> stack = new Stack<>();

        assertThatThrownBy(stack::pop).isInstanceOf(EmptyStackException.class);
    }

    @Test
    void peekOnAnEmptyStackThrows() {
        Stack<String> stack = new Stack<>();

        assertThatThrownBy(stack::peek).isInstanceOf(EmptyStackException.class);
    }

    @Test
    void growsPastInitialCapacityWithoutLosingOrder() {
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < 100; i++) {
            stack.push(i);
        }

        assertThat(stack.size()).isEqualTo(100);
        for (int i = 99; i >= 0; i--) {
            assertThat(stack.pop()).isEqualTo(i);
        }
    }
}

src/test/java/com/datastructures/linear/stack/applied/CopybookBracketValidatorTest.java

package com.datastructures.linear.stack.applied;

import org.junit.jupiter.api.Test;

import static org.assertj.core.api.Assertions.assertThat;

class CopybookBracketValidatorTest {

    private final CopybookBracketValidator validator = new CopybookBracketValidator();

    @Test
    void anEmptyLineIsTriviallyBalanced() {
        assertThat(validator.validate("")).isEqualTo(BracketValidationResult.ok());
    }

    @Test
    void aLineWithNoBracketsIsBalanced() {
        assertThat(validator.validate("MOVE A TO B").valid()).isTrue();
    }

    @Test
    void picClauseParenthesesAreBalanced() {
        BracketValidationResult result = validator.validate("05 CUSTOMER-NAME PIC X(30).");

        assertThat(result.valid()).isTrue();
    }

    @Test
    void nestedMixedBracketTypesAreBalanced() {
        BracketValidationResult result = validator.validate("COMPUTE X = ([A + B] * {C - D})");

        assertThat(result.valid()).isTrue();
    }

    @Test
    void aClosingBracketWithNothingOpenIsRejected() {
        BracketValidationResult result = validator.validate("MOVE A) TO B");

        assertThat(result.valid()).isFalse();
        assertThat(result.message()).contains("unexpected").contains(")");
    }

    @Test
    void mismatchedBracketTypesAreRejected() {
        BracketValidationResult result = validator.validate("COMPUTE X = (A + B]");

        assertThat(result.valid()).isFalse();
        assertThat(result.message()).contains("expected").contains("]");
    }

    @Test
    void anUnclosedBracketAtEndOfLineIsRejected() {
        BracketValidationResult result = validator.validate("PIC X(30");

        assertThat(result.valid()).isFalse();
        assertThat(result.message()).contains("unclosed").contains("(");
    }

    @Test
    void anUnclosedBraceIsAlsoRejected() {
        BracketValidationResult result = validator.validate("COMPUTE X = {A + B");

        assertThat(result.valid()).isFalse();
        assertThat(result.message()).contains("unclosed");
    }
}

View full JaCoCo coverage report →