Stack

Last In, First Out, simple as that.

Context

A stack is a deliberately constrained data structure that enforces Last In, First Out (LIFO) ordering.

It typically exposes only three operations: push, pop, and peek, all with O(1) time complexity.

The most common real-world example is the call stack, where function frames are pushed on entry and popped on return.

• They shine when history matters more than access.
• Stacks are rarely used to store data long-term; they model process, not state.
• It can be implemented with:
  • a linked list (no resizing, more allocations)
  • an array (better cache locality, needs growth strategy)

Core idea

• Maintain a pointer to the top of the stack.
• Each element is wrapped in a Node that points to the previous element.
• All operations manipulate only the top reference, guaranteeing constant time.

Implementation

import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.NoSuchElementException;

public class Stack<T> implements Iterable<T> {
    private Node<T> head;
    private int size;
    private int modCount;
    
    public void push(T element) {
        head = new Node<>(element, head);
        size++;
        modCount++;
    }
    
    public T pop() {
        if (isEmpty()) return null;
        
        var value = head.value;
        head = head.previous;
        size--;
        modCount++;
        return value;
    }
    
    public T peek() {
        return isEmpty() ? null : head.value;
    }
    
    public boolean isEmpty() { return size == 0; }
    
    public int size() { return size; }
    
    @Override
    public Iterator<T> iterator() { return new StackIterator(); }
   
    private record Node<T>(T value, Node<T> previous) { }
    
    private final class StackIterator implements Iterator<T> {
        private Node<T> current = head;
        private int expectedModCount = modCount;
        
        @Override
        public boolean hasNext() {
            if (expectedModCount != modCount) throw new ConcurrentModificationException();
            return current != null;
        }
        
        @Override
        public T next() {
            if (!hasNext()) throw new NoSuchElementException();
            var value = current.value;
            current = current.previous;
            return value;
        }
    }
}