Visão Geral

Estrutura de Dados: Fila

Existem algumas bibliotecas prontas que podemos usar para implementar filas, mas faremos isso de maneira manual para entender seu comportamentos (se ficarem curiosos, olhem https://docs.python.org/3/library/queue.html ).

Filas são estruturas de dados em que só é possível inserir um novo elemento no final da fila e só é possível remover um elemento do início. Dizemos que filas seguem um protocolo em que o primeiro a entrar é o primeiro a sair (FIFO - First In First Out).

Em uma fila, para que o primeiro elemento a entrar (ser inserido) seja o primeiro a sair (ser removido), precisamos ser capazes de:

1. Inserir um novo elemento no final da fila.

2. Remover um elemento do início da fila.

Costumamos dizer que os elementos entram em uma fila na parte de trás e são removidos pela frente.

Exemplo de uma fila

Uma metáfora para essa terminologia é uma fila de pessoas esperando para comprar um ingresso para o cinema. As pessoas que também querem devem esperar no final da fila a sua vez e quem está na no início da fila será o primeiro a ser atendido na bilheteria do cinema.

Existem muitas outras aplicações de filas. Lojas, teatros, centros de reserva e outros serviços semelhantes que normalmente processam solicitações de clientes de acordo com o princípio FIFO. Uma fila, portanto, seria uma escolha lógica para uma estrutura de dados para lidar com chamadas para um centro de atendimento ao cliente ou uma lista de espera em um restaurante. Filas FIFO também são usadas por muitos dispositivos de computação, como uma impressora em rede ou um servidor da Web respondendo a solicitações.