Este post tem o enfoque ao que é a estrutura de dado, mas, cada linguagem de programação pode representa-lo ao seu modo, alterando brevemente alguma característica.

O que define uma fila

Estrutura com dados sequenciais e ordenados

Pense numa fila de entrada de um evento, onde quem chegou primeiro entrará primeiro na festa.

A fila possui o conceito First In First Out ( FIFO ) onde o primeiro a entrar, é o primeiro a sair.

PS: A quem use o termo Laft In Laft Out ( LILO ), o que no fim das contas é a mesma coisa. Irei usar apenas o termo FIFO neste artigo.

Ela é uma estrutura linear, ainda que que os dados estejam espalhados fisicamente, eles são manipulados de modo linear, seguindo a regra FIFO.

Podemos dizer que a fila possui cabeça e final, e dizer que não existe uma regra de que deva inserir itens no final ou no início. Sendo mais comumente utilizado a forma convencional, onde se insere no final da fila.

O que precisa ser respeitado é o conceito FIFO

Operações comuns em uma fila:

PUSH​ ​: enfileirar elemento; ​

​SIZE​ ​: retornar tamanho; ​ ​

HEAD​ ​: retornar cabeça; ​ ​

POP​ ​: desenfileirar elemento; ​ ​

EMPTY​ ​: verificar se a fila está vazia.

---

Tipos comuns de fila

Filas possuem variações onde o seu conceito se amplia um pouco mais para representar melhor alguns elementos do mundo real.

Clássica

A fila clássica é o modo mais natural da estrutura, incrementando sempre na última posição e removendo a cabeça.

Circular

A fila circular possui o elemento final, mas não acaba ao passar por ele quando percorrida. A estrutura atribuir ao último elemento o endereço da cabeça da fila. E é isso que cria o efeito circular.

Esse tipo de fila precisa de meios claras para identificar qual elemento é a cabeça e qual é o fim da fila para ser manipulada corretamente.

Prioridade

A fila de prioridade altera brevemente o comportamento FIFO.

Isso porque a inclusão ou exclusão na fila não observa apenas o primeiro a entrar para sair. Ela precisa passar pela verificação intermediária de checagem da prioridade do item. De todo modo, se tivermos 2 itens de mesma prioridade, a regra FIFO estará valendo.

A checagem pode ser na entrada ou na saída dos dados, e cada uma dessas formas tem uma finalidade.

A título de exemplo, imagine esse caso.

Um sistema onde muito mais usuários consomem itens da fila do que usuário inserem itens na fila.

É mais performático organizar os itens já pela ordem de prioridade na fila no ato de inserir, de modo que na hora de consumir a fila, onde de fato se tem muitas requisições, o sistema apenas remova certo de que está na ordem de prioridade adequada.

Inverta o contexto do exemplo e fará sentido verificar a prioridade na saída.

Somado ao conceito de ordenar pela prioridade na entrada ou na saída dos dados, a fila de prioridade pode ser implementada de 2 formas.