Pilha

Conceito

Pilha é a disciplina LIFO: o último a entrar é o primeiro a sair. Duas operações essenciais — push e pop — e opcionalmente peek (olhar o topo sem remover).

A pilha não é uma estrutura de dados que você escolhe por performance; é uma disciplina de acesso que você escolhe porque o problema tem essa forma. Problemas naturalmente LIFO:

• aninhamento — parênteses, tags, escopos, blocos
• "voltar ao contexto anterior" — chamadas de função, navegação, undo
• backtracking — tentar um caminho, desfazer, tentar outro
• DFS iterativo — a pilha explícita substitui a recursão

Onde já existe uma pilha no seu programa sem você declarar: a 6. Pilha de Chamadas. Toda linguagem com funções tem uma, e é ela que torna recursão possível — e que estoura.

Array ou lista ligada por baixo? Array, quase sempre: push/pop no fim são O(1) amortizado e a localidade é perfeita, porque você sempre toca a mesma ponta. Lista ligada só se você precisar de O(1) de pior caso garantido (sem o pico da realocação) ou não puder realocar.

Parênteses balanceados é o exemplo canônico porque expõe exatamente o que a pilha modela: cada abertura empilha uma obrigação, cada fechamento tem que casar com a obrigação mais recente.

Em Go

Não existe tipo Stack na stdlib, e não é omissão — o slice já é uma pilha:

var pilha []int
pilha = append(pilha, v)                 // push, O(1) amortizado
topo := pilha[len(pilha)-1]              // peek
pilha = pilha[:len(pilha)-1]             // pop

var zero T
pilha[len(pilha)-1] = zero
pilha = pilha[:len(pilha)-1]

Em Go 1.21+ existe clear(s) para zerar um slice inteiro, útil quando você reusa o array com s = s[:0].

Para pilha genérica reutilizável, generics resolvem em 15 linhas — e o tipo fica seguro, ao contrário de container/list.

Respostas às perguntas-guia

1. Que problemas são naturalmente LIFO?

Conceito: tudo que envolve aninhamento ou retorno ao contexto anterior: parênteses, escopos, chamadas, undo, backtracking, DFS.

Em Go: o caso mais visível é defer — Go executa os defer de uma função em ordem LIFO, porque é uma pilha. É a razão de defer mu.Unlock() funcionar corretamente com locks aninhados.

2. Que estrutura você usaria por baixo: array ou lista ligada? Por quê?

Conceito: array. Você toca sempre a mesma ponta, então a localidade é ótima e o custo é O(1) amortizado. Lista ligada só para O(1) de pior caso garantido.

Em Go: slice, sem hesitar — com o cuidado de zerar no pop se o elemento carrega ponteiro.

3. Onde já existe uma pilha no seu programa sem você declarar?

Conceito: a pilha de chamadas. Cada chamada empilha um frame; cada retorno desempilha.

Em Go: a pilha de chamadas da goroutine (2 KB inicial, crescendo por cópia) e a pilha de defer de cada função. Um stack trace é literalmente essa pilha impressa.

4. Como validar parênteses balanceados com ela?

Conceito: empilha cada abertura; a cada fechamento, verifica se casa com o topo e desempilha. No fim, a pilha precisa estar vazia. Dois modos de falha: fechamento sem par (topo errado ou pilha vazia) e abertura sem par (pilha não vazia no fim).

Em Go: ver o exemplo abaixo — 15 linhas com um slice.

Trade-offs

Do conceito:

• LIFO é a disciplina mais barata que existe (uma ponta, um índice) e serve apenas aos problemas que têm essa forma. Forçar um problema FIFO numa pilha inverte a ordem.
• Pilha explícita vs recursão: a explícita não estoura o stack do runtime e permite controlar o limite; a recursiva é mais legível. Ver 5. Recursão.

Em Go:

• Slice como pilha custa zero abstração e cobra atenção no pop (vazamento por referência retida).
• defer te dá comportamento de pilha de graça, com custo por defer já muito baixo desde o Go 1.14 (open-coded defers).

Exemplo prático

package main

import "fmt"

func balanceado(s string) bool {
	par := map[rune]rune{')': '(', ']': '[', '}': '{'}
	var pilha []rune

	for _, c := range s {
		switch c {
		case '(', '[', '{':
			pilha = append(pilha, c) // push: empilha a obrigação
		case ')', ']', '}':
			if len(pilha) == 0 || pilha[len(pilha)-1] != par[c] {
				return false // fechamento sem par, ou par errado
			}
			pilha = pilha[:len(pilha)-1] // pop
		}
	}
	return len(pilha) == 0 // sobrou abertura sem fechar?
}

// Pilha genérica, com o pop CORRETO (zera antes de encurtar)
type Pilha[T any] struct{ itens []T }

func (p *Pilha[T]) Push(v T) { p.itens = append(p.itens, v) }

func (p *Pilha[T]) Pop() (T, bool) {
	var zero T
	if len(p.itens) == 0 {
		return zero, false
	}
	i := len(p.itens) - 1
	v := p.itens[i]
	p.itens[i] = zero // <- sem isto, o GC nao libera o valor apontado
	p.itens = p.itens[:i]
	return v, true
}

func main() {
	for _, s := range []string{"({[]})", "(]", "((", ""} {
		fmt.Printf("%-8q %v\n", s, balanceado(s))
	}

	var p Pilha[string]
	p.Push("a")
	p.Push("b")
	v, _ := p.Pop()
	fmt.Println("pop:", v) // b — LIFO
}

Relacionado

• 5. Fila — a disciplina oposta
• 6. Pilha de Chamadas — semana 3, a pilha que o runtime mantém
• 5. Recursão — semana 3, recursão é a pilha implícita
• 2. Array — o que fica por baixo

Parte de Semana 02 - Estruturas de Dados I · 00 - MOC Fundamentos de Programação