Questão de Algoritmos e Estrutura de Dados — Estrutura de Dados — UFSCAR 2023
Algoritmos e Estrutura de Dados›Estrutura de Dados
Código
qg046183
Banca
UFSCAR
Órgão
UFSCAR
Ano
2023
Nível
Superior
Cargo
Analista de Tecnologia da Informação
Uma estrutura de dados é uma maneira organizada de armazenar e gerenciar dados em um programa ou sistema de computador. Filas e pilhas são estruturas de dados que têm diferentes princípios de operação e são úteis em contextos diferentes. Como é possível implementar uma pilha usando duas filas?
AConcatenando os elementos da primeira fila com os elementos da segunda fila para formar uma pilha.
BInserindo elementos em uma fila e removendo-os da outra fila intercaladamente.
CInserindo elementos em uma fila e removendo-os da mesma fila.
DInserindo elementos em ambas as filas simultaneamente.
EEssa implementação não é possível, uma vez que as estruturas possuem propriedades conflitantes.
Revelar gabarito e comentário▾
GabaritoB — Inserindo elementos em uma fila e removendo-os da outra fila intercaladamente.
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”.
Pilha com duas filas
Gabarito: letra B. A implementação de uma pilha (LIFO – Last In, First Out) utilizando duas filas (FIFO – First In, First Out) é um problema clássico de algoritmos e estruturas de dados. A estratégia básica consiste em manter uma fila para inserções (enqueue) e, na operação de remoção (pop), transferir todos os elementos da fila principal para a fila auxiliar, exceto o último, que é o elemento do topo da pilha; esse último é então removido e retornado, e as duas filas são trocadas de papel. Dessa forma, as operações de inserção e remoção ocorrem de forma intercalada entre as filas, exatamente como descrito na alternativa B.
A banca testa o conhecimento dos princípios de funcionamento das duas estruturas e a capacidade de adaptar uma delas para simular o comportamento da outra.
1Push: enfileira na fila principal
2Pop: transfere p/ fila auxiliar
3Pop: último é o topo (remove)
4Troca os papéis das filas
LEVEL · soulevel.com.br
Alternativa A — ❌ Incorreta
Afirma que basta concatenar os elementos das duas filas. Concatenar não produz o comportamento LIFO; a concatenação simples apenas une os elementos sem ordenação que reflita a ordem inversa exigida pela pilha.
Alternativa B — ✅ Correta ⟵ GABARITO
Inserir elementos em uma fila e, ao remover, utilizar a outra fila para reter os elementos que não são o topo (último inserido) é exatamente o mecanismo clássico de implementação de pilha com duas filas. Em termos concretos:
Push (inserir): enfileira o novo elemento na fila principal.
Pop (remover): desenfileira todos os elementos da fila principal e os enfileira na fila auxiliar, até restar apenas um; esse último é o topo da pilha e é removido e retornado; em seguida, trocam-se os nomes das filas (a auxiliar vira a principal e vice-versa).
Alternativa C — ❌ Incorreta
Inserir e remover da mesma fila produziria comportamento de fila (FIFO), não de pilha (LIFO). Uma fila única não consegue inverter a ordem de chegada.
Alternativa D — ❌ Incorreta
Inserir em ambas as filas simultaneamente não traria vantagem e ainda criaria redundância; a operação de remoção não saberia qual fila consultar para obter o último elemento inserido.
Alternativa E — ❌ Incorreta
A afirmação de que a implementação é impossível é falsa. Conforme demonstrado, é perfeitamente possível com a lógica de transferência entre as duas filas, embora a operação pop tenha custo O(n) no pior caso.
PEGA ESSA DICA!
Para fixar, pense na pilha como uma caixa onde o último objeto colocado é o primeiro a ser retirado. Com duas filas (fila de espera), você coloca objetos sempre na mesma fila; quando precisar tirar o último, remove todos os anteriores para a outra fila, pega o último e depois inverte os nomes das filas. Esse raciocínio cai com frequência em concursos e entrevistas técnicas.