O que é e como funciona uma estrutura do tipo fila?
Passo 1
A questão pede para entender o que é uma fila (queue) em estruturas de dados e como ela funciona, isto é, quais são seus princípios e operações básicas.
Passo 2
Uma fila é uma coleção ordenada de elementos que segue a política FIFO (First In, First Out), ou seja, o primeiro elemento inserido é o primeiro a ser removido.
Passo 3
As operações fundamentais de uma fila são:
• Enqueue: insere um novo elemento no final (rear) da fila.
• Dequeue: remove o elemento que está na frente (front) da fila.
• Front (ou Peek): acessa sem remover o elemento da frente.
• IsEmpty e IsFull: verificam se a fila está vazia ou cheia (no caso de capacidade limitada).
• Enqueue: insere um novo elemento no final (rear) da fila.
• Dequeue: remove o elemento que está na frente (front) da fila.
• Front (ou Peek): acessa sem remover o elemento da frente.
• IsEmpty e IsFull: verificam se a fila está vazia ou cheia (no caso de capacidade limitada).
Passo 4
Na prática, podemos implementar uma fila usando um vetor (array) circular ou uma lista ligada. No array circular, mantemos dois índices, front e rear, e usamos aritmética modular para avançá-los sem precisar deslocar elementos. Numa lista ligada, temos ponteiros para o nó da frente e o nó do final, o que torna enqueue e dequeue operações de tempo $O(1)$ naturalmente.
Passo 5
Filas aparecem em muitas situações, como gerenciamento de tarefas de impressão, processamento de requisições em servidores ou em algoritmos de busca em largura (BFS). Em todas elas, garantimos que o processamento respeite a ordem de chegada dos itens.
Resposta
Uma fila é uma estrutura de dados FIFO (First In, First Out) na qual elementos são inseridos no final (enqueue) e removidos da frente (dequeue), garantindo que o primeiro a entrar seja o primeiro a sair. Implementa-se normalmente com vetor circular ou lista ligada e suporta operações de inserção, remoção, consulta do elemento da frente e testes de vazio/cheio.