Estrutura de dados pilha (stack) em Python
Nesta lição, você vai usar uma lista do Python para implementar as operações básicas de uma pilha: empilhar (push), desempilhar (pop) e consultar o topo (peek).
Introdução
O problema
O botão de desfazer, o botão Voltar do navegador e a verificação de parênteses abertos e fechados têm algo em comum: precisam lembrar itens e devolver primeiro o mais recente. A pilha (stack) é a estrutura de dados feita exatamente para isso.
Pense assim
Uma pilha é como uma pilha de pratos em um refeitório. Você coloca pratos novos em cima e tira pratos de cima. O último prato colocado é o primeiro a ser usado, e você não pode puxar um prato do meio.
stack.append("third")🍽️ Coloque um prato em cimastack.pop()⬆️ Tire o prato de cimastack[-1]👀 Olhe o prato de cima sem tirá-lostack📚 Os pratos que ainda estão na pilhaUma pilha é uma coleção LIFO (last in, first out, ou seja, o último a entrar é o primeiro a sair): itens são adicionados e removidos só no topo.
Pontos-chave
stack.append(...)empilha um item no topo, que é o fim da lista.stack.pop()remove e devolve o item do topo, aqui"third".stack[-1]lê o item do topo sem removê-lo.- Tanto
appendquantopoptrabalham no fim da lista, então são rápidos.
Quando usar?
- Históricos de desfazer e refazer.
- Verificar se os parênteses abrem e fecham direito e analisar expressões.
- Busca em profundidade e backtracking sem recursão.
Quando não é preciso
- Os itens devem sair na ordem em que chegaram: isso é uma fila.
- Você precisa pegar itens do meio ou por posição: uma lista normal ou outra estrutura serve melhor.
Veja como funciona
Faça push e pop para ver que o último item que entra é sempre o primeiro a sair.
Código de exemplo
stack = []
stack.append("first")
stack.append("second")
stack.append("third")
print("popped:", stack.pop())
print("top:", stack[-1])
print("stack:", stack)
Resultado da execução
popped: third
top: second
stack: ['first', 'second']
Explicação do código
O método append() coloca um elemento no topo da pilha, e pop() remove e retorna o elemento do topo, por isso "third" sai primeiro. stack[-1] permite consultar o topo sem removê-lo. As operações append() e pop() no fim da lista têm complexidade média O(1).
Altere os valores e execute o programa no compilador Python online CodeUtility sem instalar Python.
Exercícios práticos
Tente modificar o código seguindo as sugestões abaixo. Mudar o código e observar o resultado ajuda você a entender muito mais do que só ler.
- Teste com uma lista vazia, uma lista de um único elemento e uma lista com valores repetidos.
- Imprima o estado depois de cada passo para ver o algoritmo trabalhando.
- Meça o tempo com 100, 1.000 e 10.000 elementos e compare com outra solução.
Erros comuns
Fazer pop em uma pilha vazia
pop() em uma lista vazia lança IndexError.
item = stack.pop()
if stack:
item = stack.pop()
Usar o começo da lista como topo
insert(0, x) e pop(0) movem todos os itens, o que é lento.
stack.insert(0, item)
stack.pop(0)
stack.append(item)
stack.pop()
Terminou esta lição?
Marque como aprendida para acompanhar seu progresso.
Pratique com um desafio
Use o conteúdo desta lição para resolver um problema real. Cada desafio roda no navegador, com testes instantâneos e uma revisão por IA.
- Nearest Smaller Value to the Left For each number, find the closest earlier position containing a strictly smaller number. Médio
- Mini Stack-Language Interpreter Evaluate a small stack language. Difícil