Stack

Q: Valid parentheses — check balanced brackets

Valid parentheses — check balanced brackets - A Easy difficulty question commonly asked at Google. Study Stack patterns and Java implementation to solve this.

Q: Design a stack that supports getMin() in O(1)

Design a stack that supports getMin() in O(1) - A Medium difficulty question commonly asked at Amazon. Study Stack patterns and Java implementation to solve this.

Q: Largest rectangle in histogram

Largest rectangle in histogram - A Hard difficulty question commonly asked at Facebook. Study Stack patterns and Java implementation to solve this.

Q: Next greater element in a circular array

Next greater element in a circular array - A Medium difficulty question commonly asked at Microsoft. Study Stack patterns and Java implementation to solve this.

Q: Decode string — e.g. "3[a2[c]]" → "accaccacc"

Decode string — e.g. "3[a2[c]]" → "accaccacc" - A Medium difficulty question commonly asked at Google. Study Stack patterns and Java implementation to solve this.

Beginner

LIFO structure powering expression evaluation, backtracking, and monotonic stack problems.

Think of it this way

Think of a stack of pancakes. You always add a new pancake to the top and always eat from the top. The last pancake placed is the first one eaten — Last In, First Out. Trying to pull a pancake from the bottom would collapse the whole stack, just like accessing the middle of a stack in code is O(n).

In code, it looks like thisJava

Deque<Integer> stack = new ArrayDeque<>(); // prefer over legacy Stack class

stack.push(1);   // [1]        — add to top
stack.push(2);   // [1, 2]
stack.push(3);   // [1, 2, 3]

System.out.println(stack.pop());   // 3 — last in, first out
System.out.println(stack.peek());  // 2 — look at top without removing

Overview

A stack is a Last-In-First-Out (LIFO) data structure. The last element pushed is the first to be popped. In Java, use Deque<Integer> (ArrayDeque implementation) instead of the legacy Stack class — it is faster and not synchronized. Stacks are the foundation of recursive call simulation, expression parsing, and the monotonic stack pattern used in many "next greater element" problems.

Time & Space Complexity

Operation	Time	Space
Push	`O(1)`	`O(1)`
Pop	`O(1)`	`O(1)`
Peek / Top	`O(1)`	`O(1)`
Search	`O(n)`	`O(1)`
isEmpty	`O(1)`	`O(1)`

Java Implementation

Java

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

public class StackPatterns {

    // Valid parentheses — O(n)
    public static boolean isValid(String s) {
        Deque<Character> stack = new ArrayDeque<>();
        for (char c : s.toCharArray()) {
            if (c == '(' || c == '{' || c == '[') {
                stack.push(c);
            } else {
                if (stack.isEmpty()) return false;
                char top = stack.pop();
                if (c == ')' && top != '(') return false;
                if (c == '}' && top != '{') return false;
                if (c == ']' && top != '[') return false;
            }
        }
        return stack.isEmpty();
    }

    // Next greater element for each array element — O(n)
    public static int[] nextGreater(int[] arr) {
        int n = arr.length;
        int[] result = new int[n];
        Deque<Integer> stack = new ArrayDeque<>(); // stores indices
        for (int i = 0; i < n; i++) {
            // pop elements smaller than current — their next greater is arr[i]
            while (!stack.isEmpty() && arr[stack.peek()] < arr[i]) {
                result[stack.pop()] = arr[i];
            }
            stack.push(i);
        }
        // remaining elements have no next greater
        while (!stack.isEmpty()) result[stack.pop()] = -1;
        return result;
    }

    // Evaluate reverse Polish notation — O(n)
    public static int evalRPN(String[] tokens) {
        Deque<Integer> stack = new ArrayDeque<>();
        for (String token : tokens) {
            switch (token) {
                case "+" -> { int b = stack.pop(); stack.push(stack.pop() + b); }
                case "-" -> { int b = stack.pop(); stack.push(stack.pop() - b); }
                case "*" -> { int b = stack.pop(); stack.push(stack.pop() * b); }
                case "/" -> { int b = stack.pop(); stack.push(stack.pop() / b); }
                default  -> stack.push(Integer.parseInt(token));
            }
        }
        return stack.pop();
    }
}

Key Points to Remember

Use ArrayDeque<Integer> in Java — faster than Stack and Deque-compliant

Deque<Integer> stack = new ArrayDeque<>(); // ✓ modern, fast
Stack<Integer> old  = new Stack<>();       // ✗ legacy, synchronized, slow

Monotonic stack solves "next greater/smaller element" problems in O(n)

// Pop elements smaller than current — their answer is arr[i]
while (!stack.isEmpty() && arr[stack.peek()] < arr[i])
    result[stack.pop()] = arr[i];
stack.push(i);

Valid parentheses checking is the classic stack interview question

if (c == '(') stack.push(c);
else if (stack.isEmpty() || stack.pop() != '(') return false;

Stack can simulate recursion iteratively — push children instead of calling recursively

Two stacks can implement a queue (interview classic)

// Stack 1: inbox (push here)   Stack 2: outbox (pop from here)
// When outbox is empty, pour all of inbox into outbox

Interview Questions

Valid parentheses — check balanced brackets

EasyGoogleSolve it

Design a stack that supports getMin() in O(1)

MediumAmazonSolve it

Largest rectangle in histogram

HardFacebookSolve it

Next greater element in a circular array

MediumMicrosoftSolve it

Decode string — e.g. "3[a2[c]]" → "accaccacc"

MediumGoogleSolve it

Ask Aria about Stack

Your personal AI tutor — ask anything about this concept

Linked List

Queue