Questão de Algoritmos e Estrutura de Dados — Estrutura de Dados — UFSM 2022

Estruturas de dados: Pilha, Fila e Lista

Gabarito: letra C — corretas apenas II e III. A afirmativa I é verdadeira sob interpretação teórica, mas a banca a considerou falsa (o usual é que pilha e fila são estruturas distintas); a afirmativa IV é falsa, pois o topo da pilha é o elemento mais recente, não o mais antigo.

A questão testa o conhecimento básico sobre as operações e implementações das estruturas lineares. Vamos analisar cada item.

Item I — ❌ Incorreta

"Uma Pilha pode ser implementada com uma Fila FIFO (first-in, first-out)."

Em tese, é possível implementar uma pilha usando uma ou duas filas (com custo adicional), mas a afirmativa é considerada falsa pela banca, pois a definição clássica de pilha (LIFO) e fila (FIFO) são opostas: a pilha insere e remove no mesmo extremo (topo), enquanto a fila insere em um extremo e remove no outro. A implementação direta de pilha com uma única fila não respeitaria a ordem LIFO sem manipulações extras. Portanto, a banca adota o entendimento de que não se implementa pilha com fila de forma trivial.

Item II — ✅ Correta

"Uma Pilha pode ser implementada com uma estrutura de dados Lista."

Correto. Uma pilha pode ser implementada sobre uma lista (encadeada ou sequencial). As operações de push (inserir no topo) e pop (remover do topo) são facilmente mapeadas para inserção e remoção no início ou no fim da lista, dependendo da escolha. Exemplos comuns: lista encadeada simples com inserção/remoção no início, ou vetor (array) com controle de índice de topo.

Item III — ✅ Correta

"Uma Lista permite inserção ou remoção no início ou fim da estrutura de dados."

Sim, essa é uma característica fundamental das listas lineares. Em uma lista encadeada, podemos inserir/remover no início (cabeça) e no fim (cauda). Em uma lista sequencial (vetor), também é possível inserir/remover no início (com deslocamento) e no fim (sem deslocamento). A afirmativa é genérica e verdadeira.

Item IV — ❌ Incorreta

"O topo de uma Pilha é o elemento mais antigo inserido."

Errado. O topo da pilha é o elemento mais recente inserido (último a entrar). O elemento mais antigo (primeiro a entrar) é chamado de fundo da pilha. Essa inversão é uma pegadinha clássica.

Conclusão: Apenas os itens II e III estão corretos. Portanto, a alternativa C é o gabarito.