Stack (pilha)
Última atualização
Uma pilha é uma coleção com exatamente uma extremidade aberta. Você adiciona um valor empilhando-o no topo, e remove um desempilhando esse mesmo topo, então o último valor a entrar é sempre o primeiro a sair. É isso que LIFO significa, e essa é a regra inteira: não há como alcançar o meio sem antes remover o que está acima. Pressione reproduzir acima e veja a coluna crescer a cada push e diminuir pela mesma extremidade a cada pop.
A restrição é justamente o ponto. Como as duas operações tocam apenas o topo, cada uma é O(1) por mais alta que a pilha fique, e é essa previsibilidade que coloca as pilhas embaixo de boa parte da computação: a pilha de chamadas que executa a recursividade, o histórico de desfazer de um editor, o casamento de parênteses em um analisador sintático, e a pilha explícita que transforma uma busca em profundidade recursiva em um laço. Troque a extremidade de remoção e o que você tem é uma Queue (fila).
Complexidade de tempo e espaço
Para a pilha padrão apoiada em um array ou em uma lista ligada:
| Operação | Complexidade | Notas |
|---|---|---|
| Push | O(1) | O(1) amortizado em um array dinâmico, que de vez em quando é redimensionado. |
| Pop | O(1) | Sempre o elemento do topo, então nada precisa ser deslocado. |
| Peek (topo) | O(1) | Lê o topo sem removê-lo. |
| Buscar | O(n) | Não é para isso que serve uma pilha: você precisa desempilhar até chegar lá. |
| Espaço | O(n) | Um espaço para cada valor armazenado. |
Passo a passo
| Passo | O que acontece |
|---|---|
| 1 | A pilha começa vazia, com o topo não apontando para nada. |
| 2 | Push escreve o valor na posição do topo e sobe o topo em uma posição. |
| 3 | Cada push seguinte cai logo acima do valor anterior. |
| 4 | Pop lê o valor do topo e depois desce o topo em uma posição. |
| 5 | O valor que volta é sempre o que foi empilhado mais recentemente. |
| 6 | Desempilhar de uma pilha vazia é um erro, chamado stack underflow, então o código real verifica is_empty() antes. |
Exemplo resolvido
Empilhando 3, 7, 5 e depois esvaziando a pilha:
| Operação | Pilha (da base ao topo) | Retorna |
|---|---|---|
push(3) | [3] | nada |
push(7) | [3, 7] | nada |
push(5) | [3, 7, 5] | nada |
pop() | [3, 7] | 5, o valor mais novo |
pop() | [3] | 7 |
pop() | [] | 3, o valor mais antigo, por último |
Quando usar uma pilha
| Use quando | Evite quando |
|---|---|
| Você precisa do item mais recente de volta primeiro: desfazer, botões de voltar, casamento de parênteses | Você precisa do item mais antigo primeiro, que é uma Queue (fila) |
| Você está transformando um algoritmo recursivo em um iterativo | Você precisa buscar ou indexar no meio dos dados |
| Você está analisando estruturas aninhadas como expressões, JSON ou HTML | Muitos leitores precisam de acesso arbitrário, onde um array ou um mapa se encaixa melhor |
Você quer inserção e remoção O(1) garantidas, sem rebalanceamento | Você precisa manter os dados em ordem, o que um heap ou uma árvore te dá |
Código de Stack
Uma implementação limpa e executável de Stack em Python, JavaScript, Java, C++, C. Escolha uma linguagem, copie o código ou abra-o já carregado no Playground da Coddy.
Código de Stack em Python
Python
1stack = []2
3# Push three values onto the top4for value in [3, 7, 5]:5 stack.append(value)6 print(f"push {value} -> {stack}")7
8# Pop them back off: last in, first out9while stack:10 value = stack.pop()11 print(f"pop {value} -> {stack}")12
13print("empty:", len(stack) == 0)Código de Stack em JavaScript
JavaScript
1const stack = [];2
3// Push three values onto the top4for (const value of [3, 7, 5]) {5 stack.push(value);6 console.log(`push ${value} ->`, stack);7}8
9// Pop them back off: last in, first out10while (stack.length > 0) {11 const value = stack.pop();12 console.log(`pop ${value} ->`, stack);13}14
15console.log('empty:', stack.length === 0);Código de Stack em Java
Java
1import java.util.ArrayDeque;2import java.util.Deque;3
4public class Main {5 public static void main(String[] args) {6 Deque<Integer> stack = new ArrayDeque<>();7
8 // Push three values onto the top9 for (int value : new int[] {3, 7, 5}) {10 stack.push(value);11 System.out.println("push " + value + " -> " + stack);12 }13
14 // Pop them back off: last in, first out15 while (!stack.isEmpty()) {16 int value = stack.pop();17 System.out.println("pop " + value + " -> " + stack);18 }19
20 System.out.println("empty: " + stack.isEmpty());21 }22}Código de Stack em C++
C++
1#include <iostream>2#include <stack>3
4int main() {5 std::stack<int> stack;6
7 // Push three values onto the top8 for (int value : {3, 7, 5}) {9 stack.push(value);10 std::cout << "push " << value << " -> size " << stack.size() << "\n";11 }12
13 // Pop them back off: last in, first out14 while (!stack.empty()) {15 int value = stack.top();16 stack.pop();17 std::cout << "pop " << value << " -> size " << stack.size() << "\n";18 }19
20 std::cout << "empty: " << std::boolalpha << stack.empty() << "\n";21 return 0;22}Código de Stack em C
C
1#include <stdio.h>2
3#define CAP 164
5int stack[CAP];6int top = 0; /* index of the next free slot */7
8int main(void) {9 int values[3] = {3, 7, 5};10
11 /* Push three values onto the top */12 for (int i = 0; i < 3; i++) {13 stack[top++] = values[i];14 printf("push %d -> size %d\n", values[i], top);15 }16
17 /* Pop them back off: last in, first out */18 while (top > 0) {19 int value = stack[--top];20 printf("pop %d -> size %d\n", value, top);21 }22
23 printf("empty: %d\n", top == 0);24 return 0;25}Perguntas frequentes sobre pilhas
O que significa LIFO?
Último a entrar, primeiro a sair: o valor empilhado mais recentemente é o primeiro a ser desempilhado. Uma pilha de pratos é a imagem de sempre: você pega o prato que acabou de colocar, não o do fundo. Uma Queue (fila) segue a disciplina oposta, FIFO.
Qual é a diferença entre uma pilha e uma fila?
Apenas a extremidade de onde você remove. As duas adicionam por uma extremidade em
O(1); uma pilha remove por essa mesma extremidade (LIFO), uma fila remove pela outra (FIFO). Todo o resto, inclusive a tabela de complexidade acima, é idêntico.Quais são as principais operações de uma pilha?
push adiciona um valor no topo, pop remove e retorna o valor do topo, peek (às vezes top) lê o topo sem removê-lo, e is_empty informa se ainda sobrou algo. As quatro são O(1).O que é um stack overflow?
É empilhar em uma pilha que não tem mais espaço. O caso famoso é a pilha de chamadas: cada chamada de função empilha um quadro, então uma recursividade que nunca alcança seu caso base continua empilhando até bater no limite de pilha do ambiente de execução e o programa quebra. O erro espelhado, desempilhar de uma pilha vazia, é o stack underflow.
Como uma pilha é implementada?
Duas formas comuns. Um array dinâmico empilha e desempilha no fim, o que é
O(1) amortizado e amigável ao cache: list do Python e ArrayDeque do Java funcionam assim. Uma lista encadeada empilha e desempilha na cabeça, O(1) no pior caso e sem redimensionamento, mas custa um ponteiro por elemento. std::stack do C++ é um adaptador que usa std::deque por padrão, um array segmentado, e aceita outro contêiner se você indicar.Onde as pilhas são usadas em programas reais?
A pilha de chamadas para chamadas de função e recursividade, o histórico de desfazer e refazer, a navegação para trás do navegador, a avaliação de expressões e o casamento de parênteses em analisadores sintáticos, e a pilha explícita que converte uma busca em profundidade recursiva em um laço iterativo.
Recursos relacionados
Mais visualizações
