Filas: conceito e implementação em C

No meu último post sobre estrutura de dados em C, eu mostrei como implementar o tipo abstrato de dados pilha utilizando listas encadeadas. No post de hoje, vou mostrar o que são filas, pra que elas servem e como implementá-las em C. Se você não está familiarizado com o conceito de listas encadeadas, recomendo a leitura do meu post sobre o assunto (esse aqui). Então, vamos lá.

O que é uma fila?

Uma fila é uma sequência de elementos que permite duas operações: inserção e remoção de elementos. Essas operações geralmente são denominadas de enqueue/dequeue, put/get ou, em português, enfileirar e desenfileirar. A operação dequeue, ou get, deve ao mesmo tempo remover e recuperar (retornar) o valor de um elemento.

O que torna a fila algo especial é o modo como os elementos são inseridos ou removidos. Assim como numa fila de lotérica, o primeiro a entrar na fila é o primeiro a sair (se não levarmos em consideração a existência dos fura-fila, no caso da lotérica). Em Teoria das Filas, esse comportamento é designado de disciplina FIFO (first in, first out, ou, em português, primeiro a entrar, primeiro a sair).

Qual a diferença entre pilha e fila?

No post sobre pilhas, eu comentei que esse tipo de dados segue a disciplina LIFO (Last in, first out). Para deixar ainda mais claro, podemos ver a diferença entre pilha e fila da seguinte forma: na pilha, os elementos são removidos e inseridos sempre na mesma “ponta” da sequência. Enquanto que na fila, o elemento entra por uma “ponta” e sai pela outra.

Ou seja, em nível de implementação, se decidimos que os elementos de uma pilha serão inseridos no início da sequência, então eles deverão ser removidos também do início da sequência. Se resolvermos implementar a pilha inserindo elementos ao fim da sequência, então eles deverão ser removidos do fim da sequência. Ou seja, sempre lidamos com a mesma “ponta” da sequência.

Ao implementarmos uma fila, por outro lado, se decidimos que os elementos são inseridos no início dela, então eles devem ser removidos do final (a outra ponta). Por outro lado, se decidimos que os elementos são inseridos ao final, então eles devem ser removidos do início. Ou seja, trabalhamos com as duas “pontas” da fila. Tradicionalmente, na implementação de filas, os elementos são adicionados ao final e removidos do início, provavelmente para manter a analogia com as filas da vida real. Mas no fim das contas, fim e início de uma sequência acabam sendo uma questão de perspectiva.

Pra que serve uma fila?

Assim como as pilhas, as filas também são amplamente utilizadas em computação. Principalmente para comunicação entre processos ou threads de um mesmo processo através de filas de mensagem, que permitem que um processo ou thread envie uma sequência de mensagens que poderão ser consumidas por um outro processo ou thread, respeitando a ordem de envio.

Também é utilizada para a implementação do algoritmo de busca em grafos chamado de algoritmo de busca em largura (ou breadth-first search), do qual eu trato nesse post, que garante encontrar o menor caminho entre dois vértices de um grafo não-valorado, caso este exista.

Fila de prioridade

Existe um tipo especial de fila que precisa ser mencionado: a fila de prioridade. Esse tipo de fila não segue nem a disciplina FIFO nem a LIFO. Ao invés disso, cada elemento possui um valor que corresponde ao seu “grau de prioridade” e a operação de desenfileirar remove o elemento com a maior prioridade. Esse tipo de fila também tem muitas aplicações práticas, como em algoritmos de escalonamento de processos e de busca em grafos.

Como implementar uma fila em C com listas encadeadas

Se você leu o post sobre listas encadeadas do blog deve imaginar que para implementar uma fila, basta utilizarmos a mesma estrutura do tipo lista_no, a função para inserir um elemento no final da lista e a função que remove um elemento do início (modificada para retornar o valor desse elemento).

Embora isso seja possível, essa não é uma estratégia recomendável, pois nosso código para adicionar um elemento ao final da lista tinha que percorrer toda a lista até chegar ao final, para então adicionar o elemento. Isso significa que numa lista de tamanho N, um laço de repetição seria executado N vezes sempre que um elemento fosse adicionado na fila. Isso pode ser muito custoso em nível de processamento.

Por isso, diferente do que fizemos com listas e pilhas, para implementar uma fila, faremos uso de duas estruturas diferentes:

typedef struct fila_no{
	struct fila_no * prox;
	int dado;
}fila_no;

typedef struct fila_t{
	fila_no * frente;
	fila_no * final;
}fila_t;

fila_no é uma estrutura exatamente igual à lista_no e à pilha_no, com as quais trabalhamos nos outros posts, exceto pelo nome. Ela armazena um ponteiro para outra struct do tipo fila_no, e um valor inteiro, que é o dado a ser armazenado no elemento. A fila é formada fazendo com que cada elemento da sequência aponte para o próximo.

A novidade aqui é a estrutura fila_t. Ela irá armazenar dois ponteiros do tipo fila_no (apelido de struct fila_no, que produzimos utilizando typedef). Um ponteiro irá apontar para o primeiro elemento da fila (o elemento da frente) e outro, para o último elemento da fila (o elemento do final da fila).

Com um ponteiro apontando para cada ponta da fila, podemos inserir e remover itens de nossa fila em tempo constante. Já que não precisamos iterar sobre a fila para chegar ao último elemento!

Nossa estrutura fila_t funciona mais ou menos como a “cabeça” da estrutura de fila. Ele representa a fila propriamente dita, enquanto que fila_no representa cada elemento individualmente. Isso vai ficar mais claro daqui a pouco.

Criação da fila

Para criar uma fila, alocamos o espaço para a estrutura do tipo fila_t, e inicializamos seus dois ponteiros para NULL. Lembrando que para usar malloc() e a macro NULL, precisamos incluir o cabeçalho <stdio.h>.

fila_t * fila_cria(void){
	/*Inicializa nosso novo objeto do tipo fila_t *  */
	fila_t * nova_fila = malloc(sizeof(fila_t));
	nova_fila -> frente = NULL;
	nova_fila -> final = NULL;
    return nova_fila;
}

Esse valor retornado por fila_cria() (um ponteiro para fila_t) será utilizado para se referir à nossa fila. Então precisamos armazená-lo em uma variável e utilizá-lo como parâmetro para nossas outras funções. Na nossa função principal, inicializaremos uma nova fila mais ou menos assim:

fila_t * minha_fila = fila_cria();
fila_put(minha_fila, 10);

Criação a função put() da fila

Agora vamos implementar a nossa função de put(). Ela deve pegar um valor e inseri-lo ao final da fila:

void fila_put(fila_t * fila, int val){
	/*Cria o novo nó*/
	fila_no * novo_no = malloc(sizeof(fila_no));
	novo_no -> dado = val;
	novo_no -> prox = NULL;
	/*--------------*/
	
	/*Se a fila estiver vazia,
	a frente e o final apontam para o mesmo novo elemento*/
	if (fila -> frente == NULL){
		fila -> frente = fila -> final = novo_no;
	}
	/*Caso contrário...*/
	
	else{
		/*O que era o último elemento, vai
		apontar para o novo último elemento*/
		fila -> final -> prox = novo_no;
		
		/*O novo elemento vai ser o final da fila*/
		fila -> final = novo_no;
	}	

}

Depois de criar um novo nó para representar o novo elemento da fila, precisamos inseri-lo ao final da fila. Caso a fila esteja vazia (o que é verificado testando se a frente da fila está vazia), então fazemos a frente e o final apontarem para o mesmo novo nó. O que é natural, já que quando uma fila tem apenas uma pessoa, ela é a primeira e última da fila ao mesmo tempo.

Caso contrário, pegamos o elemento que era o último da fila e o fazemos apontar para o novo elemento. E então fazemos o ponteiro final, da estrutura de fila, apontar para o novo elemento também.

Precisamos que cada elemento aponte para o próximo da fila, porque na função get(), para remover elementos, alteraremos o ponteiro frente da fila baseado no endereço contido em prox do elemento removido.

Imagine que a fila sabe quem está na frente e quem está no final, mas depois que um elemento é removido, é esse elemento que diz quem deve ser o próximo a ser “atendido”.

Criação a função get() da fila

Agora, precisamos apenas implementar nossa função get():

int fila_get(fila_t * fila){
	/*Prossiga apenas se realmente tiver objetos na fila*/
	if (fila -> frente){


		/*Armazena o dado do objeto a ser removido*/
		int val = fila -> frente -> dado;
		
		/*Precisamos armazenar o endereço do primeiro elemento 
		porque vamos mudar o ponteiro fila -> frente, mas
		precisamos liberar o primeio elemento com free() */
		fila_no * temp = fila -> frente;
		
		/*A fila anda...*/				
		fila -> frente = fila -> frente -> prox;
		free(temp);
		return val;
	}
	/*Avise se o ponteiro for NULL*/
	return -1;
}

Nosso get() deve basicamente consultar o elemento que está na frente da fila (o elemento para o qual fila -> frente aponta). Se for NULL, a fila está vazia, e a função retorna -1*.

*: isso só vai funcionar se estabelecemos que nossa fila deve armazenar apenas valores positivos. Caso contrário, um valor de retorno de -1 pode ser interpretado como se -1 fosse o valor do elemento na frente da fila. Para fins didáticos, vamos apenas supor que estamos trabalhando com números positivos (se isso realmente for um problema, você pode dar uma olhada nesse post aqui para ter um insight sobre como resolvê-lo).

Caso contrário, armazenamos o valor do elemento da frente da fila e fazemos fila -> frente apontar para o segundo elemento da fila, cujo endereço está contido em fila -> frente -> prox.

Finalmente, liberamos a memória do nó que estava na frente da fila e retornamos seu valor.

Pela imagem, você pode perceber que quando a fila esvazia, o ponteiro fila -> final passa a apontar para um endereço inválido, já que liberamos a memória do último elemento da fila, para o qual ele apontava. Isso não é realmente um problema, já que só acontece quando fila -> frente passa a apontar para NULL, e em nossa função fila_put(), nos certificamos de que quando fila -> frente == NULL, fila -> final passa a apontar para o elemento da fila recém criado. Então, na prática, nunca tentamos acessar esse endereço inválido.

Destruição da fila

Agora precisamos criar um mecanismo para destruir a fila. Para isso, devemos iterar sobre a fila, liberando a memória de cada um de seus elementos, e então liberar a estrutura da fila em si, fazendo o ponteiro na função principal que apontava para o endereço de memória dessa estrutura passar a apontar para NULL.

void fila_destroi(fila_t * * fila){

  /*Primeiro destroi cada elemento da fila*/
  fila_no * aux = (* fila) -> frente; //variável auxiliar
  fila_no * temp;          //variável temporária
  while (aux){            //Verdadeiro enquanto aux for diferente de NULL
    temp = aux;           //armazena o nó na frente da fila
    aux = aux -> prox;    //caminha para o próximo item da fila
    free(temp);           //libera a memória do nó que estava no topo
  }
  /*Depois destroi a 'cabeça' da fila*/
  free(* fila);
  * fila = NULL;         //a variável que armazenava a pilha agora armazena NULL
}

Para conseguir alterar o valor da variável que armazena a fila na função principal, utilizaremos ponteiros duplos. Ou seja, para utilizar essa função, devemos passar para essa função o endereço de uma variável que armazena o endereço de um fila_t, mais ou menos assim:

fila_destroi(&fila);

Se isso for confuso pra você, recomendo dar uma lida nessa seção do post sobre listas sem cabeça.

Imprimindo a fila

Com nossas funções para criar e destruir filas e inserir e remover elementos da fila, já temos uma fila completamente funcional. Mas para testá-la é bom termos uma função que imprima nossa fila na tela. Para isso, vamos reciclar a função que utilizamos para imprimir uma lista encadeada no post sobre o assunto:

void fila_imprime(fila_t * fila){
	/*Se a fila existir...*/
	if (fila){
		fila_no * aux = fila -> frente;
		while(aux){
                printf("[%d]->", aux -> dado);                
                aux = aux -> prox;
        }
    }
    printf("NULL\n");
}

A função apenas itera sobre cada elemento da fila até achar NULL, imprimindo o valor de cada elemento que encontrar até lá. Lembre-se de adicionar o cabeçalho stdio.h para poder utilizar printf().

Testando a fila

Agora sim, podemos fazer um programinha de teste para testar nossa fila (que iremos adaptar do programa apresentado no post sobre pilhas).

int main(void){
	/*Um array para armazenar os valores da fila*/
	int seq[] = {5, 6, 7, 8, 9, 10, 11};

	/*O número de membros de um array é igual 
	 * ao tamanho do array em bytes dividido
	 * pelo tamanho do membro em bytes*/
	int arrsz = sizeof(seq)/sizeof(seq[0]);
	
	printf("Tamanho de seq = %d\n", arrsz);
	
	/*Cria a fila*/
	fila_t * fila = fila_cria();
	printf("Inicializando a fila...\n");	
	
	/*Inicializa a fila com os elementos do array*/
	for (int i = 0; i < arrsz; i++){
		fila_put(fila, seq[i]);
	}
	printf("Fila:\n");
	fila_imprime(fila);
	
	/*Dá get em alguns itens da fila, exibe o valor
	 * e imprime o estado da fila
	 * após o get*/
	for (int i = 0; i < arrsz-3; i++){
		int get = fila_get(fila);
		printf("Get: %d\nFila:", get);
		fila_imprime(fila);
	}
	printf("Destruindo a fila...\nFila:\n");
	fila_destroi(&fila);
	fila_imprime(fila);
}

E isso é tudo sobre filas em C! Se você ainda não leu, recomendo dar uma olhada nos dois posts sobre listas encadeadas e no post sobre pilhas. Continue acompanhando o blog para aprender a implementar outros tipos abstratos de dados, como listas circulares, filas de prioridade e árvores!