O que é uma pilha (stack) e para que é usada?

Question

Accepted Answer

Uma **pilha** (stack) é uma coleção **LIFO** (Last-In, First-Out): o último elemento colocado é o primeiro removido. Você toca apenas no **topo**.

## Operações

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

## Exemplo

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

Todas as operações são **O(1)** quando apoiadas por um array dinâmico ou lista ligada.

| Operação | Tempo |
|---|---|
| push | O(1) |
| pop | O(1) |
| peek | O(1) |

## Usos comuns

- **Function call stack** — rastreia chamadas ativas e variáveis locais.
- **Undo/redo** — push para cada ação; pop para desfazer.
- **Expression evaluation / parsing** — correspondência de parênteses, conversão de infixa para posfixa.
- **Backtracking & DFS** — lembrar onde retornar.

## Por que isso importa

A pilha modela "faça a coisa mais recente primeiro", que aparece em todos os lugares, desde recursão até botões de voltar do navegador.

Reconhecer um padrão LIFO instantaneamente sugere uma pilha, frequentemente transformando um problema confuso em algumas linhas limpas de push/pop.