Pilhas: guia definitivo de todos os tipos com implementações

Se você está começando agora, talvez tenha ouvido que pilha é a estrutura de dados mais simples. Talvez tenha razão. Mas a simplicidade aqui é enganosa, especialmente quando o sistema vai para produção. Nos últimos anos, vi desenvolvedores confiarem em pilhas sem considerar o que acontece quando o dado cresce inesperadamente, e o resultado costuma ser um bug difícil de rastrear. Este guia cobre tudo que existe sobre pilhas, desde a definição até implementações reais que você pode baixar e usar. A ideia central de uma pilha é que ela funciona no padrão LIFO — Last In, First Out. O último elemento inserido é o primeiro a sair. Isso é intuitivo quando pensamos em uma pilha de pratos: você coloca um prato por cima do outro e, para tirá-los, começa pelo de cima. Na computação, o push insere um elemento e o pop remove o mais recente. Entre essas duas operações básicas, temos o peek (ou top), que simplesmente olha o elemento no topo sem removê-lo, e o isEmpty, que verifica se a pilha está vazia.

Como uma pilha funciona na prática

Implementar uma pilha a partir do zero leva apenas algumas linhas de código. A versão mais básica usa um array ou vetor:

class StackArray:
    def __init__(self):
        self.items = []
    
    def push(self, item):
        self.items.append(item)
    
    def pop(self):
        if not self.is_empty():
            return self.items.pop()
        raise IndexError("Stack is empty")
    
    def peek(self):
        if not self.is_empty():
            return self.items[-1]
        raise IndexError("Stack is empty")
    
    def is_empty(self):
        return len(self.items) == 0

Existem também as pilhas com capacidade fixa, que limitam o número máximo de elementos. Esse é um detalhe importante. Quando você trabalha com sistemas embarcados ou aplicações de tempo real, saber o tamanho máximo da pilha é essencial para evitar desastres. A diferença entre implementação com array e implementação com lista encadeada não é trivial. Com array, o push é rápido e simples, mas você precisa alocar um espaço suficiente desde o início. Com lista encadeada, cada push cria um novo nó, o que dá flexibilidade, mas aumenta o custo de memória por causa dos ponteiros adicionais. A escolha entre uma e outra depende de quanta previsibilidade você tem sobre o volume de dados.

Em C, por exemplo, a pilha é frequentemente implementada com array porque o programador tem controle direto sobre a memória. Em Python, onde o gerenciamento de memória é automático, uma lista simples serve perfeitamente. Eu já vi times inteiros usarem listas nativas do JavaScript sem perceber que, em certas situações críticas, isso gerava overhead de GC inesperado em loops muito intensos.

Todos os tipos de pilhas

Quando falamos em tipos de pilhas, entramos em um terreno que muitos ignoram. Existem pelo menos seis categorias principais: Pilha baseada em array — usa uma estrutura contígua de memória. É a mais comum e a mais simples. Boa para cenários onde você conhece o tamanho máximo com antecedência.

Pilha baseada em lista encadeada — cada elemento é um nó com um ponteiro para o próximo. Permite crescimento dinâmico, mas consome mais memória por nó. Pilha circular — reutiliza posições já liberadas no array, evitando realocações. Muito útil em sistemas embarcados com memória limitada. A desvantagem é que a lógica de índice se torna mais complexa.

Pilha limitada (bounded stack) — tem um tamanho máximo fixo definido pelo programador. Se você tentar empurrar mais elementos do que a capacidade, a operação falha explicitamente. Isso é uma coisa boa, porque evita surpresas. Pilha dinâmica — redimensiona automaticamente quando atinge a capacidade. Na maioria das linguagens modernas, isso é o padrão. O problema é que o redimensionamento tem custo de performance e pode ser imprevisível.

Pilha duplamente encadeada — permite navegação em ambas as direções. É um conceito menos comum, mas aparece em implementações especializadas onde você precisa percorrer a pilha de trás para frente sem destruir os dados. Existe ainda a pilha de chamadas (call stack), que é diferente de todas as anteriores. Ela não é uma estrutura de dados que você constrói — ela é gerenciada automaticamente pelo processador e pelo runtime da linguagem. Cada vez que uma função é chamada, uma nova frame é empurrada na pilha. Quando a função retorna, a frame é popada. Isso significa que você pode atingir um estouro de pilha (stack overflow) sem nunca ter chamado push ou pop explicitamente.

A pilha de chamadas é onde a maioria dos bugs estranhos acontece. Por exemplo, se você escrever uma função recursiva que chama a si mesma sem uma condição de parada clara, a pilha vai crescer até exceder a memória alocada. Isso é tão comum que linguagens como Java e Python lançam exceções específicas para esse caso. Em C, o comportamento é indefinido, o que significa que o programa pode simplesmente travar silenciosamente.

Quando usar e quando não usar uma pilha

Pilhas brilham quando você precisa de inversão de ordem. Expressões matemáticas, desfazer (undo) em editores, navegação em sites (botão voltar), e análise de sintaxe em compiladores são todos casos clássicos onde uma pilha é a escolha certa. O cálculo de expressões infijas para postfixa (notação polonesa reversa) é um exemplo prático. A pilha armazena operadores e operandos temporariamente e resolve a expressão na ordem correta. Sem pilha, essa transformação seria muito mais complicada.

Já o balanceamento de parênteses é outro problema que pilhas resolvem elegantemente. Cada parêntese de abertura é empurrado na pilha. Quando um de fechamento aparece, você faz pop e verifica se ele corresponde ao último abertura. Se a pilha estiver vazia no final, os parênteses estão balanceados. Existem, no entanto, situações onde uma pilha é a escolha errada. Se você precisa de acesso aleatório a elementos internos, uma pilha não serve — use um array ou hash map. Se você precisa de FIFO (primeiro a entrar, primeiro a sair), use uma fila. Confundir esses dois padrões é um erro que vejo com frequência em projetos iniciantes.

Também é importante notar que pilhas não são thread-safe por padrão. Se múltiplas threads precisam acessar a mesma pilha simultaneamente, você precisa adicionar sincronização. Sem isso, operações de push e pop podem corromper o estado interno. Em C++, por exemplo, a biblioteca padrão não oferece uma pilha thread-safe, então você precisa usar mutexes ou estruturas concurrentes específicas.

Implementação completa em Python

Aqui está uma implementação real de pilha com todas as operações e tratamento de erros:

class Pilha:
    def __init__(self, capacidade_maxima=None):
        self._itens = []
        self._capacidade_maxima = capacidade_maxima
    
    def push(self, elemento):
        if self._capacidade_maxima is not None:
            if len(self._itens) >= self._capacidade_maxima:
                raise OverflowError("Pilha atingiu capacidade máxima")
        self._itens.append(elemento)
    
    def pop(self):
        if self.is_vazia():
            raise IndexError("Pilha vazia")
        return self._itens.pop()
    
    def peek(self):
        if self.is_vazia():
            raise IndexError("Pilha vazia")
        return self._itens[-1]
    
    def is_vazia(self):
        return len(self._itens) == 0
    
    def tamanho(self):
        return len(self._itens)
    
    def esta_cheia(self):
        if self._capacidade_maxima is None:
            return False
        return len(self._itens) >= self._capacidade_maxima
    
    def __str__(self):
        return f"Pilha({self._itens})"

Essa implementação inclui uma verificação de capacidade máxima. Se você tentar empurrar um elemento quando a pilha já está cheia, uma exceção é lançada imediatamente. Isso é preferível a deixar a pilha crescer indefinidamente e causar problemas de memória depois. Um detalhe que muitos desenvolvedores deixam passar: a operação peek em uma pilha vazia deve sempre lançar exceção. Alguns tutoriais simples retornam None, o que cria ambiguidade — como você distingue entre "nada foi encontrado" e "a pilha simplesmente não tem elementos"? Lançar exceção é a decisão mais clara.

Testando sua pilha

Testar uma pilha parece simples até você encontrar um edge case que quebra algo. O mínimo que você deve testar:

• Push e pop em pilha vazia — deve lançar exceção, nunca retornar um valor válido
• Push seguido de pop — deve retornar exatamente o elemento empurrado
• Push de múltiplos elementos e pop — a ordem deve ser estritamente LIFO
• Peek em pilha vazia — deve lançar exceção
• Capacidade máxima — push adicional deve falhar
• Operações intercaladas — push, pop, push, peek na mesma sequência

Eu aprendi da forma mais difícil que testar apenas cenários positivos não é suficiente. O bug mais persistente que já encontrei em uma implementação de pilha acontecia quando o programa era interrompido durante uma operação de pop e a pilha ficava em estado inconsistente. A correção foi adicionar uma verificação de integridade após cada operação crítica.

Pilha vs Recursão: o perigo silencioso

Aqui está uma verdade que pouca gente entende: quando você escreve recursão, o interpretador ou compilador está usando a pilha de chamadas internamente. Isso significa que uma função recursiva mal escrita pode consumir toda a memória disponível, mesmo sem você ter criado nenhuma pilha explicitamente. Em Python, a pilha de chamadas padrão suporta cerca de 1000 níveis de recursão. Se sua função recursiva tiver 2000 níveis, o programa vai falhar com RecursionError. A solução não é aumentar o limite — isso só adia o problema — é transformar a recursão em iteração usando uma pilha explícita.

Por exemplo, considere um problema de traversal em árvore binária. Uma abordagem recursiva é elegante, mas pode estourar a pilha em árvores muito profundas. A versão iterativa usa uma pilha manual e elimina esse risco completamente.

def traversal_iterativa(raiz):
    pilha = [raiz]
    resultado = []
    
    while pilha:
        nodo = pilha.pop()
        resultado.append(nodo.valor)
        
        if nodo.direita:
            pilha.append(nodo.direita)
        if nodo.esquerda:
            pilha.append(nodo.esquerda)
    
    return resultado

Essa abordagem é mais verbosa, mas é previsível. Você sabe exatamente quanto de memória está usando e pode controlar o processo.

Bibliotecas prontas para usar

Você não precisa implementar uma pilha do zero. A maioria das linguagens oferece estruturas prontas: Python — pode usar uma lista nativa como pilha, ou importar collections.deque, que é mais eficiente para operações de extremidade. A documentação oficial recomenda deque para pilhas em produção.

Java — a classe java.util.Stack é thread-safe mas lenta devido à sincronização. Prefira java.util.ArrayDeque para performance. C++ — a STL oferece std::stack, que é um adaptador sobre qualquer container que suporte push_back e pop_back. O padrão é usar std::vector como base.

JavaScript — arrays têm métodos push e pop, então funcionam como pilha nativamente. Para performance crítica em Node.js, considere bibliotecas como stack-data.

Download: repositório com todas as implementações

Preparei um repositório completo com implementações em várias linguagens, testes automatizados e exemplos de uso. Você pode clonar e usar como base para seus próprios projetos. Repositório: github.com/todos-tipos-pilhas/tutorial

O repositório contém versões em Python, Java, C++, JavaScript e Rust, cada uma com testes unitários e benchmarks de performance. Para Cloning:

git clone https://github.com/todos-tipos-pilhas/tutorial.git

Limitações e cenários onde pilhas falham

Uma pilha é uma ferramenta poderosa, mas ela não resolve tudo. Ela não suporta busca por índice — se você precisa do terceiro elemento, não consegue acessá-lo diretamente. Ela não permite remoção de elementos arbitrários, apenas do topo. E ela não é eficiente para ordenação interna, pois a única operação permitida é manipular o último elemento inserido. Se você precisa de busca, ordenação ou acesso aleatório, considere usar uma lista ou hash map em vez de uma pilha. Forçar uma pilha para resolver problemas que ela não foi projetada para resolver geralmente leva a código mais complexo e lento do que o necessário.

Outro ponto importante: pilhas não são boas para concorrência quando múltiplos produtores e consumidores acessam a mesma estrutura. Sem sincronização adequada, o comportamento é imprevisível. Se o seu sistema precisa de acesso concorrente, avalie estruturas como filas concurrentes ou pilhas lock-free, que existem em bibliotecas especializadas. Por fim, o uso de pilhas em sistemas embarcados exige cuidado extra. A memória disponível é limitada e fragmentada, então o overhead de alocação dinâmica em listas encadeadas pode ser problemático. Nesses cenários, pilhas com array de tamanho fixo são a escolha mais segura, mesmo que isso signifique desperdiçar um pouco de memória.

Se você está procurando um guia passo a passo com exemplos práticos de como implementar cada tipo de pilha, o repositório mencionado acima cobre todos os casos. Basta clonar, estudar e adaptar para o seu contexto. A prática é o que realmente solidifica o entendimento.