Pilhas
Pilhas em Algoritmos e Estrutura de Dados
Pilha é uma estrutura de dados linear que segue o princípio LIFO (Last In, First Out), onde o último elemento inserido é o primeiro a ser removido.
Operações Básicas
- Push (Empilhar): Adiciona um elemento no topo da pilha.
- Pop (Desempilhar): Remove e retorna o elemento do topo da pilha.
- Top/Peek (Consultar Topo): Retorna o elemento do topo sem removê-lo.
- isEmpty (Vazia): Verifica se a pilha está vazia.
- isFull (Cheia): Em implementações estáticas, verifica se a pilha atingiu a capacidade máxima.
Implementações
- Vetor/Array: Alocação contígua com controle de topo via índice.
- Lista Encadeada: Nós dinâmicos com ponteiro para o topo.
Aplicações em Concursos
- Avaliação de expressões pós-fixadas (notação polonesa).
- Verificação de parênteses/chaves/colchetes balanceados.
- Algoritmos como DFS (Busca em Profundidade) e backtracking.
- Conversão de bases numéricas (ex: decimal para binário).
Complexidade
- Todas as operações básicas: O(1) (tempo constante).
- Espaço: O(n), onde n é o número de elementos.
Dicas para Concursos
- Memorize o LIFO e as operações básicas (Push/Pop).
- Pratique implementações em array e lista encadeada.
- Foque em problemas clássicos (ex: balanceamento, torres de Hanói).