# Stack — Data Structures & Algorithms

Source: https://www.geekswithgeeks.com/en/dsa/stack

> Last-In-First-Out: push and pop only at the top.

## LIFO

You only ever touch the top element. `push`, `pop`, and `peek` are all `O(1)`. Backed by an array (append/pop) or a linked list (insert/remove at head).

## Stack of plates

You add and take plates from the top. The first plate you put down is the last one you pick up.

## Balanced parentheses

Push openings, pop and match on closings. Empty stack at the end means balanced.

```python
def is_balanced(s):
    pairs = {')': '(', ']': '[', '}': '{'}
    st = []
    for c in s:
        if c in '([{':
            st.append(c)
        elif not st or st.pop() != pairs[c]:
            return False
    return not st
```

Output:

```
is_balanced("({[]})") -> True
is_balanced("(]")     -> False
```

## Where it hides

Function call stack, undo/redo, browser history, expression evaluation, DFS, and "next greater element" (monotonic stack).