Stack (LIFO)

How does Stack (LIFO) work?

A stack has two moves: push and pop. The last thing pushed is the first thing back.

An array holds one perfectly well. Push writes at the end, pop reads and shrinks.

Push whenever something opens. That may be a bracket, a directory or a pending calculation.

Pop whenever something closes. Then check that the popped item matches the thing closing it.

An empty stack at a pop means the input is broken. A non-empty stack at the end means something never closed.

Nothing below the top is ever read. That restriction is what keeps each operation O(1).

Sources: Wikipedia: Stack (abstract data type)

1. stack = []Checking the string ([]). Nothing is open yet.
2. stack = ['(']The opening round bracket is pushed.
3. stack = ['(', '[']A square bracket is pushed on top of it.
4. stack = ['(']The closing square bracket pops its match.
5. stack = []The closing round bracket pops the last one. Empty means valid.

function isValid(s) {
    const stack = [];
    const pairs = { ')': '(', ']': '[', '}': '{' };
    for (const ch of s) {
        if (ch in pairs) {
            if (stack.pop() !== pairs[ch]) return false;
        } else {
            stack.push(ch);
        }
    }
    return stack.length === 0;
}

function isValid(s: string): boolean {
    const stack: string[] = [];
    const pairs: Record<string, string> = { ')': '(', ']': '[', '}': '{' };
    for (const ch of s) {
        if (ch in pairs) {
            if (stack.pop() !== pairs[ch]) return false;
        } else {
            stack.push(ch);
        }
    }
    return stack.length === 0;
}

def is_valid(s):
    stack = []
    pairs = {')': '(', ']': '[', '}': '{'}
    for ch in s:
        if ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False
        else:
            stack.append(ch)
    return not stack

function isValid(string $s): bool {
    $stack = [];
    $pairs = [')' => '(', ']' => '[', '}' => '{'];
    foreach (str_split($s) as $ch) {
        if (isset($pairs[$ch])) {
            if (array_pop($stack) !== $pairs[$ch]) return false;
        } else {
            $stack[] = $ch;
        }
    }
    return count($stack) === 0;
}

    public static boolean isValid(String s) {
        Deque<Character> stack = new ArrayDeque<>();
        Map<Character, Character> pairs = Map.of(')', '(', ']', '[', '}', '{');
        for (char ch : s.toCharArray()) {
            if (pairs.containsKey(ch)) {
                if (stack.isEmpty() || stack.pop() != pairs.get(ch)) return false;
            } else {
                stack.push(ch);
            }
        }
        return stack.isEmpty();
    }

    public static bool IsValid(string s) {
        var stack = new Stack<char>();
        var pairs = new Dictionary<char, char> {
            [')'] = '(', [']'] = '[', ['}'] = '{',
        };
        foreach (char ch in s) {
            if (pairs.ContainsKey(ch)) {
                if (stack.Count == 0 || stack.Pop() != pairs[ch]) return false;
            } else {
                stack.Push(ch);
            }
        }
        return stack.Count == 0;
    }

A worked example of Stack (LIFO)

Simplify a file path

You get an absolute path that may contain dots and double dots. Return the shortest path that means the same thing.

A double dot goes up one directory, a single dot stays put.

Split the path on slashes and walk the parts in order.

Push a real name and pop on a double dot. Skip empty parts and single dots, then join the stack.

function simplifyPath(path) {
    const stack = [];

    for (const part of path.split("/")) {
        if (part === "" || part === ".") continue;

        if (part === "..") {
            stack.pop(); // popping an empty stack is a no-op at the root
        } else {
            stack.push(part);
        }
    }

    return "/" + stack.join("/");
}

When should you use Stack (LIFO)?

Use Stack (LIFO) when the problem statement says “valid parentheses / balanced brackets”, “match the most recent open with the next close” or “undo, backtrack to the last state, nested structure”. A solution built on it usually runs in O(n).

• •valid parentheses / balanced brackets
• •match the most recent open with the next close
• •undo, backtrack to the last state, nested structure
• •evaluate an expression with nested operators
• •process in reverse order of arrival

The signal words of every pattern sit in one table, the algorithm patterns cheat sheet.

What is Stack (LIFO) confused with?

Stack (LIFO) is most often confused with Monotonic stack, Recursion, Graph BFS / DFS and Monotonic deque (sliding window max/min).

• Monotonic stack: That keeps the stack ordered so every pop answers a question. A plain stack only remembers what is open.
• Recursion: Every recursive call already sits on a stack. Writing your own avoids the depth limit.
• Graph BFS / DFS: A queue gives breadth-first order, a stack gives depth-first. Same traversal, different container.
• Monotonic deque (sliding window max/min): A deque can be read and trimmed at both ends. A stack only ever touches the top.

Common mistakes with Stack (LIFO)

• Popping without checking for empty

  A pop on an empty stack quietly returns undefined. Test the size before you trust the value.

• Ignoring what is left at the end

  A stack that still holds items means something never closed. Check it after the loop finishes.

• Using shift instead of pop

  shift takes from the front, which makes it a queue. That reverses the meaning of the whole loop.

• Pushing values when you need positions

  Many of these problems ask how far back something was. Push the index and read the value from it.

Which interview problems use Stack (LIFO)?

Interview problems solved with Stack (LIFO) include Valid parentheses, Min stack, Evaluate reverse polish notation, Simplify path, Basic calculator, Decode string and Backspace string compare.

• Valid parentheses: Push each opening bracket, pop and match on each closing one.
• Min stack: A second stack of running minimums answers in O(1).
• Evaluate reverse polish notation: Push numbers, pop two on every operator.
• Simplify path: Push a directory, pop on a double dot.
• Basic calculator: Push the running result before an opening bracket.
• Decode string: Push the repeat count and the text before each bracket.
• Backspace string compare: Each backspace pops the last character kept.

What is the time and space complexity of Stack (LIFO)?

The target complexity of Stack (LIFO) is O(n).

Every push and pop is O(1), so n operations cost O(n). Memory is O(n) in the worst case.