Conceito Computacional de Fila

Uma fila é uma lista, na qual as inserções são realizadas em uma das extremidades chamada “CAUDA” (TAIL), e as retiradas são realizadas da outra extremidade, chamada “CABEÇA”(HEAD) (Figura 1), em uma fila o primeiro elemento que entra, é o primeiro elemento que sai (FIFO – First In First Out) esta é a disciplina da fila.

Exemplo de declaração de uma fila estática : Fila : array [1..Max] of <Type>

Em que Type e Max são definidos pelo programador.

Ilustrando uma lista estática com no máximo 10 elementos, sua estrutura com cabeça (CAB/HEAD) e cauda (CAUDA/TAIL):
Fila (HEAD/TAIL)

Um exemplo de fila que faz parte do cotidiano de algumas pessoas é a fila de banco. Quem nunca foi ao banco e não se deparou com um fila enorme pela frente?
Essa fila de banco, utiliza o mesmo conceito de fila na computação. Veja, o primeiro a chegar na fila, é o primeiro a sair dela, se alguém chegar ao banco e quiser entrar na fila, este será o último da fila (FIFO).
Ilustração de uma fila de banco, onde a primeira da fila (mulher de azul) marca a cabeça da fila Head, e a última da fila (mulher verde), indica a cauda da fila Tail (Figura 2).
– Ilustração de uma Fila de banco

Exemplo da declaração de uma fila dinâmica :

Tipo
No = ^Elemento
Elemento = Registro
{Informações}
Prox : No
Fim

Variáveis
Cab, Cauda, P : No

Quanto a utilização de uma variável que marca o fim da fila (Cauda/Tail) : a utilização dessa variável não é obrigatória, porém quando utilizada torna o programa muito mais eficiente (rápido), sendo assim sua utilização fica a critério de cada um.

Operações para fila dinâmica :

Todas as operações com fila serão exemplificadas através de funções e procedimentos para que a codificação se torne mais versátil.

A – Criar Fila (Fila vazia)

B – Incluir na Fila

C – Verificar se a fila está vazia

D – Retirar da Fila

A – Criar fila

Procedimento Cria ( var Cab,Cauda No)
Inicio
Cab <- Nulo
Cauda <- Nulo
Fim

Este procedimento, apenas inicializa as variáveis Cab e Cauda, que irão constituir a lista, criando assim uma nova lista.

B – Incluir na fila

Função Inclui(var Cab,Cauda No; Dado Real) : lógico
Início
Aloque(P)
Se P = Nulo então
Inclui <- Falso
Senão
Inicio

P^.info <- dado
P^.prox <- nulo
Se Cab = Nulo então
Cab <- P
Senão
Cauda^.prox <- P

Cauda <- P
Inclui <- Verdadeiro
Fim
Fim

Entendendo a função: inicialmente um novo espaço na memória é alocado para o novo elemento, depois os dados são lidos, seu apontador de elementos recebe o valor Nulo, e é feita uma tomada de decisão, se não existirem elementos ele passa a ser o primeiro (CAB), senão ele vai para o fim da fila.

C – Verificar se a fila está vazia

Função Vazia (Cab No) : Lógico
Inicio
Se Cab = Nulo então
Vazia <- Verdadeiro
Senão
Vazia <- Falso
Fim

Entendendo a função : é feita uma verificação, se a variável Cab for igual a nulo, quer dizer que não existe nenhum elemento na lista, e a função retorna verdadeiro, caso contrário a lista possui algum elemento e a função retorna falso.

D – Retirar da Fila

Função Retirar (var Cab,Cauda : No) : lógico
Variáveis
Aux : No
Inicio
Se Vazia(Cab) então
Retirar <- Falso
Senão
Inicio
Retirar <- Verdadeiro
Aux <- Cab
Cab <- Cab^.prox
Disponibilize(Aux)
Se Vazia (Cab) então
Cauda <- Nulo
Fim
Fim

Entendendo a função : a função verifica se a cabeça da lista (CAB) está vazia, se estiver, a função retorna falso, para evitar erros, pois não podemos retirar um elemento sem que ele exista. Caso não seja vazia, a função retorna verdadeiro, e o primeiro da fila é apagado.

Implementando…

Programa implementando em linguagem pascal, que ilustra uma fila e suas operações básicas. Para criação dessa fila foi utilizado o conceito de listas encadeadas dinâmicas.