Stack Basics

1. Introduction: The Pancake Pile

Imagine you are making pancakes. As each pancake finishes cooking, you place it on a plate. You stack them one on top of the other. When you are ready to eat, you don't grab the bottom pancake—it's crushed under the weight of the others! You grab the top pancake. The last pancake you put on the plate is the first one you eat.

This is a Stack. It is a linear data structure that strictly follows the Last-In, First-Out (LIFO) principle. In computer science, Stacks are ubiquitous. The "Undo" button (Ctrl+Z) in your text editor is a Stack. Your web browser's "Back" button is a Stack. The operating system's Memory Call Stack (which tracks recursive functions) is a Stack.

2. Core Concept: LIFO Operations

A Stack restricts access to a single point: the "Top".

1. Push (push): Add an element to the top of the Stack.
2. Pop (pop): Remove and return the element at the top of the Stack.
3. Peek (peek): Look at the top element without removing it.

Java Implementation Warning: NEVER USE java.util.Stack!

Java has a legacy class called java.util.Stack (from Java 1.0). It is considered obsolete and highly discouraged. Why? Because it extends Vector, which means every single method is synchronized (thread-safe). This locks the object on every operation, creating massive unnecessary performance overhead for single-threaded algorithms.

The Solution: Always use java.util.ArrayDeque (Double Ended Queue). It is blazingly fast, uses contiguous array memory, and implements the push, pop, and peek methods perfectly.

import java.util.ArrayDeque;
import java.util.Deque;

public class BestPracticeStack {
    public static void main(String[] args) {
        // CORRECT: Fast and efficient
        Deque<Integer> stack = new ArrayDeque<>();
        
        // INCORRECT: Legacy, slow, synchronized
        // Stack<Integer> badStack = new Stack<>(); 
    }
}

3. Beginner Code Example: String Reversal

The most fundamental property of LIFO is Reversal. Whatever order you put things into a Stack, they come out in the exact opposite order.

Problem Statement: Write a function to reverse a string using a Stack.

import java.util.ArrayDeque;
import java.util.Deque;

public class StackReversal {
    public static String reverseString(String s) {
        Deque<Character> stack = new ArrayDeque<>();
        
        // 1. Push all characters onto the stack
        for (char c : s.toCharArray()) {
            stack.push(c);
        }
        
        // 2. Pop them off (they will come out in reverse order!)
        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()) {
            sb.append(stack.pop());
        }
        
        return sb.toString();
    }
}

Note: In reality, reversing a string with Two Pointers is $O(1)$ space. Doing it with a Stack is $O(N)$ space. However, this perfectly illustrates the structural behavior of the Stack.

4. Intermediate Code Example: Array Implementation

In system design interviews or embedded C programming, you might be asked to implement a Stack from scratch using a primitive fixed-size array.

The Insight: An array stack is incredibly simple. You allocate an array and keep a single integer variable topIndex initialized to -1.

• To push, increment topIndex and write to the array.
• To pop, read from the array and decrement topIndex. (You don't even need to delete the old data, because the topIndex boundary prevents anyone from reading it!)

public class MyArrayStack {
    private int[] data;
    private int topIndex;
    private int capacity;

    public MyArrayStack(int size) {
        this.capacity = size;
        this.data = new int[capacity];
        this.topIndex = -1; // Stack is empty
    }
    
    // O(1) Push
    public boolean push(int val) {
        if (isFull()) {
            System.out.println("Stack Overflow!");
            return false;
        }
        
        topIndex++;
        data[topIndex] = val;
        return true;
    }
    
    // O(1) Pop
    public int pop() {
        if (isEmpty()) {
            throw new RuntimeException("Stack Underflow!");
        }
        
        int value = data[topIndex];
        topIndex--; // We just move the boundary!
        return value;
    }
    
    // O(1) Peek
    public int peek() {
        if (isEmpty()) throw new RuntimeException("Stack is empty");
        return data[topIndex];
    }
    
    public boolean isEmpty() { return topIndex == -1; }
    public boolean isFull() { return topIndex == capacity - 1; }
}

5. Intermediate Code Example: Linked List Implementation

What if you don't know the capacity in advance, and you don't want to deal with array resizing? You can implement a Stack using a Singly Linked List!

The Insight: To maintain $O(1)$ push and pop, we must perform all operations at the HEAD of the Linked List. (If we added to the tail, popping would require an $O(N)$ traversal to find the node right before the tail).

class StackNode {
    int val;
    StackNode next;
    StackNode(int val) { this.val = val; }
}

public class MyLinkedStack {
    private StackNode head;
    
    public MyLinkedStack() {
        this.head = null;
    }
    
    // O(1) Push (Insert at Head)
    public void push(int val) {
        StackNode newNode = new StackNode(val);
        newNode.next = head;
        head = newNode; // The new node is the new top of the stack
    }
    
    // O(1) Pop (Remove from Head)
    public int pop() {
        if (isEmpty()) throw new RuntimeException("Stack Underflow");
        
        int value = head.val;
        head = head.next; // Sever the top node, moving head down
        return value;
    }
    
    public int peek() {
        if (isEmpty()) throw new RuntimeException("Stack empty");
        return head.val;
    }
    
    public boolean isEmpty() {
        return head == null;
    }
}

6. Common Mistakes Beginners Make

1. Using java.util.Stack

   • The Mistake: Stack<Integer> s = new Stack<>();
   • Why it's wrong: Slower execution due to legacy thread synchronization.
   • The Fix: Use Deque<Integer> s = new ArrayDeque<>();.

2. Crashing on Empty Stacks

   • The Mistake: int val = stack.pop(); without checking stack.isEmpty().
   • Why it's wrong: pop() throws a NoSuchElementException if the structure is empty. If you aren't 100% sure the stack has items, always wrap it in an !isEmpty() check.

3. Confusing Queue and Stack methods on Deque

   • The Mistake: Mixing offer()/poll() with push()/pop().
   • Why it's wrong: Because ArrayDeque implements both Queue and Stack, it allows both. offer() adds to the BACK. push() adds to the FRONT. If you mix them, your data will be severely corrupted. Pick the Stack methods (push, pop, peek) and strictly stick to them.

7. Interview Q&A

Q1: Stack Overflow vs Stack Underflow? Answer: Stack Overflow occurs when you try to push to a fixed-size stack that is completely full (commonly seen when recursive functions have no base case and exceed the OS memory limit). Stack Underflow occurs when you try to pop from a stack that is empty.

Q2: ArrayStack vs LinkedStack. Which is better? Answer: ArrayStack (ArrayDeque) is significantly better for 99% of use cases. Even with dynamic resizing, the amortized time is $O(1)$. It benefits massively from CPU Cache Locality (elements are adjacent in hardware RAM). LinkedStack scatters nodes across the heap, triggering frequent garbage collection and cache misses.

8. Practice Problems

1. Implement Stack using Arrays/LinkedLists
   • Goal: Build both structures from memory. Understand why Linked List pushes to the Head.
2. Reverse a String
   • Goal: Master the structural reversal property.
3. Design a Browser History (LeetCode 1472)
   • Hint: Use two Stacks! One for the "Back" button (history), and one for the "Forward" button (future).

9. Summary

• LIFO: Last-In, First-Out.
• Java Syntax: Always use Deque<Integer> stack = new ArrayDeque<>();. Never use the legacy Stack class.
• Core Methods: push() adds. pop() removes and returns. peek() returns without removing.
• Implementations: In an array, push simply increments an index. In a Linked List, push inserts a new Head node.