Building a Custom Java Stack: LIFO Mechanics & Why Legacy Stack is Broken

Building an Undo (Ctrl+Z) feature for a photo editor or code editor requires tracking user actions in strict reverse chronological order.

Every time a user draws a shape, changes a color, or types a line of text, your application records that action. When the user presses Ctrl+Z (Undo), the editor must reverse the most recent action first.

If you store user actions inside a standard list and remove from position 0, pressing Undo would revert the first action performed two hours ago instead of the stroke made one second ago.

This access pattern requires Last-In-First-Out (LIFO) order. The last item pushed in is the first item popped out.

---

Why You Need This in Real Life

LIFO stacks underpin foundational systems across software engineering:

• JVM Call Stacks: When method A() calls method B(), the JVM pushes frame B() onto the thread execution stack. When B() finishes, the frame pops off, returning execution context to A().
• Parsing Expression Trees: Balancing parentheses in JSON, XML, or math expressions (((a + b) * c)).
• Undo / Redo History Buffers: Tracking reversible application state mutations.

---

A Production Pitfall: The java.util.Stack Legacy Trap

Many Java developers reach for java.util.Stack out of habit.

In Java 1.0, java.util.Stack was created as a direct subclass of java.util.Vector:

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

This 1996 design decision created two severe production flaws:

1. Broken Encapsulation: Because Stack inherits from Vector, code can call stack.add(index, element) or stack.remove(0), inserting items into the middle of the stack and violating LIFO invariants.
2. Synchronization Locks: Every method in Vector contains the synchronized keyword, imposing lock overhead on single-threaded execution.

Modern Java applications use ArrayDeque or custom stack structures instead of legacy java.util.Stack.

---

The LIFO Mental Model

Think of a stack like a spring-loaded plate dispenser in a cafeteria.

PUSH "C"                       POP
   |                            ^
   v                            |
+------+                     +------+
| "C"  | <--- TOP            | "C"  | <--- Returns "C"
+------+                     +------+
| "B"  |                     | "B"  | <--- New TOP
+------+                     +------+
| "A"  |                     | "A"  |
+------+                     +------+

The fundamental API contract requires four operations:

• push(E item): Places an element onto the top of the stack.
• pop(): Removes and returns the element at the top.
• peek(): Inspects the top element without removing it.
• isEmpty(): Checks if the stack contains zero items.

---

Array-Backed Stack Implementation

An array makes an efficient backing store for a stack because all push/pop operations take place at the highest array index (size - 1). No element shifting is ever required.

import java.util.EmptyStackException;

public class MyArrayStack<T> {
    private Object[] elements;
    private int size = 0;
    private static final int DEFAULT_CAPACITY = 10;

    public MyArrayStack() {
        this.elements = new Object[DEFAULT_CAPACITY];
    }

    public void push(T item) {
        ensureCapacity();
        elements[size++] = item;
    }

    @SuppressWarnings("unchecked")
    public T pop() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        T item = (T) elements[--size];
        elements[size] = null; // Clear reference for GC!
        return item;
    }

    @SuppressWarnings("unchecked")
    public T peek() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        return (T) elements[size - 1];
    }

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

    public int size() {
        return size;
    }

    private void ensureCapacity() {
        if (size == elements.length) {
            elements = java.util.Arrays.copyOf(elements, elements.length * 2);
        }
    }
}

---

Linked-Node-Backed Stack Implementation

If you require exact $O(1)$ push and pop operations without any array resizing pauses, use a singly linked node structure where top represents the head of the list.

import java.util.EmptyStackException;

public class MyLinkedStack<T> {
    private static class Node<T> {
        T data;
        Node<T> next;

        Node(T data, Node<T> next) {
            this.data = data;
            this.next = next;
        }
    }

    private Node<T> top = null;
    private int size = 0;

    public void push(T item) {
        top = new Node<>(item, top);
        size++;
    }

    public T pop() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        T data = top.data;
        top = top.next;
        size--;
        return data;
    }

    public T peek() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        return top.data;
    }

    public boolean isEmpty() {
        return top == null;
    }

    public int size() {
        return size;
    }
}

---

Quick Summary

• Stacks enforce Last-In-First-Out (LIFO) order.
• Array backings offer compact memory layouts; linked node backings eliminate resize latency.
• Avoid legacy java.util.Stack due to inherited Vector synchronization locks and broken API encapsulation.

References & Further Reading

1. OpenJDK. JEP 180: Handle Frequent HashMap Collisions with Balanced Trees. OpenJDK JEP Standard.
2. OpenJDK Repository. OpenJDK 21 Source Code: java.util.HashMap. GitHub.
3. Cormen, T. H., et al. (2022). Introduction to Algorithms (4th Edition) — Chapter 11: Hash Tables. MIT Press.

---