Último a entrar, primeiro a sair.
push coloca um item no topo; pop remove esse mesmo topo; peek o consulta sem removê-lo. A invariante é que o topo sempre representa a decisão mais recente ainda pendente.
ABC · topo
voltar à Fase 4/ data structure · bancada 01
Stacks & Queues
Escolha a ordem certa para retirar o próximo item.
LR / 04Stack / Queue
O que muda quando a estrutura usa LIFO (último a entrar, primeiro a sair) ou FIFO (primeiro a entrar, primeiro a sair)?
Uma pilha devolve primeiro o item mais recente; uma fila devolve primeiro o item que chegou antes.
instrumentação / estado atual
passo01 / 04Empilhar
focopushO novo item entra no topo da pilha.
complexidadeO(1)caso médio
operaçãopushobservado agora
/ visualização em execução
frame 01Empilhar
STACK / LIFO
371115
QUEUE / FIFO
topo ↑ / frente →3711
/ entrada registradaA estrutura recebeu uma nova decisão.
Passo 1 · O novo item entra no topo da pilha.
Passo 1: O novo item entra no topo da pilha.
Como ler esta réguaEla não mede o tempo do seu aparelho: compara como o trabalho tende a crescer quando n, a quantidade de elementos na estrutura, aumenta.
operações
O(1) · Custo constante
A operação usa um ponto conhecido da estrutura, sem precisar percorrer todos os elementos. O número de passos não cresce com n.
Push, pop e acesso médio em uma Hash Table podem permanecer constantes quando a implementação preserva sua estrutura.comparação / duas técnicas
Compare o crescimento lado a lado
Escolha duas técnicas diferentes. As curvas usam a mesma escala visual para explicar como o custo tende a aumentar.
Comparações prontasaplique um par didático
Use este par para contrastar operações locais de extremidade com uma decomposição recursiva cujo número de movimentos cresce exponencialmente. Stacks & Queues tende a crescer mais devagar do que Towers of Hanoi quando aumentam quantidade de itens (n). Isso descreve tendência assintótica, não mede o tempo do seu aparelho.
/ raciocínio sincronizado
A mesma ideia, três leituras.
01
PILHA.push(item)02
PILHA.pop() remove o topo03
FILA.enqueue(item)04
FILA.dequeue() remove a frenteO destaque acompanha o passo atual; leia a linha destacada antes de avançar.
/ leitura técnica · estruturas lineares
A regra de saída é o contrato.
As duas estruturas guardam uma sequência; o que muda é o ponto autorizado para inserir e remover. Esse contrato simples determina o comportamento de chamadas, travessias e agendas de trabalho.
Primeiro a entrar, primeiro a sair.
enqueue acrescenta no fim; dequeue remove da frente; front consulta a próxima tarefa. A invariante é que a frente contém o item que espera há mais tempo.
A · frenteBC · fim
Operações e custo
Com uma representação apropriada, inserir, remover e consultar a extremidade correta custa O(1). O custo pode mudar se uma fila usar um array simples e remover pelo início, pois deslocar os elementos restantes passa a custar O(n).
Representação importa
Arrays redimensionáveis são compactos e rápidos no fim; listas encadeadas evitam deslocamentos; filas circulares reaproveitam posições já liberadas. A escolha deve manter as extremidades de acesso direto, não apenas “guardar itens em um array”.
Vazio e capacidade não são detalhes
Tentar pop ou dequeue numa estrutura vazia exige um caso explícito. Em capacidade fixa, também existe overflow; em capacidade dinâmica, o redimensionamento é parte do contrato de desempenho amortizado.
/ escolha pela ordem
Qual estrutura combina com a próxima decisão?
- Pilha
- Desfazer/refazer, retorno de chamadas, parsing de delimitadores e DFS: priorize a decisão mais recente.
- Fila
- Agendamento, buffers e BFS: atenda pela ordem de chegada para preservar camadas e equidade.
- Não confunda
- Uma pilha não torna qualquer busca “profunda”, e uma fila não garante prioridade por custo: para isso, use uma fila de prioridade.
CHECK / INVARIANTE
Antes e depois de cada operação
Para verificar uma implementação, descreva a ordem abstrata dos itens antes da operação e confirme que ela se preserva depois: push(x) torna x o novo topo; enqueue(x) mantém os itens anteriores na frente e põe x no fim. Esse raciocínio separa a regra da estrutura dos detalhes da memória.