[Curso de AeED - Aula 15] - Filas

Outra estrutura de dados bastante usada em computação é a fila. Na estrutura de fila, os acessos aos elementos também seguem uma regra. O que diferencia a fila da pilha é a ordem de saída dos elementos: enquanto na pilha “o último que entra é o primeiro que sai”, na fila “o primeiro que entra é o primeiro que sai” (a sigla FIFO – first in, first out – é usada para descrever essa estratégia). A ideia fundamental da fila é que só podemos inserir um novo elemento no final da fila e só podemos retirar o elemento do início.

A estrutura de fila é uma analogia natural com o conceito de fila que usamos no nosso dia a dia: quem primeiro entra numa fila é o primeiro a ser atendido (a sair da fila). Um exemplo de utilização em computação é a implementação de uma fila de impressão. Se uma impressora é compartilhada por várias máquinas, deve-se adotar uma estratégia para determinar que documento será impresso primeiro. A estratégia mais simples é tratar todas as requisições com a mesma prioridade e imprimir os documentos na ordem em que foram submetidos – o primeiro submetido é o primeiro a ser impresso.

De modo análogo ao que fizemos com a estrutura de pilha, neste capítulo discutiremos duas estratégias para a implementação de uma estrutura de fila: usando vetor e usando lista encadeada. Para implementar uma fila, devemos ser capazes de inserir novos elementos em uma extremidade, o fim, e retirar elementos da outra extremidade, o início.


1- Interface do tipo fila

Antes de discutirmos as duas estratégias de implementação, podemos definir a interface disponibilizada pela estrutura, isto é, definir quais operações serão implementadas para manipular a fila. Mais uma vez, para simplificar a exposição, consideraremos uma estrutura que armazena valores reais. Independente da estratégia de implementação, a interface do tipo abstrato que representa uma estrutura de fila pode ser composta pelas seguintes operações:
  1. criar uma estrutura de fila;
  2. inserir um elemento no fim;
  3. retirar o elemento do início;
  4. verificar se a fila está vazia;
  5. liberar a fila.
O arquivo fila.h, que representa a interface do tipo, pode conter o seguinte código:

typedef struct fila Fila;

Fila* cria (void);
void insere (Fila* f, float v);
float retira (Fila* f);
int vazia (Fila* f);
void libera (Fila* f);

A função cria aloca dinamicamente a estrutura da fila, inicializa seus campos e retorna seu ponteiro; a função insere adiciona um novo elemento no final da fila e a função retira remove o elemento do início; a função vazia informa se a fila está ou não vazia; e a função libera destrói a estrutura, liberando toda a memória alocada.



2- A fila estática (utilizando um vetor)

Como no caso da pilha, nossa primeira implementação de fila será feita usando um vetor para armazenar os elementos. Para isso, devemos fixar o número máximo N de elementos na fila. Podemos observar que o processo de inserção e remoção em extremidades opostas fará com que a fila “ande” no vetor. 


A função para criar a fila aloca dinamicamente essa estrutura e inicializa a fila como sendo vazia, isto é, com os índices ini e fim iguais entre si (no caso, usamos o valor zero).

Fila* cria (void){

Fila* f = (Fila*) malloc(sizeof(Fila));

f->ini = f->fim = 0; /* inicializa fila vazia */ return f;

}


Para inserir um elemento na fila, usamos a próxima posição livre do vetor, indicada por fim. Devemos ainda assegurar que há espaço para a inserção do novo elemento, tendo em vista que trata-se de um vetor com capacidade limitada. Consideraremos que a função auxiliar que faz o incremento circular está disponível.


void insere (Fila* f, float v){

if (incr(f->fim) == f->ini) {           /* fila cheia: capacidade esgotada

*/

printf("Capacidade da fila estourou.\n");
exit(1);                     /* aborta programa */

}
/* insere elemento na próxima posição livre */

f->vet[f->fim] = v;
f->fim = incr(f->fim);


A função para retirar o elemento do início da fila fornece o valor do elemento retirado como retorno. Podemos também verificar se a fila está ou não vazia.


float retira (Fila* f){
float v;

if (vazia(f)) {
printf("Fila vazia.\n");

exit(1);                     /* aborta programa */
}

/* retira elemento do início */
v = f->vet[f->ini];

f->ini = incr(f->ini);
return v;

}


  A função que verifica se a fila está vazia pode ser dada por:

int vazia (Fila* f){

return (f->ini == f->fim);
}



Finalmente, a função para liberar a memória alocada pela fila pode ser:

void libera (Fila* f){
free(f);

}


3- Implementando uma fila com alocação dinâmica

Vamos agora ver como implementar uma fila através de uma lista encadeada, que será, como nos exemplos anteriores, uma lista simplesmente encadeada, em que cada nó guarda um ponteiro para o próximo nó da lista. Como teremos que inserir e retirar elementos das extremidades opostas da lista, que representarão o início e o fim da fila, teremos que usar dois ponteiros, ini e fim, que apontam respectivamente para o primeiro e para o último elemento da fila. Essa situação é ilustrada na figura abaixo:


A operação para retirar um elemento se dá no início da lista (fila) e consiste essencialmente em fazer com que, após a remoção, ini aponte para o sucessor do nó retirado. (Observe que seria mais complicado remover um nó do fim da lista, porque o antecessor de um nó não é encontrado com a mesma facilidade que seu sucessor.) A inserção também é simples, pois basta acrescentar à lista um sucessor para o último nó, apontado por fim, e fazer com que fim aponte para este novo nó.

O nó da lista para armazenar valores reais, como já vimos, pode ser dado por:

struct no {

float info;
struct no* prox;

};
typedef struct no No;



A estrutura da fila agrupa os ponteiros para o início e o fim da lista:

struct fila {

No* ini;
No* fim;

};


A função cria aloca a estrutura da fila e inicializa a lista como sendo vazia.

Fila* cria (void){

Fila* f = (Fila*) malloc(sizeof(Fila));
f->ini = f->fim = NULL;

return f;
}



Cada novo elemento é inserido no fim da lista e, sempre que solicitado, retiramos o elemento do início da lista. Desta forma, precisamos de duas funções auxiliares de lista: para inserir no fim e para remover do início. A função para inserir no fim ainda não foi discutida, mas é simples, uma vez que temos explicitamente armazenado o ponteiro para o último elemento. Essa função deve ter como valor de retorno o novo “fim” da lista. A função para retirar do início é idêntica à função usada na implementação de pilha.


/* função auxiliar: insere no fim */

No* ins_fim (No* fim, float v){

No* p = (No*) malloc(sizeof(No));
p->info = v;

p->prox = NULL;

if (fim != NULL) /* verifica se lista não estava vazia */ fim->prox = p;
return p;
}


/* função auxiliar: retira do início */
No* ret_ini (No* ini){
No* p = ini->prox;

free(ini);
return p;

}


As funções que manipulam a fila fazem uso dessas funções de lista. Devemos salientar que a função de inserção deve atualizar ambos os ponteiros, ini e fim, quando da inserção do primeiro elemento. Analogamente, a função para retirar deve atualizar ambos se a fila tornar-se vazia após a remoção do elemento:


void insere (Fila* f, float v){
f->fim = ins_fim(f->fim,v);

if (f->ini==NULL)     /* fila antes vazia? */
f->ini = f->fim;

}

float retira (Fila* f){

float v;
if (vazia(f)) {
printf("Fila vazia.\n");

exit(1);                     /* aborta programa */
}

v = f->ini->info;
f->ini = ret_ini(f->ini);

if (f->ini == NULL) /* fila ficou vazia? */ f->fim = NULL;

return v;

}



A fila estará vazia se a lista estiver vazia:

int vazia (Fila* f){
return (f->ini==NULL);

}



Por fim, a função que libera a fila deve antes liberar todos os elementos da lista.

void libera (Fila* f){
No* q = f->ini;

while (q!=NULL) {
No* t = q->prox;

free(q);
q = t;

}
free(f);

}



Analogamente à pilha, para testar o código, pode ser útil implementarmos uma função que imprima os valores armazenados na fila. Os códigos abaixo ilustram a implementação dessa função nas duas versões de fila (vetor e lista). A ordem de impressão adotada é do início para o fim.



/* imprime: versão com vetor */
void imprime (Fila* f){
int i;

for (i=f->ini; i!=f->fim; i=incr(i))
printf("%f\n",f->vet[i]);

}

/* imprime: versão com lista */
void imprime (Fila* f){
No* q;

for (q=f->ini; q!=NULL; q=q->prox)
printf("%f\n",q->info);

}

[Curso de AeED - Aula 15] - Filas [Curso de AeED - Aula 15] - Filas Reviewed by Vinicius dos Santos on 03:26:00 Rating: 5

Nenhum comentário

Escreve ai sua opinião!