Filas

Uma fila real é um conjunto disposto em seqüência linear onde os elementos podem “entrar” e “sair” da fila. A maneira mais fácil de imaginar seu comportamento é lembrar das filas encontradas em caixas de banco: como o caixa pode demorar um pouco mais em um atendimento, as pessoas que chegam têm que entrar no final de uma fila para esperar a sua vez de serem atendidas. Quando o caixa está livre, ele pede que a pessoa do início da fila se dirija até ele para ser atendida.

Uma fila enquanto um tipo abstrato de dados é uma estrutura e comportamentos onde podemos acrescentar e remover elementos de um mesmo tipo usando a seguinte descrição de comportamento: Primeiro a Entrar, Primeiro a Sair (do inglês, First In, First Out, FIFO). Os elementos que entram são adicionados ao final de uma fila e os que saem são removidos do seu início.

Podemos criar uma fila usando estruturas e funções específicas para manipular os dados de forma correta. A seguinte implementação usa um vetor para armazenar os elementos de uma fila de caracteres.

// Arquivo filaVetor.h
#define MAX 5
struct SFilaVetor {
	char dados[MAX];
	int inicio;
	int final;
};
typedef struct SFilaVetor Fila;
 
Fila* novaFila();
void fila_inclui(Fila* f, char c);
char fila_exclui(Fila* f);

O arquivo de cabeçalho acima define a estrutura de dados e as assinaturas das funções usadas como interface para nossa fila. A estrutura possui dois campos inicio e final para indicar, respectivamente a posição do próximo elemento que entrar na fila e a posição do próximo elemento a sair da fila. O campo dados, definido como um vetor de MAX posições é usado para guardar os elementos.

// Arquivo filaVetor.c
#include <stdio.h>
#include <stdlib.h>
#include "filaVetor.h"
 
Fila* novaFila(){
	Fila *f = malloc(sizeof(Fila));
	f->inicio = 0;
	f->final = 0;
	return f;
}
void fila_incluir(Fila* f, char c){
	if(f->final == MAX){
		printf("Fila cheia!\n");
		return;
	}
	f->dados[f->final] = c;
	f->final++;
}
 
char fila_excluir(Fila* f){
	if(f->inicio == f->final){
		printf("Fila vazia!\n");
		return;
	}
	f->inicio++;
	return f->dados[f->inicio-1];
}

A função nova_pilha() é responsável por requisitar a memória necessária e iniciar nossas variáveis de controle. Elementos são adicionados à fila pelo procedimento fila_incluir(), onde primeiro devemos verificar se a final>=MAX que significa que fila está cheia. A função fila_excluir() devolve um elemento da posição inicio caso a fila não esteja vazia (representado por inicio==final). Em ambos os casos, inicio e final são incrementados. Com a fila sendo preenchida e esvaziada o comportamento esperado é que inicio “corra atrás” de final. Sempre que ele o alcança temos a fila vazia.

// Arquivo filaVetorTeste.c
#include <stdio.h>
#include "filaVetor.h"
 
int main(){
	Fila *f = novaFila();
	char c; int i;
	for(i=0; i<MAX+1; i++){
		c = 'A'+i;
		printf("Incluindo %c...\n",c);
		fila_inclui(f, c);
	}
	for(i=0; i<MAX+1; i++){
		printf("Removendo...");
		c = fila_exclui(f);
		printf("%c saiu da fila.\n",c);
	}
	for(i=0; i<MAX+1; i++){
		c = 'A'+i;
		printf("Incluindo %c...\n",c);
		fila_inclui(f, c);
	}
}

O programa acima testa o funcionamento da nossa solução acrescentando e removendo, em seguida, MAX+1 elementos à fila.

É importante lembrar que os valores de dados continuam intactos na fila, porém inacessíveis pois os nossos índices não voltam atrás!

Fila Circular

A implementação de fila exposta anteriormente tem um problema sério: as filas só podem armazenar um conjunto limitado de elementos e assim que o limite é atingido a estrutura se torna inútil! Isto acontece porque nossos marcadores de final e início de fila param de funcionar quando atingem a última posição. O ideal seria reaproveitar os espaços liberados pelos elementos removidos da fila, assim podemos sempre adicionar novos elementos desde que o total de elementos armazenados não passe nosso limite definido inicialmente.

Uma alternativa para implementação da fila circular consiste em permitir que os nossos marcadores de início e final de fila possam dar “uma volta” ao início quando atingem o limite de armazenamento. A abordagem abaixo, escolhida para esta implementação, nos faz perder uma posição de armazenagem de elemento mas sua simplicidade de implementação nos permite explorar os efeitos da fila circular.

//arquivo filaCircularVetor.h
#define MAX 5
struct SFilaCircularVetor {
	char dados[MAX];
	int inicio;
	int final;
};
typedef struct SFilaCircularVetor FilaCircular;
 
FilaCircular* novaFila();
void fila_incluir(FilaCircular* f, char c);
char fila_excluir(FilaCircular* f);

O arquivo de cabeçalho não muda muito além da definição de novos tipos. É na implementação das funções é que devemos ter maior atenção com o novo comportamento:

// arquivo filaCircularVetor.c
#include <stdio.h>
#include <stdlib.h>
#include "filaCircularVetor.h"
 
FilaCircular* novaFila(){
	FilaCircular *f = malloc(sizeof(FilaCircular));
	f->inicio = 0;
	f->final = 0;
	return f;
}
void fila_incluir(FilaCircular* f, char c){
	if( f->final+1 == f->inicio ||
		((f->final+1 == MAX) && (f->inicio==0))){ 
		printf("Fila cheia!\n");
		return;
	}
	f->dados[f->final] = c;
	f->final++;
	if(f->final == MAX)	f->final = 0;
}
 
char fila_exclui(FilaCircular* f){
	if(f->inicio == MAX){
		f->inicio = 0;
	}
	if(f->inicio == f->final){
		printf("Fila vazia!\n");
		return;
	}
	f->inicio++;
	return f->dados[f->inicio-1];
}

Em fila_incluir() temos que levar em conta que nossa fila agora pode ter o final em uma posição arbitrária e não mais depois da última posição. Isto nos leva a duas possibilidades: (a) a posição seguinte ao final é o maior valor (MAX) e a primeira posição 0 ainda esteja ocupada pelo inicio; ou (b) a posição seguinte ao final seja a posição inicio. Em ambos os casos temos a fila cheia. Caso contrário, há espaço para uma inclusão e se final passou pelo limite (MAX) devemos movê-lo para a posição 0.

Já em fila_incluir() a única alteração é começamos por verificar se o inicio deve retornar à primeira posição. A condição de fila vazia é a mesma: inicio == final.

Um novo programa de teste agora pode ser escrito da seguinte forma:

// arquivo filaCircularVetorTeste.c
#include <stdio.h>
#include "filaCircularVetor.h"
 
int main(){
	FilaCircular *f = novaFila();
	char c; int i;
	for(i=0; i<MAX+1; i++){
		c = 'A'+i;
		printf("Incluindo %c...\n",c);
		fila_incluir(f, c);
	}
	for(i=0; i<MAX+1; i++){
		printf("Removendo...");
		c = fila_excluir(f);
		printf("%c saiu da fila.\n",c);
	}
	for(i=0; i<MAX+1; i++){
		c = 'A'+i;
		printf("Incluindo %c...\n",c);
		fila_incluir(f, c);
	}
}

Como a fila é circular, podemos incluir elementos indefinidamente desde que a fila não armazene mais que MAX-1 elementos simultaneamente. Os seja, a fila deve ter um fluxo médio de inclusão menor ou igual ao de exclusão. Para o programa acima esta condição não é alcançada e a fila enche sempre que armazena MAX-1 elementos.

A filas têm muitas aplicações que variam desde uso em simuladores até em dispositivos de entrada e saída. Existem implementações otimizadas para tarefas específicas, mas os conceitos são os mesmos abordados nestes exemplos e exercícios.