Stack

Concept

A Stack is a linear data structure that follows the LIFO (Last In, First Out) principle.

Think of a stack of dinner plates at a buffet.
When a waiter brings a clean plate, they put it on the top of the stack. When a customer takes a plate, they take it from the top of the stack. You cannot easily pull a plate from the bottom without the entire stack crashing down.

Mental Model

Core Operations

A standard Stack strictly enforces $O(1)$ time complexity for its core operations:

• push(item): Add an item to the top. ($O(1)$)
• pop(): Remove and return the top item. ($O(1)$)
• peek(): Return the top item without removing it. ($O(1)$)
• isEmpty(): Check if the stack has no items. ($O(1)$)

Note: You are intentionally not allowed to search for or remove items in the middle of a Stack.

Implementation

In JavaScript and Python, a dynamic Array actually serves as a perfect Stack right out of the box, because pushing and popping from the end of an array is Amortized $O(1)$.

// Implementing a Stack using a standard Array wrapper
class Stack<T> {
    private items: T[] = [];

    push(item: T): void {
        this.items.push(item);
    }

    pop(): T | undefined {
        // .pop() removes from the very end of the array
        return this.items.pop();
    }

    peek(): T | undefined {
        if (this.isEmpty()) return undefined;
        return this.items[this.items.length - 1];
    }

    isEmpty(): boolean {
        return this.items.length === 0;
    }
}

(If you were in C or Java, you could also implement a Stack using a Singly Linked List, where the Head acts as the Top of the stack).

Use Cases

Stacks are the go-to data structure whenever you need to process things in reverse order, or when you need to keep track of a “history” so you can backtrack.

1. The Call Stack: The CPU uses a Stack to track function calls. When funcA calls funcB, funcA is pushed onto the stack. When funcB finishes, it pops off, and the CPU resumes funcA from the top of the stack.
2. Undo/Redo: Every time you type a word, it is pushed to an Undo stack. Pressing Ctrl+Z pops the top word off.
3. Parsing Valid Parentheses: The absolute most famous Stack interview question.

Valid Parentheses

Problem: Given a string containing (, ), {, }, [, ], determine if the string is valid. Open brackets must be closed by the same type of brackets, in the correct order.
Input: "({[]})" -> Valid. Input: "([)]" -> Invalid.

function isValid(s: string): boolean {
    const stack: string[] = [];
    
    // Hash map to quickly check matching pairs
    const map = {
        ')': '(',
        '}': '{',
        ']': '['
    };

    for (let char of s) {
        if (char === '(' || char === '{' || char === '[') {
            // It's an opening bracket! Push it to the top of the stack.
            stack.push(char);
        } else {
            // It's a closing bracket! It MUST perfectly match the top of the stack.
            const lastOpen = stack.pop();
            
            // If the stack was empty, or it doesn't match the required opening bracket:
            if (lastOpen !== map[char]) {
                return false;
            }
        }
    }

    // If the stack is empty at the end, everything was perfectly closed!
    return stack.length === 0;
}

Interview Questions

Q: In JavaScript, what happens if you exceed the maximum size of the Call Stack?
A: You trigger a Stack Overflow Error (or “Maximum call stack size exceeded”). This usually happens when you write a Recursive function but forget to include the Base Case, causing the function to push itself onto the Stack infinitely until the browser or Node.js runtime forcefully kills the process to save the computer’s memory.

Q: A developer wants to evaluate a Reverse Polish Notation (RPN) mathematical string, e.g., ["2", "1", "+", "3", "*"]. How does a Stack solve this?
A: RPN is naturally solved by a Stack. You iterate through the array. If the item is a number, you push it to the stack. If the item is an operator (like +), you instantly pop() the top two numbers off the stack, add them together, and push() the resulting sum back onto the stack. When the loop finishes, the final answer will be the only number remaining in the stack.