Stack

A stack is a linear data structure that follows LIFO (Last In, First Out) ordering — the most recently added element is the first one removed. Think of a stack of plates: you add and remove from the top only.

Core Operations

• push(x) — add an element to the top of the stack.
• pop() — remove and return the top element.
• peek() / top() — view the top element without removing it.
• isEmpty() — check whether the stack has any elements.

When to Use a Stack

Stacks are the go-to structure whenever you need to reverse order, track nested structures (parentheses, function calls, undo history), or process something in a "most-recent-first" manner. Classic use cases include expression evaluation, backtracking, and DFS traversal.

Common Techniques

• Monotonic Stack — maintain elements in increasing/decreasing order to solve "next greater/smaller element" problems in O(n).
• Matching Pairs — push opening brackets, pop and compare on closing brackets to validate balanced expressions.
• Auxiliary Stack — keep a second stack alongside the main one to track minimums/maximums in O(1), as in "Min Stack."
• Call Stack Simulation — use an explicit stack to simulate recursion iteratively (e.g., iterative tree traversal).

Time & Space Complexity

Illustration: LIFO Ordering

C++ Example: Valid Parentheses

#include <iostream>
#include <stack>
#include <string>
using namespace std;

bool isValid(string s) {
    stack<char> st;

    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') {
            st.push(c);
        } else {
            if (st.empty()) return false;
            char top = st.top();
            if ((c == ')' && top != '(') ||
                (c == ']' && top != '[') ||
                (c == '}' && top != '{')) {
                return false;
            }
            st.pop();
        }
    }
    return st.empty();
}

Python Example: Common Stack Patterns

# 1. Min Stack - retrieve minimum in O(1)
class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []

    def push(self, val):
        self.stack.append(val)
        if not self.min_stack or val <= self.min_stack[-1]:
            self.min_stack.append(val)

    def pop(self):
        val = self.stack.pop()
        if val == self.min_stack[-1]:
            self.min_stack.pop()

    def top(self):
        return self.stack[-1]

    def get_min(self):
        return self.min_stack[-1]


# 2. Next Greater Element using a monotonic stack
def next_greater_elements(nums):
    result = [-1] * len(nums)
    stack = []  # stores indices

    for i, num in enumerate(nums):
        while stack and nums[stack[-1]] < num:
            idx = stack.pop()
            result[idx] = num
        stack.append(i)

    return result


# 3. Evaluate Reverse Polish Notation
def eval_rpn(tokens):
    stack = []
    ops = {
        '+': lambda a, b: a + b,
        '-': lambda a, b: a - b,
        '*': lambda a, b: a * b,
        '/': lambda a, b: int(a / b),
    }
    for token in tokens:
        if token in ops:
            b = stack.pop()
            a = stack.pop()
            stack.append(ops[token](a, b))
        else:
            stack.append(int(token))
    return stack[-1]

Practice on LeetCode

Once you're comfortable with the concepts above, try solving these problems to reinforce your understanding:

• Easy 20. Valid Parentheses — classic matching-pairs stack usage.
• Easy 155. Min Stack — auxiliary stack to track minimums in O(1).
• Medium 739. Daily Temperatures — monotonic stack for "next greater element."
• Medium 150. Evaluate Reverse Polish Notation — stack-based expression evaluation.
• Medium 503. Next Greater Element II — monotonic stack on a circular array.