A stack is a linear data structure that restricts insertion and deletion operations to one end—commonly referred to as the top. This constraint enforces a Last-In-First-Out (LIFO) behavior: the most recently added element is the first to be removed.

Core Terminology

• Top: The active end where all push and pop operations occur.
• Bottom: The fixed, inactive end of the stack.
• Push: Inserting an element onto the top.
• Pop: Removing and returning the topmost element.

Custom Stack Implementations

1. Array-Based Stack

This implementation uses a dynamically resizing integer array to store elements, with an explicit size tracker.

Key Components

public class ArrayStack {
    private int[] storage;
    private int currentSize;

    public ArrayStack() {
        this.storage = new int[8]; // initial capacity
        this.currentSize = 0;
    }
}

Core Operations

• Push: Resizes the internal array if full before appending.
• Pop: Throws IllegalStateException if empty; otherwise returns and decrements.
• Peek: Returns top value with out mutation; throws expection on empty stack.
• Size & Empty Check: Direct access to currentSize.

Example push:

public void push(int value) {
    if (currentSize == storage.length) {
        storage = Arrays.copyOf(storage, storage.length * 2);
    }
    storage[currentSize++] = value;
}

Example pop:

public int pop() {
    if (isEmpty()) {
        throw new IllegalStateException("Cannot pop from an empty stack");
    }
    return storage[--currentSize];
}

2. Linked-List-Based Stack

To avoid array resizing overhead and achieve O(1) amortized operations, a singly linked list suffices—even though doubly linked lists are sometimes considered, they're unnecessary here since only the tail (top) is accessed.

Node Definition

private static class Node {
    int data;
    Node next;

    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

Implementation Highlights

• Uses a top reference (no need for head or tail pointers).
• push inserts at the front (O(1)).
• pop removes from the front (O(1)).
• size() traverses once per call (O(n)), but can be optimized by tracking count.

Example push:

public void push(int value) {
    Node newNode = new Node(value);
    newNode.next = top;
    top = newNode;
    currentSize++;
}

Example pop:

public int pop() {
    if (isEmpty()) {
        throw new IllegalStateException("Cannot pop from an empty stack");
    }
    int result = top.data;
    top = top.next;
    currentSize--;
    return result;
}

Built-in java.util.Stack

The standard library’s Stack class extends Vector, inheriting thread-safety and dynamic resizing. While functional, it's largely discouraged in modern Java due to performance overhead and design limitations.

Key methods include:

• push(E item) — adds to top
• pop() — removes and returns top
• peek() — inspects top without removal
• empty() — checks emptiness
• search(Object o) — returns 1-based possition from top

Note: For production code, prefer Deque implementations like ArrayDeque, which offer better performance and are designed specifically for stack/queue use cases.

Common Algorithmic Applications

Stacks underpin many classic problems, including:

• Validating balanced parentheses (e.g., "{[()]}")
• Evaluating postfix (Reverse Polish Notation) expressions
• Verifying valid push/pop sequences
• Maintaining minimum values during operations (Min Stack)