Pilhas e Filas: Conceitos Fundamentais
Gabarito: letra E. A alternativa E descreve corretamente que a implementação iterativa da busca em profundidade (DFS) utiliza uma pilha explícita para simular a recursão. As demais alternativas contêm erros conceituais: inversão das políticas LIFO/FIFO, afirmação de que são intercambiáveis, confusão entre BFS e DFS, e complexidades equivocadas.
Alternativa A — ❌ Incorreta
Afirma que "a fila opera sob a política LIFO". Na verdade, a fila segue a política FIFO (First In, First Out). A política LIFO é da pilha. Além disso, a avaliação de expressões pós-fixadas utiliza uma pilha, não uma fila. Portanto, a alternativa está duplamente errada.
Alternativa B — ❌ Incorreta
Diz que "Pilha e fila possuem complexidade assintótica idêntica para inserção e remoção e podem ser usadas de forma intercambiável em qualquer algoritmo sem alterar o resultado". Embora ambas tenham operações O(1) para inserção/remoção (em implementações comuns), não são intercambiáveis porque alteram a ordem de processamento. Por exemplo, substituir uma pilha por uma fila em um DFS transforma o algoritmo em BFS, mudando o resultado da busca.
Alternativa C — ❌ Incorreta
Afirma que "A busca em largura (BFS) utiliza uma pilha". Isso é falso: a busca em largura utiliza uma fila para processar vértices na ordem de descoberta, garantindo que os mais próximos da origem sejam visitados primeiro. A pilha é usada na busca em profundidade (DFS).
Alternativa D — ❌ Incorreta
Diz que "As operações de inserção e remoção em uma pilha ou fila têm complexidade O(log n) quando implementadas com array ordenado, garantindo acesso eficiente a qualquer elemento por busca binária". Isso é incorreto:
Pilhas e filas têm operações O(1) (push/pop e enqueue/dequeue) em implementações típicas;
Um array ordenado não é uma implementação natural de pilha ou fila, pois a ordenação exigiria rearranjos frequentes;
A busca binária não se aplica a pilhas/filas, pois elas não suportam acesso aleatório eficiente.
Alternativa E — ✅ Correta ⟵ GABARITO
"A implementação iterativa da busca em profundidade (DFS) utiliza uma pilha explícita para simular o comportamento da recursão implícita na versão recursiva." Essa afirmação é correta: o DFS recursivo usa implicitamente a pilha de chamadas do sistema; a versão iterativa explícita usa uma pilha (push ao visitar, pop ao retroceder), reproduzindo a mesma ordem de processamento.
Característica | Pilha | Fila |
|---|
Política | LIFO | FIFO |
Operações | push/pop O(1) | enqueue/dequeue O(1) |
Uso típico | DFS, recursão, expressões pós-fixadas | BFS, processamento por ordem de chegada |
Gabarito: letra E