Compreendendo Filas em C

 

Uma estrutura de dados do tipo fila funciona de forma similar a uma fila do mundo real, como, por exemplo, a fila de um banco. As filas possuem uma característica especial, onde, o primeiro elemento que entra é o primeiro elemento que sai. Isso fica evidente em uma fila de banco, em que a primeira pessoa que entra na fila para ser atendida é a primeira a sair, enquanto isso, novas pessoas entram ao final da fila. Esse processo é chamado de FIFO (First in, First out), que em português significa “o primeiro que entra, é o primeiro que sai”.

O fundamento principal da fila é que só podemos inserir um elemento no final e só podemos remover o elemento do início. Os elementos do meio ou em qualquer outra posição de memória que não seja o início e o fim, ficam inacessíveis, mesmo eles estando armazenados na memória do computador.

 

Operações fundamentais de uma fila

Independente do tipo de alocação usada na implementação de uma fila, sendo ela estática com acesso sequencial ou dinâmica com acesso encadeado, as seguintes operações são sempre possíveis:

• Criação da fila;
• Inserção de um elemento ao final da fila;
• Remoção de um elemento do início da fila;
• Acesso ao elemento do início da fila;
• Retornar o tamanho da fila;
• Verificar se a fila está vazia ou não;
• Destruição da fila.

Para implementar a fila, utilizaremos listas encadeadas. Para isso, será necessário um ponteiro para o início, que indica o primeiro elemento da fila, um ponteiro para o final, que indica o último elemento da fila e outro campo que irá armazenar o número de elementos da fila.

 

Criando uma fila

Antes de implementarmos a função de criação da fila, devemos lembrar que estamos trabalhando também com listas encadeadas, logo, temos que inicialmente definir a estrutura de No e Fila (lista) que ficarão responsáveis por armazenar as informações passadas.

A estrutura de No será definida na interface do TAD Fila.

Assim, a estrutura pode ser implementada da seguinte forma:

A função de criação da fila inicializa a lista como sendo vazia, uma possível implementação é a seguinte:

Basicamente, o que a função faz é a alocação de uma área de memória para a fila. Em seguida, a função inicializa os três campos dela, sendo eles: inicio, fim e n. Por fim, retorna o ponteiro da estrutura.

 

Inserindo um elemento na fila

Inserir um elemento em uma fila dinâmica encadeada é uma tarefa um tanto quanto simples. Basicamente, é preciso alocar o espaço para o novo elemento a ser inserido na estrutura e fazer uns ajustes em alguns ponteiros. Como se trata de uma inserção no final da fila, o elemento a ser inserido obrigatoriamente deve apontar para NULL.

Também é preciso considerar que a fila pode ou não estar vazia. Caso ela esteja vazia, precisamos fazer com que o ponteiro inicial da fila (fila->inicio) aponte para o novo elemento a ser inserido. Caso contrário, o elemento do final da fila deverá apontar para o novo elemento a ser inserido.

Abaixo será ilustrado o processo de inserção de um elemento na fila:

 

Passo 1:

Cria a fila vazia apontando para NULL.

 

Passo 2:

Aloca o espaço para o novo elemento (no) e o insere na fila vazia.

 

Passo 3:

Aloca o espaço para um novo elemento (no) e o insere no final da fila.

Inserindo mais um elemento:

Uma possível implementação para essa função é a seguinte:

 

Removendo um elemento da fila

Como já foi dito anteriormente, para remover um elemento da fila devemos remover pelo início. Inicialmente, precisamos verificar se a fila está vazia. Caso ela esteja, retornaremos uma mensagem de erro, caso contrário, daremos continuidade ao processo de remoção.

Vale ressaltar que, caso a fila esteja vazia, não necessáriamente uma mensagem de erro deve aparecer na tela. Para essa implementação usaremos uma função do tipo void, mas, ela pode ser do tipo inteiro ou até de outro tipo. Portanto, o valor de retorno passa ser relativo ao que o programador definir.

Caso a fila não esteja vazia, é necessário criar uma cópia do início em um ponteiro auxiliar (no) e, em seguida, fazemos com que o início da fila (fila->inicio) aponte para o elemento seguinte a ele. Após isso, é preciso liberar a memória associada ao antigo ponteiro de início da fila (no). Por fim, decrementamos o tamanho da fila em um.

Abaixo será ilustrado o processo de remoção de um elemento na fila:

 

Passo 1:

Fazer com que o ponteiro de início da fila (fila->inicio), aponte para o elemento seguinte a ele.

Passo 2:

Em seguida, liberamos a memória do antigo ponteiro de início da fila, neste caso, o nó cujo dado é 2 e atualizamos a quantidade de elementos da fila decrementando em uma unidade por remoção.

Esse processo pode ser executado quantas vezes forem necessárias até que a fila se encontre vazia e ambos ponteiros inicio e fim aponte para NULL.

O código abaixo é uma possível implementação para essa função:

 

Consultando o elemento do início da fila

Para recuperar o primeiro elemento é uma tarefa quase que imediata, basta fazermos:

 

Retornando o número de elementos

Para retornar o número de elementos é uma tarefa bastante simples, basta fazermos:

 

Verificando se a fila está vazia

A estrutura de fila, definida anteriormente, já possui um campo que armazena o número de elementos, o que facilita na implementação dessa função. A função que verifica se a fila está vazia pode ser dada por:

 

Liberando a fila da memória

O processo de liberar a fila é o mesmo de liberar uma lista encadeada, afinal, estamos trabalhando com listas. Para isso, a função deve liberar todos os nós da lista. Uma possível solução é a seguinte:

 

Código final do TAD Fila

Fila.c

 

Fila.h

 

Cliente.c

 

Análise de complexidade

Um aspecto importante quando manipulamos filas tem relação direta com os custos das suas operações. O custo computacional de uma fila dinâmica encadeada, para as operações de criação, inserção, remoção, consulta e para as funções auxiliares como: verificar se a fila está vazia e retornar a quantidade de elementos totais, possuem complexidade O(1). Sendo assim, a função de liberar a fila da memória é a única que possui complexidade O(n).

 

Conclusão

A estrutura de dados de fila é utilizada em inúmeras aplicações na computação. Elas também são utilizadas de forma indireta em outras aplicações ou estruturas de dados como: Busca em Largura, Grafos, Árvores e Filas de Prioridade. Filas também podem ser usadas para armazenar e controlar o fluxo de dados em um computador ou acesso aos seus recursos, como: gerenciamento de documentos enviados para impressora ou até mesmo processamento de tarefas em multiprogramação.

 

Referências

Estrutura de Dados Descomplicada - Em Linguagem C , por André Backes

Entendendo Algoritmos, por Aditya Bhargava

Obrigado pela leitura!