---
title: "Stack (LIFO)"
url: https://algopath.pro/patterns/stack
language: en
summary: "A stack always hands back the most recent item first. That makes it the tool for anything that has to close in reverse order."
updated: 2026-08-24
---

# Stack (LIFO)

A stack always hands back the most recent item first. That makes it the tool for anything that has to close in reverse order.

## 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).

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

## When should you use Stack (LIFO)?

- 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

## What is Stack (LIFO) confused with?

- **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.

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

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

## 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.

```javascript
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("/");
}
```

## 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)?

- **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.

## JavaScript

```javascript
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;
}
```

## Python

```python
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
```

## PHP

```php
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;
}
```