Discorra sobre a estrutura de dados em pilha (Stack).
Passo 1
O que você pediu: discorrer sobre a estrutura de dados em pilha (stack).
O que eu vou cobrir (lista de tópicos que o texto dará):
O que eu vou cobrir (lista de tópicos que o texto dará):
- Definição e ideia intuitiva.
- Operações abstratas (semântica) e suas complexidades.
- Implementações comuns (vetor estático, vetor dinâmico, lista ligada) com pseudocódigo passo a passo.
- Casos de uso clássicos e exemplos práticos (com execução passo a passo em um exemplo).
- Variações úteis (pilha monotônica, pilha limitada, pilha do sistema).
- Erros e armadilhas comuns e dicas práticas para a prova/implementação.
Passo 2
Definição simples e analogia:
Uma pilha é uma estrutura de dados que guarda elementos seguindo a ordem LIFO — “Last In, First Out” (último a entrar é o primeiro a sair). Imagine um monte de pratos empilhados: para pegar um prato você só tira do topo; para colocar, você empilha em cima. Essa regra é a essência da pilha.
Uma pilha é uma estrutura de dados que guarda elementos seguindo a ordem LIFO — “Last In, First Out” (último a entrar é o primeiro a sair). Imagine um monte de pratos empilhados: para pegar um prato você só tira do topo; para colocar, você empilha em cima. Essa regra é a essência da pilha.
Passo 3
Operações abstratas (ADT) e semântica — cada linha explica o que faz e as condições importantes:
- push(x): insere o elemento
no topo da pilha. Pré-condição: pode haver restrição de capacidade; se houver, tratar overflow. Pós-condição: topo contém . - pop(): remove e retorna o elemento que estava no topo. Pré-condição: pilha não vazia (evitar underflow). Pós-condição: topo passa a ser o elemento que estava logo abaixo do removido.
- peek() ou top(): retorna (sem remover) o elemento do topo. Pré-condição: pilha não vazia.
- isEmpty(): retorna verdadeiro se a pilha estiver vazia.
- size(): retorna o número de elementos na pilha.
Complexidades usuais: push e pop têm custo constante, isto é,no caso de implementação apropriada. size e isEmpty podem ser .
Passo 4
Implementação com vetor estático (array fixo) — ideia e pseudocódigo passo a passo:
- Representação: um array
com capacidade e um índice que aponta para a posição onde será inserido o próximo elemento (ou para o elemento atual do topo, conforme convenção). Vou usar a convenção: é o índice do elemento do topo; se pilha vazia, . - Inicialização:
. - push(x):
- Verificar overflow: se
então erro (overflow). - Fazer
. - Fazer
. - Retornar sucesso.
- Verificar overflow: se
- pop():
- Verificar underflow: se
então erro (underflow). - Guardar
. - Fazer
. - Retornar
.
- Verificar underflow: se
- peek():
- Se
erro. - Retornar
.
Comentários: push/pop são. Desvantagem: capacidade fixa; precisa escolher ou tratar overflow.
- Se
Passo 5
Implementação com lista ligada (singly linked list) — passo a passo e vantagens:
- Representação: nó com campos (valor, next). Guardar ponteiro
(topo da pilha). Pilha vazia tem . - push(x):
- Alocar novo nó
com e . - Fazer
. - Retornar sucesso.
- Alocar novo nó
- pop():
- Se
então erro (underflow). - Guardar
. - Fazer
. - Retornar
.
- Se
- peek():
- Se
erro. - Retornar
.
Comentários: push/pop são. Vantagem: capacidade dinâmica, sem restrição fixa. Desvantagem: overhead de alocação de nós e uso de memória extra por ponteiros.
- Se
Passo 6
Implementação com vetor dinâmico (resizing array) e conceito de custo amortizado:
- Estratégia típica: começar com capacidade
(ou outro valor), quando o array enche, criar um novo array de capacidade e copiar os elementos; ao remover muitos elementos, pode reduzir a capacidade. - Complexidade: cópia é cara em uma operação (custo
), mas com a estratégia de dobrar a capacidade, o custo amortizado de push é .
Explicação do “amortizado” simples: embora algumas pushes custempor causa da cópia, na média sobre sequências longas de operações cada push custa constante. Então dizemos amortizado .
Passo 7
Resumo de complexidades e espaço:
- push:
(amortizado se usar vetor dinâmico). - pop:
. - peek/isEmpty/size:
. - Espaço:
para armazenar elementos.
Observação: constante escondida difere entre implementações (ponteiro extra em lista ligada, possíveis reallocs no vetor dinâmico).
Passo 8
Aplicações clássicas com exemplos passo a passo:
- Verificação de parênteses balanceados (algoritmo):
- Percorrer a expressão; para cada símbolo:
- Se símbolo é uma abertura
, , , dar push no símbolo. - Se símbolo é fechamento, verificar se pilha vazia -> erro; senão pop e checar se o tipo combina.
- Se símbolo é uma abertura
- No final, se pilha vazia então está balanceado.
Exemplo prático: expressão. - Ler ’
- Percorrer a expressão; para cada símbolo:
Passo 9
Padrões avançados e problemas de entrevista:
- Pilha monotônica: mantém elementos em ordem monótona (ex.: crescente). Útil para problemas como “next greater element” e “largest rectangle in histogram”. Ideia: ao inserir um elemento remove-se do topo enquanto o topo violar a monotonicidade. Complexidade: cada elemento entra e sai no máximo uma vez, então
. - Problemas típicos: next greater/smaller, span de preços, máxima área em histograma, implementar fila usando duas pilhas (enqueue/dequeue com duas pilhas, custo amortizado
por operação).
Passo 10
Erros, armadilhas e dicas práticas para provas/códigos:
- Sempre verificar underflow antes de pop/peek. Na prova, escreva essa verificação explicitamente.
- Cuidado com índice
ao usar array: off-by-one é comum (decida a convenção e mantenha consistente). - Se usar vetor dinâmico, explique a estratégia de redimensionamento e justifique a complexidade amortizada.
- Para memória, liste quando usar lista ligada (quando não quer tamanho fixo) e quando usar array (melhor localidade de memória e menos overhead).
- Em concorrência, pilhas simples não são seguras sem sincronização; usar estruturas atômicas ou locks.
- Implementações prontas: em muitas linguagens há a estrutura pronta (por exemplo, std::stack em C++, java.util.Deque em Java usado como pilha); saiba usar e não reinventar em prova, a menos que peçam.
Passo 11
Prova informal de corretude (invariante útil):
- Invariante da pilha: depois de k operações, os elementos na pilha, do fundo ao topo, são exatamente a sequência resultante das operações push/pop aplicadas nessa ordem. Uma prova por indução em k mostra que push e pop mantêm essa propriedade. Em provas, ao justificar algoritmos com pilha, articular essa invariante ajuda a convencer o avaliador.
Passo 12
Pequeno exercício prático (para treinar na prova) e sugestão de resolução:
- Exercício: dada a sequência de operações: push(1), push(2), pop(), push(3), peek(), pop(), pop(). Simule a pilha e escreva os valores retornados por pop/peek.
- Como resolver na prova: faça uma tabela coluna por coluna simulando o conteúdo da pilha e o valor de
. Isso evita erros.
Resposta rápida do exercício (faça você mesmo antes de olhar): as operações retornam (pop ->), (peek -> ), (pop -> ), (pop -> ) — e então a última pop seria underflow.
Passo 13
Recapitulando com motivação e incentivo (um empurrãozinho amigo):
- Pilha é um conceito simples, com operação central e forte previsibilidade: LIFO.
- Em provas, explique claramente a representação escolhida (vetor ou lista), escreva o pseudocódigo das operações e justifique complexidades (
, para espaço). - Pratique simulações manuais (empilhar/desempilhar) e dois ou três problemas clássicos (parênteses, next greater, pilha para expressão) — esses cobrem muita matéria e aparecem sempre. Você consegue!
Resposta
Pilha (stack): estrutura LIFO que suporta pelo menos as operações push (inserir), pop (remover/retornar), peek (ver topo) e consultas isEmpty/size; implementável por array estático, array dinâmico (redimensionamento) ou lista ligada, com push/pop em
(amortizado
no vetor dinâmico) e aplicações em verificação de parênteses, avaliação de expressões, chamadas de função/recursão, DFS e padrões como pilha monotônica.