Pilhas e filas

Pilha (LIFO)

Só se mexe no topo: push coloca, pop tira. Está em todo lugar: a pilha de chamadas do programa, o "desfazer" do editor, o botão voltar, a navegação entre telas e a checagem de parênteses balanceados (cada fecha precisa casar com o último abre).

Fila (FIFO)

Entra no fim, sai pela frente. É a fila de tarefas, de mensagens (Kafka, SQS), de impressão — e a estrutura que faz a busca em largura visitar um grafo por níveis.

Qual classe usar

Em Kotlin, ArrayDeque serve para as duas (addLast/removeLast = pilha; addLast/removeFirst = fila), tudo O(1). Evite removeAt(0) num MutableList: desloca o array inteiro. Em Swift, use Deque do pacote Swift Collections; em TypeScript, shift() também é O(n) — para filas grandes, use um índice de leitura.

fun balanceado(s: String): Boolean {
    val pares = mapOf(')' to '(', ']' to '[', '}' to '{')
    val pilha = ArrayDeque<Char>()
    for (c in s) when (c) {
        '(', '[', '{' -> pilha.addLast(c)
        ')', ']', '}' -> if (pilha.removeLastOrNull() != pares[c]) return false
    }
    return pilha.isEmpty() // sobrou abre sem fecha?
}