Questão de Algoritmos e Estrutura de Dados — Estrutura de Dados — JVL Concursos 2025
Algoritmos e Estrutura de Dados›Estrutura de Dados
Código
qg572224
Banca
JVL Concursos
Órgão
Prefeitura de Regeneração - PI
Ano
2025
Nível
Superior
Cargo
Professor de Computação
Uma fila é implementada com duas pilhas S1 e S2, enfileirando em S1 e desenfileirando a partir de S2 com transferência de S1 para S2 quando S2 está vazia. Para uma sequência com M enfileiramentos e M desenfileiramentos intercalados, assinale o custo amortizado por operação.
AΘ(log M) por operação, pois cada transferência entre pilhas executa busca binária em S2.
BΘ(1) por operação, pois cada elemento movimenta-se no máximo duas vezes entre as pilhas.
CΘ(√M) por operação, pois a movimentação total distribui-se em blocos de tamanho médio raiz de M.
DΘ(M) por operação, pois cada desenfileiramento percorre todos os elementos remanescentes.
Revelar gabarito e comentário▾
GabaritoB — Θ(1) por operação, pois cada elemento movimenta-se no máximo duas vezes entre as pilhas.
Comentário gerado por IA. É um apoio ao estudo, ancorado em fontes, mas pode conter imprecisões — confira sempre na fonte oficial (lei, súmula, edital e gabarito da banca). Encontrou um erro? Use “Reportar”.
Fila com duas pilhas: custo amortizado
Gabarito: letra B. Em uma fila implementada com duas pilhas, cada elemento é movimentado no máximo duas vezes entre as pilhas: uma vez ao ser transferido de S1 para S2 (quando S2 está vazia) e outra vez ao ser removido de S2. Como há M enfileiramentos e M desenfileiramentos intercalados, o total de operações de pilha é O(M), resultando em custo amortizado O(1) por operação.
A banca testa o conceito de análise amortizada em estruturas de dados: mesmo que uma operação isolada (desenfileirar quando S2 está vazia e toda S1 precisa ser transferida) custe Θ(n) no pior caso, esse custo elevado é raro e diluído ao longo da sequência. O custo amortizado constante deriva do fato de cada elemento ser movido um número fixo de vezes (no máximo 2 transferências entre pilhas).
Operação
Custo por operação (pior caso)
Custo amortizado
Motivo
Enfileirar (push em S1)
Θ(1)
Θ(1)
Operação simples de pilha
Desenfileirar (S2 vazia → transferir S1→S2)
Θ(n)
Θ(1)
Custo alto é raro; cada elemento é transferido no máximo 1 vez
Desenfileirar (S2 não vazia)
Θ(1)
Θ(1)
Operação simples de pilha
Total (M enfileirar + M desenfileirar)
—
Θ(1) por operação
Cada elemento é movido no máximo 2 vezes entre pilhas
1Enfileirar: push em S1
2Desenfileirar: S2 vazia?
3Sim: transfere S1→S2
4Não: pop de S2
LEVEL · soulevel.com.br
Alternativa A — ❌ Incorreta
Afirma que o custo é Θ(log M) porque cada transferência entre pilhas executa busca binária em S2. Isso é falso: as pilhas implementam operações LIFO (push/pop) em O(1), e não há busca binária. A transferência é sequencial (desempilhar de S1 e empilhar em S2).
Alternativa B — ✅ Correta ⟵ GABARITO
A análise amortizada mostra que, apesar de algumas operações serem mais caras, o custo médio por operação é Θ(1). Cada elemento é empurrado em S1 (enfileirar), depois transferido (pop de S1 + push em S2) exatamente uma vez, e finalmente removido (pop de S2). Total de 4 operações de pilha por elemento, fixo. Como temos 2M operações (M enfileirar + M desenfileirar) e cada elemento contribui O(1), o total é O(M) e a média é O(1).
Alternativa C — ❌ Incorreta
Sugere custo Θ(√M) baseado em distribuição em blocos de tamanho médio raiz de M. Não há fundamento: a transferência entre pilhas não é feita em blocos, e sim toda vez que S2 fica vazia. O número de transferências depende da intercalação. Neste caso (intercalados), cada desenfileirar encontra S2 vazia a cada duas operações? Na verdade, com enfileiramentos e desenfileiramentos intercalados, S2 ficará vazia alternadamente, mas ainda assim cada elemento é movido no máximo duas vezes.
Alternativa D — ❌ Incorreta
Afirma que cada desenfileiramento percorre todos os elementos remanescentes. Isso só acontece quando S2 está vazia e a transferência de S1 para S2 percorre todos os elementos de S1. Mas isso não ocorre em toda operação — apenas quando S2 está vazia, e cada elemento é percorrido exatamente uma vez na transferência. Portanto o custo amortizado não é Θ(M).
PEGA ESSA DICA!
Em questões de amortização, identifique o "evento caro" e veja quantas vezes ele ocorre. Nesta fila, o evento caro é a transferência completa de S1 para S2. Cada elemento é transferido apenas uma vez, então o custo total é linear no número de operações. Lembre-se: a pilha tem operações O(1), então o gargalo está na movimentação dos elementos, não no acesso.