Stacks & Applications

Now let's implement a stack from scratch! We'll build two versions: one using an array (fixed size) and one using a linked list (dynamic size). Understanding both will deepen your knowledge of data structures.

Method 1: Using Array

The simplest approach - use an array and a top variable to track the current position. Think of top as a finger pointing to the topmost element.

We need three things to build our stack: an array to hold the data, a top variable to track where the newest element is, and a capacity to know the maximum size. The constructor sets up these pieces. We start with top = -1 because the stack is empty - there's no valid element yet!

class ArrayStack {
    private int[] arr;      // Array to store elements
    private int top;        // Index of top element
    private int capacity;   // Maximum size
    
    public ArrayStack(int capacity) {
        this.capacity = capacity;
        this.arr = new int[capacity];
        this.top = -1;  // Empty stack starts at -1
    }
}

The push method adds a new element to the top of the stack. First, we check if there's room - if the array is already full, we can't add more! Then we use a clever trick: ++top increments the index first, then we store the value at that new position. This way, we move to the next empty slot and fill it in one step.

public void push(int x) {
    if (isFull()) {
        throw new RuntimeException("Stack Overflow");
    }
    arr[++top] = x;  // Increment top, then store
}
// Example: push(10) when top=-1 → top becomes 0, arr[0]=10

The pop method removes and returns the top element. Safety first - we check if the stack is empty before trying to remove anything! The expression arr[top--] does two things: it grabs the value at the current top position, then decrements the index. The element isn't really "deleted" - it's still in the array - but since top moved down, it's now considered "out of bounds" and will be overwritten on the next push.

public int pop() {
    if (isEmpty()) {
        throw new RuntimeException("Stack Underflow");
    }
    return arr[top--];  // Return value, then decrement top
}
// Example: pop() when top=2 → returns arr[2], top becomes 1

Sometimes you want to see what's on top without actually removing it - that's what peek does. Think of it like peeking at the top card of a deck without taking it. We simply return the value at the current top index, and the stack stays exactly the same. Don't forget to check if empty first - peeking at an empty stack would give us garbage data!

public int peek() {
    if (isEmpty()) {
        throw new RuntimeException("Stack is empty");
    }
    return arr[top];  // Just look, don't modify top
}
// Example: peek() when top=2 → returns arr[2], top stays 2

These helper methods tell us about the stack's current state. isEmpty() checks if top is -1, meaning nothing has been pushed yet. isFull() checks if we've used all available slots - since arrays are 0-indexed, the last valid index is capacity - 1. The size() method returns how many elements are currently in the stack, which is top + 1 because top is an index, not a count.

public boolean isEmpty() {
    return top == -1;  // No elements
}

public boolean isFull() {
    return top == capacity - 1;  // Array is full
}

public int size() {
    return top + 1;  // Number of elements (0-indexed)
}

Method 2: Using Linked List

With a linked list, we get a dynamic-sized stack - no overflow possible (unless you run out of memory)! New elements are added at the head of the list, making push/pop both O(1).

In a linked list stack, each element lives in its own "node" object. A node holds two things: the actual value and a reference (pointer) to the next node below it. The top variable always points to the head node - the most recently added element. Unlike arrays, we don't need to declare a fixed size upfront. The stack can grow and shrink dynamically as we push and pop!

class LinkedListStack {
    private class Node {
        int val;        // Data stored in node
        Node next;      // Pointer to next node
        Node(int val) { this.val = val; }
    }
    
    private Node top;   // Points to top element (head)
    private int size;   // Track number of elements
}

To push onto a linked list stack, we create a brand new node with our value. Then we link this new node to whatever was previously on top (even if it's null for an empty stack). Finally, we update top to point to our new node. It's like adding a new link at the beginning of a chain - the new link becomes the first one, and it holds onto the rest of the chain.

public void push(int x) {
    Node newNode = new Node(x);  // Create new node
    newNode.next = top;          // Point to current top
    top = newNode;               // New node becomes top
    size++;
}
// Visual: [new] -> [old top] -> [rest...]

Popping from a linked list is like removing the first link of a chain. First, we save the value stored in the top node (we need to return it!). Then we simply move the top pointer to the next node in line. The old top node gets disconnected and Java's garbage collector will clean it up automatically. No shifting elements around like in an array!

public int pop() {
    if (isEmpty()) {
        throw new RuntimeException("Stack Underflow");
    }
    int val = top.val;    // Save value to return
    top = top.next;       // Move top to next node
    size--;
    return val;
}
// Visual: [removed] | [new top] -> [rest...]

The peek method lets us see the top value without modifying the stack - we just return top.val directly. For isEmpty(), we check if top is null, which means no nodes exist yet. Unlike the array version, there's no isFull() method because a linked list can keep growing until your computer runs out of memory. The size() method returns our manually tracked count.

public int peek() {
    if (isEmpty()) {
        throw new RuntimeException("Stack is empty");
    }
    return top.val;  // Just return, don't modify
}

public boolean isEmpty() {
    return top == null;  // No nodes exist
}

public int size() {
    return size;
}

Array vs Linked List: Which to Choose?

Good news - you don't have to build a stack from scratch every time! Java provides ready-to-use stack implementations. Let's explore the different options and learn which one to use in different situations.

First, import the classes you need. Java has a dedicated Stack class, but modern Java developers prefer Deque (Double-Ended Queue) which can work as both a stack and a queue. ArrayDeque is the most efficient implementation for stack operations.

import java.util.Stack;
import java.util.Deque;
import java.util.ArrayDeque;
import java.util.LinkedList;

The Stack class has been in Java since version 1.0. It works fine but has a hidden cost: it's synchronized, meaning it's thread-safe but slower for single-threaded programs (which is most of the time!). The methods are intuitive: push() adds, pop() removes, peek() looks, and isEmpty() checks.

// Using Stack class (older, synchronized)
Stack stack1 = new Stack<>();
stack1.push(1);
stack1.push(2);
int top = stack1.peek();   // 2
int popped = stack1.pop(); // 2
boolean empty = stack1.isEmpty();

This is the recommended approach in modern Java! ArrayDeque is faster than Stack because it's not synchronized. We declare it as type Deque (the interface) but create an ArrayDeque (the implementation). This is good practice - code to the interface! The methods work exactly the same way.

// Using Deque (preferred - faster, not synchronized)
Deque stack2 = new ArrayDeque<>();
stack2.push(1);            // Adds to front
stack2.push(2);
int top2 = stack2.peek();  // 2
int popped2 = stack2.pop(); // 2

You can also use LinkedList as a stack since it implements the Deque interface too. It's slightly slower than ArrayDeque for pure stack operations, but useful if you need both stack and queue functionality, or if you're doing lots of insertions in the middle.

// LinkedList can also be used as stack
Deque stack3 = new LinkedList<>();
stack3.push(1);
stack3.push(2);

Here's a pattern you'll use constantly in interviews and real code: always check if the stack is empty before calling pop() or peek(). If you try to pop from an empty stack, Java throws an exception and your program crashes! This defensive check prevents that.

// Common pattern: checking before pop
if (!stack.isEmpty()) {
    int val = stack.pop();
}
// Or use a ternary for peek
int topVal = stack.isEmpty() ? -1 : stack.peek();

This is the classic stack problem and one of the most common interview questions! The idea is simple: every opening bracket needs a matching closing bracket in the right order. Stacks are perfect for this because the most recent opening bracket must be closed first (LIFO).

Why Stacks Are Perfect for This

Consider the string "([{}])". The innermost bracket {} must close first, then [], then (). This is exactly LIFO order!

char '(' → Push!   Stack: [(]
char '[' → Push!   Stack: [(, []
char '{' → Push!   Stack: [(, [, {]

Opening brackets always get pushed!

char '}' → Pop {  Match? ✓  Stack: [(, []
char ']' → Pop [  Match? ✓  Stack: [(]
char ')' → Pop (  Match? ✓  Stack: []

Stack empty + all matched = VALID!

"([)]" → Wrong order! Push (, Push [, See ) but top is [ → MISMATCH!

"((("  → Not closed! Stack still has [(, (, (] at end → NOT EMPTY!

")))(" → Extra close! Pop on empty stack for first ) → UNDERFLOW!

This is the most straightforward approach and easiest to understand. We create a stack to hold opening brackets. As we scan through each character in the string, we decide whether to push it (if it's an opening bracket) or try to match it with what's on top of the stack (if it's a closing bracket).

// Valid Parentheses - LeetCode 20
// Check if string has balanced brackets: (), [], {}
boolean isValid(String s) {
    Deque stack = new ArrayDeque<>();
    
    for (char c : s.toCharArray()) {
        // Push opening brackets
        if (c == '(' || c == '[' || c == '{') {
            stack.push(c);
        }

When we encounter a closing bracket, we need to check two things: (1) Is there even an opening bracket waiting to be matched? If the stack is empty, we have an "orphan" closing bracket with no partner - that's invalid! (2) Does the closing bracket match the most recent opening bracket? We pop the top and compare.

        else {
            // Check for matching closing bracket
            if (stack.isEmpty()) return false;
            
            char top = stack.pop();
            if (c == ')' && top != '(') return false;
            if (c == ']' && top != '[') return false;
            if (c == '}' && top != '{') return false;
        }
    }

After processing all characters, we do one final check: is the stack empty? If there are leftover opening brackets in the stack, they never got matched with closing brackets - that means the string is invalid. Only if every opening bracket found its closing partner do we return true.

    return stack.isEmpty();  // All brackets matched
}

This approach uses a Map to store the bracket pairs, making the code more elegant and easier to extend. The map stores closing brackets as keys and their matching opening brackets as values. This way, we can look up what opening bracket should match any closing bracket we encounter.

// Alternative with map
boolean isValidV2(String s) {
    Deque stack = new ArrayDeque<>();
    Map map = Map.of(
        ')', '(',
        ']', '[',
        '}', '{'
    );

Now the logic becomes cleaner: if the character is an opening bracket (exists as a value in our map), push it. If it's a closing bracket (exists as a key), pop and verify the match in one line. The expression stack.pop() != map.get(c) checks if what we popped matches what this closing bracket expects.

    for (char c : s.toCharArray()) {
        if (map.containsValue(c)) {
            stack.push(c);
        } else if (map.containsKey(c)) {
            if (stack.isEmpty() || stack.pop() != map.get(c)) {
                return false;
            }
        }
    }
    
    return stack.isEmpty();
}

This is a clever variation! Instead of checking validity, we count how many brackets we'd need to INSERT to make the string valid. We track two counters: open for unmatched opening brackets, and close for unmatched closing brackets. When we see (, we increment open. When we see ), we try to match it with an existing (.

// Minimum Add to Make Parentheses Valid
// Count minimum insertions needed
int minAddToMakeValid(String s) {
    int open = 0;   // Unmatched '('
    int close = 0;  // Unmatched ')'
    
    for (char c : s.toCharArray()) {
        if (c == '(') {
            open++;
        } else {
            if (open > 0) {
                open--;  // Match with open
            } else {
                close++;  // Unmatched close
            }
        }
    }
    
    return open + close;  // Total unmatched brackets
}

How does your calculator know that 3 + 2 * 4 equals 11 (not 20)? It needs to handle operator precedence! Stacks make this elegant. Let's start with the simpler case: Reverse Polish Notation (RPN) where precedence is already resolved.

What is Reverse Polish Notation (Postfix)?

Instead of writing 3 + 4, we write 3 4 +. The operator comes after its operands. Why? No parentheses needed and precedence is built in!

Token "2" (number) → Push 2     Stack: [2]
Token "1" (number) → Push 1     Stack: [2, 1]
Token "+" (operator):
  → Pop 1 (b), Pop 2 (a)
  → Calculate: a + b = 2 + 1 = 3
  → Push 3             Stack: [3]
Token "3" (number) → Push 3     Stack: [3, 3]
Token "*" (operator):
  → Pop 3 (b), Pop 3 (a)
  → Calculate: a * b = 3 * 3 = 9
  → Push 9             Stack: [9]

If number:
  → Push to stack

If operator:
  → Pop b (top)
  → Pop a (second)
  → Calculate a op b
  → Push result

Final answer:
  → Pop the stack!

The main function loops through each token in the expression. If it's a number, we push it onto the stack. If it's an operator, we pop two values, perform the calculation, and push the result back. At the end, the final answer is the only value left on the stack.

// Evaluate Reverse Polish Notation (Postfix)
// ["2","1","+","3","*"] = ((2 + 1) * 3) = 9
int evalRPN(String[] tokens) {
    Deque stack = new ArrayDeque<>();
    
    for (String token : tokens) {
        if (isOperator(token)) {
            int b = stack.pop();  // Pop top (second operand)
            int a = stack.pop();  // Pop next (first operand)
            stack.push(calculate(a, b, token));
        } else {
            stack.push(Integer.parseInt(token));
        }
    }
    
    return stack.pop();  // Final result
}

We need a helper function to check if a token is an operator. This keeps our main logic clean and readable. We simply check if the string equals any of the four basic arithmetic operators.

private boolean isOperator(String s) {
    return s.equals("+") || s.equals("-") || 
           s.equals("*") || s.equals("/");
}

The calculate helper performs the actual arithmetic. Notice we use a op b order - this is critical! When we popped, b came first (it was on top), so a is actually the first operand in the original expression. For "10 3 -", we want 10 - 3, not 3 - 10.

private int calculate(int a, int b, String op) {
    switch (op) {
        case "+": return a + b;
        case "-": return a - b;
        case "*": return a * b;
        case "/": return a / b;
        default: throw new IllegalArgumentException();
    }
}

Basic Calculator II: Handling Infix Notation

Now for the harder problem: evaluating normal infix expressions like "3+2*2". The trick is handling operator precedence - multiplication and division happen before addition and subtraction. We use a clever approach: process * and / immediately, but delay + and - by pushing values to the stack.

// Basic Calculator II: "3+2*2" = 7
int calculate(String s) {
    Deque stack = new ArrayDeque<>();
    int num = 0;        // Current number being built
    char lastOp = '+';  // Previous operator (start with + for first number)

We iterate through each character. When we see a digit, we build up the current number (handling multi-digit numbers like "123" by multiplying by 10 and adding). We skip spaces entirely.

    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        
        if (Character.isDigit(c)) {
            num = num * 10 + (c - '0');  // Build multi-digit number
        }

When we hit an operator (or reach the end), we process the previous number based on the previous operator. For + we push the number, for - we push the negative. For * and / we pop, calculate immediately, and push the result. This ensures * and / are evaluated before + and -.

        if ((!Character.isDigit(c) && c != ' ') || i == s.length() - 1) {
            switch (lastOp) {
                case '+': stack.push(num); break;
                case '-': stack.push(-num); break;
                case '*': stack.push(stack.pop() * num); break;
                case '/': stack.push(stack.pop() / num); break;
            }
            lastOp = c;  // Save current operator for next iteration
            num = 0;     // Reset for next number
        }
    }

Finally, sum up everything in the stack. Because we pushed negative values for subtraction, a simple sum gives us the correct answer. For "3+2*2": we push 3, then push 4 (2*2 evaluated immediately), and 3+4 = 7.

    int result = 0;
    while (!stack.isEmpty()) {
        result += stack.pop();
    }
    return result;
}

This is where stacks get really powerful! A monotonic stack maintains elements in sorted order - either always increasing or always decreasing from bottom to top. It's a magical technique for solving "next greater/smaller" problems in O(n) instead of O(n²)!

When to Use Monotonic Stack?

Whenever you see these keywords in a problem, think monotonic stack:

i=0: Push 0     Stack: [0]       (index of 2)
i=1: 1 < 2?     Stack: [0,1]     (push 1)
i=2: 2 > 1?     Pop 1! result[1]=2
     2 ≤ 2?     Stack: [0,2]     (push 2)
i=3: 4 > 2?     Pop 2! result[2]=4
     4 > 2?     Pop 0! result[0]=4
     Stack: [3]         (push 3)
i=4: 3 < 4?     Stack: [3,4]     (push 4)

Index:  0   1   2   3   4
Input:  2   1   2   4   3
Result: 4   2   4  -1  -1

Explanation:
• 2 → next greater is 4
• 1 → next greater is 2
• 2 → next greater is 4
• 4 → no greater to right → -1
• 3 → no greater to right → -1

This is the classic monotonic stack problem. For each element in the array, we want to find the first element to its right that is greater. We use a stack to store indices of elements that haven't found their "next greater" yet.

// Next Greater Element
// For each element, find next greater element to its right
int[] nextGreaterElement(int[] nums) {
    int n = nums.length;
    int[] result = new int[n];
    Arrays.fill(result, -1);  // Default: no greater element
    
    Deque stack = new ArrayDeque<>();  // Store indices

As we iterate through the array, we check if the current element is greater than elements represented by indices in our stack. If yes, we found the answer for those indices! We pop them and record the answer. Then we push the current index.

    for (int i = 0; i < n; i++) {
        // Pop all smaller elements - nums[i] is their answer
        while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
            int idx = stack.pop();
            result[idx] = nums[i];
        }
        stack.push(i);
    }
    
    return result;
}

This is a variation of next greater element. Instead of finding the greater value, we need to find how many days until a warmer temperature. The key difference: we return the number of days (i - idx) instead of the temperature value.

// Daily Temperatures
// How many days until warmer temperature?
int[] dailyTemperatures(int[] temperatures) {
    int n = temperatures.length;
    int[] result = new int[n];
    Deque stack = new ArrayDeque<>();

Same pattern as before: when we find a warmer day, we pop indices from the stack and calculate the day difference. The beauty is that storing indices (not values) lets us compute both the temperature comparison AND the day count.

    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty() && 
               temperatures[stack.peek()] < temperatures[i]) {
            int idx = stack.pop();
            result[idx] = i - idx;  // Days until warmer
        }
        stack.push(i);
    }
    
    return result;
}

This is a harder problem that uses a monotonic increasing stack. We want to find the largest rectangle that can be formed in a histogram. The trick is: for each bar, we calculate the maximum rectangle where that bar is the shortest.

// Largest Rectangle in Histogram
int largestRectangleArea(int[] heights) {
    int n = heights.length;
    Deque stack = new ArrayDeque<>();
    int maxArea = 0;

We iterate through bars plus one extra (with height 0 to flush remaining bars). When we see a shorter bar, we pop and calculate the area. The width extends from the current position back to the previous bar in stack (or to the beginning if stack is empty).

    for (int i = 0; i <= n; i++) {
        int h = (i == n) ? 0 : heights[i];
        
        while (!stack.isEmpty() && heights[stack.peek()] > h) {
            int height = heights[stack.pop()];
            int width = stack.isEmpty() ? i : i - stack.peek() - 1;
            maxArea = Math.max(maxArea, height * width);
        }
        stack.push(i);
    }
    
    return maxArea;
}