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á):
  • 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.

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 x no topo da pilha. Pré-condição: pode haver restrição de capacidade; se houver, tratar overflow. Pós-condição: topo contém x.
  • 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 é, \mathcal{O}(1) no caso de implementação apropriada. size e isEmpty podem ser \mathcal{O}(1).

Passo 4

Implementação com vetor estático (array fixo) — ideia e pseudocódigo passo a passo:
  • Representação: um array A[0\ldots C-1] com capacidade C e um índice top 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: top é o índice do elemento do topo; se pilha vazia, top=-1.
  • Inicialização: top \leftarrow -1.
  • push(x):
    1. Verificar overflow: se top = C-1 então erro (overflow).
    2. Fazer top \leftarrow top + 1.
    3. Fazer A[top] \leftarrow x.
    4. Retornar sucesso.
  • pop():
    1. Verificar underflow: se top = -1 então erro (underflow).
    2. Guardar v \leftarrow A[top].
    3. Fazer top \leftarrow top - 1.
    4. Retornar v.
  • peek():
    1. Se top = -1 erro.
    2. Retornar A[top].
      Comentários: push/pop são \mathcal{O}(1). Desvantagem: capacidade fixa; precisa escolher C ou tratar overflow.

Passo 5

Implementação com lista ligada (singly linked list) — passo a passo e vantagens:
  • Representação: nó com campos (valor, next). Guardar ponteiro head (topo da pilha). Pilha vazia tem head = \text{null}.
  • push(x):
    1. Alocar novo nó n com n.value \leftarrow x e n.next \leftarrow head.
    2. Fazer head \leftarrow n.
    3. Retornar sucesso.
  • pop():
    1. Se head = \text{null} então erro (underflow).
    2. Guardar v \leftarrow head.value.
    3. Fazer head \leftarrow head.next.
    4. Retornar v.
  • peek():
    1. Se head = \text{null} erro.
    2. Retornar head.value.
      Comentários: push/pop são \mathcal{O}(1). Vantagem: capacidade dinâmica, sem restrição fixa. Desvantagem: overhead de alocação de nós e uso de memória extra por ponteiros.

Passo 6

Implementação com vetor dinâmico (resizing array) e conceito de custo amortizado:
  • Estratégia típica: começar com capacidade C=1 (ou outro valor), quando o array enche, criar um novo array de capacidade 2C e copiar os C elementos; ao remover muitos elementos, pode reduzir a capacidade.
  • Complexidade: cópia é cara em uma operação (custo \mathcal{O}\text{(C)}), mas com a estratégia de dobrar a capacidade, o custo amortizado de push é \mathcal{O}(1).
    Explicação do “amortizado” simples: embora algumas pushes custem \mathcal{O}(n) por causa da cópia, na média sobre sequências longas de operações cada push custa constante. Então dizemos amortizado \mathcal{O}(1).

Passo 7

Resumo de complexidades e espaço:
  • push: \mathcal{O}(1) (amortizado \mathcal{O}(1) se usar vetor dinâmico).
  • pop: \mathcal{O}(1).
  • peek/isEmpty/size: \mathcal{O}(1).
  • Espaço: \mathcal{O}(n) para armazenar n 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:
  1. 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.
    • No final, se pilha vazia então está balanceado.
      Exemplo prático: expressão ( [ ] ).
    • Ler ’ ' -> push('\('). Pilha: ['(']. - Ler '[' -> push('['). Pilha: ['(', '[']. - Ler ']' -> pop() obtém '['; combina -> ok. Pilha: ['(']. - Ler ')' -> pop() obtém '('; combina -> ok. Pilha: []. Resultado: balanceado. 2) Avaliação de expressões (infix -> postfix usando shunting-yard) — pilha para operadores; pilha para operandos em avaliação RPN. 3) Chamadas de função/recursão — a pilha de execução do sistema é um exemplo real: cada chamada empilha um frame com variáveis locais e endereço de retorno. 4) Backtracking e desfazer (undo): estados anteriores empilhados; para voltar, pop. 5) Busca em profundidade (DFS) pode usar pilha explícita em vez de recursão.

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 \mathcal{O}(n).
  • 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 \mathcal{O}(1) 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 top 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 top. Isso evita erros.
    Resposta rápida do exercício (faça você mesmo antes de olhar): as operações retornam (pop -> 2), (peek -> 3), (pop -> 3), (pop -> 1) — 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 ( \mathcal{O}(1), \mathcal{O}(n) 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 \mathcal{O}(1) (amortizado \mathcal{O}(1) 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.

Exercícios relacionados