A stack is a linear collection that restricts element access to a single endpoint, commonly referred to as the top. This constraint enforces a Last-In-First-Out (LIFO) ordering, meaning the most recently added item is always the first to be removed. The two fundamental operations are push (insertion at the top) and pop (removal from the top). A secondary operation, peek, allows inspection of the top element without modifying the collection.

Manual Implementation Strategies

Developers can construct a stack from scratch using either contiguous memory blocks (arrays) or node-based references (linked lists).

Array-Backed Implemantation

An array-based stack utilizes a fixed-size buffer and an index tracker to manage the top position. This approach offers O(1) time complexity for core operations but requires capacity management.

public class BoundedStack {
    private final int[] buffer;
    private int cursor;

    public BoundedStack(int capacity) {
        if (capacity <= 0) throw new IllegalArgumentException("Capacity must be positive");
        this.buffer = new int[capacity];
        this.cursor = -1;
    }

    public void push(int item) {
        if (cursor == buffer.length - 1) {
            throw new IllegalStateException("Capacity exceeded");
        }
        buffer[++cursor] = item;
    }

    public int pop() {
        if (cursor == -1) {
            throw new IllegalStateException("Stack is empty");
        }
        int removed = buffer[cursor];
        buffer[cursor--] = 0;
        return removed;
    }

    public int peek() {
        if (cursor == -1) {
            throw new IllegalStateException("Stack is empty");
        }
        return buffer[cursor];
    }

    public boolean hasElements() {
        return cursor != -1;
    }
}

The cursor variable tracks the index of the most recently inserted value. Incrementing occurs before assignment during insertion, while decrementing happens after retrieval during removal.

Reference-Based Implementation

A linked structure eliminates fixed capacity limits by allocating memory dynamically. Using a singly linked list where the head represents the top ensures constant-time insertions and deletions.

public class ReferenceStack {
    private static class Node {
        final int payload;
        Node link;

        Node(int payload, Node link) {
            this.payload = payload;
            this.link = link;
        }
    }

    private Node apex;
    private int count;

    public ReferenceStack() {
        this.apex = null;
        this.count = 0;
    }

    public void push(int item) {
        apex = new Node(item, apex);
        count++;
    }

    public int pop() {
        if (apex == null) {
            throw new IllegalStateException("No elements to remove");
        }
        int result = apex.payload;
        apex = apex.link;
        count--;
        return result;
    }

    public int peek() {
        if (apex == null) {
            throw new IllegalStateException("No elements to inspect");
        }
        return apex.payload;
    }

    public boolean hasElements() {
        return count > 0;
    }
}

By pointing the new node’s link to the current apex and then reassigning apex, the structure maintains LIFO order without traversing the list.

Standard Library Usage

Java provides java.util.Stack, a legacy collection class that extends Vector. While modern development often favors ArrayDeque for stack operations, Stack remains widely recognized for its explicit API.

import java.util.Stack;

public class StandardStackDemo {
    public static void main(String[] args) {
        Stack<String> history = new Stack<>();

        history.push("Page_A");
        history.push("Page_B");
        history.push("Page_C");

        System.out.println("Current top: " + history.peek());
        System.out.println("Removed: " + history.pop());
        System.out.println("New top: " + history.peek());
        System.out.println("Is empty: " + history.isEmpty());
    }
}

The standard implementation handles dynamic resizing automatically and includes thread-safe synchronization, though this introduces overhead in single-threaded contexts.

Practical Application: Postfix Expression Evaluation

Stacks excel at parsing and evaluating mathematical expressions, particularly postfix (Reverse Polish Notation) formats. In postfix notation, operators follow their operands, eliminating the need for parentheses and precedence rules.

The evaluation algorithm processes tokens sequentially:

1. Push operands onto the stack.
2. When an operator is encountered, pop the required number of operands, apply the operation, and push the result back.
3. The final remaining value is the expression result.

import java.util.Stack;

public class PostfixCalculator {
    public static int compute(String expression) {
        Stack<Integer> operands = new Stack<>();
        String[] tokens = expression.trim().split("\\s+");

        for (String token : tokens) {
            if (token.matches("-?\\d+")) {
                operands.push(Integer.parseInt(token));
            } else {
                int right = operands.pop();
                int left = operands.pop();
                operands.push(applyOperation(token.charAt(0), left, right));
            }
        }
        return operands.pop();
    }

    private static int applyOperation(char operator, int left, int right) {
        switch (operator) {
            case '+': return left + right;
            case '-': return left - right;
            case '*': return left * right;
            case '/':
                if (right == 0) throw new ArithmeticException("Division by zero");
                return left / right;
            default:
                throw new IllegalArgumentException("Unsupported operator: " + operator);
        }
    }

    public static void main(String[] args) {
        String rpn = "5 1 2 + 4 * + 3 -";
        System.out.println("Evaluation result: " + compute(rpn));
    }
}

This implementation processses space-separated tokens, supports multi-digit integers, and isolates arithmetic logic into a dedicated helper method. The stack temporarily holds intermediate calculation states, demonstrating how LIFO ordering naturally aligns with nested computational dependencies. Similar mechanisms power function call management, syntax parsing in compilers, and depth-first traversal algorithms.