What is a stack and what is it used for?

Question

Accepted Answer

A **stack** is a **LIFO** (Last-In, First-Out) collection: the last element pushed is the first one popped. You only ever touch the **top**.

## Operations

```text
push(3)   push(7)   pop()->7   peek()->3
 [ 3 ]     [ 7 ]      [ 3 ]      [ 3 ]
           [ 3 ]                 top
            top
```

## Example

```python
stack = []
stack.append('a')   # push
stack.append('b')   # push
top = stack[-1]     # peek -> 'b'
stack.pop()         # pop  -> 'b'
```

All operations are **O(1)** when backed by a dynamic array or linked list.

| Operation | Time |
|---|---|
| push | O(1) |
| pop | O(1) |
| peek | O(1) |

## Common uses

- **Function call stack** — tracks active calls and local variables.
- **Undo/redo** — push each action; pop to undo.
- **Expression evaluation / parsing** — matching brackets, converting infix to postfix.
- **Backtracking & DFS** — remember where to return.

## Why it matters

The stack models "do the most recent thing first," which appears everywhere from recursion to browser back buttons.

Recognizing a LIFO pattern instantly suggests a stack, often turning a tangled problem into a few clean push/pop lines.