Filas

Uma fila é uma estrutura de dados que admite inserção de novos elementos e remoção de elementos antigos.  Mais especificamente, uma  fila (= queue)  é uma estrutura sujeita à seguinte regra de operação: sempre que houver uma remoção, o elemento removido é o que está na estrutura há mais tempo.

Em outras palavras, o primeiro objeto a ser inserido na fila é também o primeiro a ser removido. Essa política é conhecida pela sigla FIFO (= First-In-First-Out).

Veja o verbete Queue na Wikipedia.

Implementação em um vetor

Suponha que nossa fila FIFO mora em um vetor fila[0..N-1].  Suponha que os elementos do vetor são inteiros (isso é só um exemplo; os elementos da fila poderiam ser quaisquer outros objetos).  A parte do vetor ocupada pela fila será

fila[ini..fim-1].

0		ini					fim			N-1

O primeiro elemento da fila está na posição ini e o último na posição fim-1.  A fila está vazia se  ini == fim  e cheia se  fim == N.    Para remover (= delete = de-queue) um elemento da fila basta fazer

   x = fila[ini++];  

Isso equivale ao par de instruções  "x = fila[ini]; ini += 1;",  nesta ordem.  É claro que você só deve fazer isso se tiver certeza de que a fila não está vazia.    Para inserir (= insert = enqueue) um objeto y na fila basta fazer

   fila[fim++] = y;  

Note como a coisa funciona bem mesmo quando a fila está vazia. É claro que você só deve inserir um elemento na fila se ela não estiver cheia; caso contrário a fila transborda (transbordar = to overflow).  Em geral, a tentativa de inserir em uma fila cheia é uma situação excepcional, que indica um mau planejamento lógico do seu programa.

Aplicação: distâncias

Eis uma aplicação clássica do conceito de fila. Imagine 6 cidades numeradas de 0 a 5 e interligadas por estradas de mão única. (É claro que você pode trocar "6" pelo seu número favorito.) As ligações entre as cidades são representadas por uma matriz A da seguinte maneira:

A[i][j] vale 1  se existe estrada da cidade i para a cidade j

e vale 0 em caso contrário. Suponha que a matriz tem zeros na diagonal, embora isso não seja importante.   Exemplo:

	0	1	2	3	4	5
0	0	0	0	0	0	0
1	1	0	0	0	0	0
2	0	1	0	0	1	0
3	0	0	1	0	1	0
4	1	0	0	0	0	0
5	0	1	0	0	0	0

A distância de uma cidade c a uma outra j é o menor número de estradas que devo percorrer para ir de c a j.  Nosso problema:  dada uma cidade c,

determinar a distância de c a cada uma das demais cidades.

As distâncias serão armazenadas em um vetor d: a distância de c a j será d[j].  Que fazer se é impossível chegar de c a j?  Poderíamos dizer nesse caso que d[j] é infinito.  Mas é mais limpo e prático dizer que d[j] vale 6, pois nenhuma distância "real" pode ser maior que 5.  Se adotarmos c igual a 3 no exemplo acima, teremos d igual a

	0	1	2	3	4	5
	2	2	1	0	1	6

Eis a idéia de um algoritmo que usa o conceito de fila para resolver nosso problema: 

• uma cidade é considerada ativa se já foi visitada mas as estradas que começam nela ainda não foram exploradas;
• mantenha uma fila das cidades ativas;
• em cada iteração, remova da fila uma cidade i e insira na fila todas as cidades vizinhas de i que ainda não foram visitadas.

// Recebe uma matriz A que representa as interligacões entre 
// cidades 0,1,..,5: há uma estrada (de mão única) de i a j 
// se e só se A[i][j] == 1.  Devolve um vetor d que registra 
// as distâncias da cidade c a cada uma das outras: d[i] é a 
// distância de c a i.

int *distancias (int A[][6], int c)
{
   int *d, j;
   int fila[6], ini, fim;

   d = mallocX (6 * sizeof (int));
   for (j = 0; j < 6; ++j)  d[j] = 6;
   d[c] = 0;
   ini = 0; fim = 1; fila[0] = c;  // c entra na fila

   while (ini != fim) { 
      int i, di;
      i = fila[ini++];  // i sai da fila
      di = d[i];
      for (j = 0; j < 6; ++j)
         if (A[i][j] == 1 && d[j] >= 6) {
            d[j] = di + 1;
            fila[fim++] = j;  // j entra na fila
         }
   }
   return d;
}

Para compreender o algoritmo (e provar que ele está correto), observe que as seguinte propriedades invariantes valem no início de cada iteração:

1. para cada cidade x,  se d[x] < 6 então d[x] é a distância de c a x;
2. a seqüência de números  d[fila[0]..fila[fim-1]]  é crescente;
3. se  d[fila[ini]] vale k  então  d[fila[fim-1]] ≤ k+1;
4. para cada índice h em 0..ini-1, toda estrada que começa em fila[h] termina em algum elemento de fila[0..fim-1].

Exercícios

Implementação circular

No exemplo das distâncias, é fácil ver que o vetor que abriga a fila não precisa ter mais componentes que o número total de cidades, pois cada cidade entra na fila no máximo uma vez.  Em geral, entretanto, é difícil prever o espaço necessário para abrigar a fila. Nesses casos, é mais inteligente implementar a fila de maneira "circular", como mostraremos a seguir.

Suponha que os elementos da fila estão dispostos no vetor  fila[0..N-1]  de uma das seguintes maneiras:

fila[ini..fim-1]   ou   fila[ini..N-1] fila[0..fim-1].

0		ini					fim			N-1

0				fim				ini		N-1

Teremos sempre 0 ≤ ini < N e 0 ≤ fim < N,  mas não podemos supor que ini ≤ fim .  A fila está

•  vazia  se   fim == ini  e
•  cheia  se   fim+1 == ini     ou     fim+1 == N  e  ini == 0 .

(Resumindo, a fila está cheia se  (fim+1) % N == ini.)  A posição fim estará sempre desocupada, para que possamos distinguir uma fila cheia de uma vazia.  Para remover um elemento da fila basta fazer

   x = fila[ini++];
   if (ini == N) ini = 0;

É claro que isso só deve ser feito se você sabe que a fila não está vazia. Para inserir um elemento y na fila faça

   if (fim + 1 == ini || fim + 1 == N && ini == 0) {
      printf ("\nSocorro! Fila vai transbordar!\n");
      exit (EXIT_FAILURE); 
   }
   fila[fim++] = y;
   if (fim == N) fim = 0;

O código começa por verificar se a fila está cheia; se estiver, não há nada a fazer senão pedir socorro e abortar o programa.

Exercícios

Implementação de uma fila em uma lista encadeada

Como administrar uma fila armazenada em uma lista encadeada? Digamos que as células da lista são do tipo celula:

typedef struct cel {
   int         conteudo; 
   struct cel *prox;
} celula;

É preciso tomar algumas decisões de projeto sobre como a fila vai morar na lista.  Vamos supor que nossa lista encadeada é circular :  a última célula aponta para a primeira. Vamos supor também que a lista tem uma célula-cabeça; essa célula não será removida nem mesmo se a fila ficar vazia.  O primeiro elemento da fila fica na segunda célula; a última célula da fila é a célula anterior à célula-cabeça.

Temos um ponteiro fi que guarda o endereço da célula-cabeça. A fila está vazia se fi->prox == fi.  Uma fila vazia pode ser criada e inicializada assim:

celula *fi;
fi = mallocX (sizeof (celula));
fi->prox = fi;

Podemos agora definir as funções de manipulação da fila.  A remoção é fácil:

// Remove um elemento da fila fi. Supõe que a fila 
// não está vazia. Devolve o elemento removido.

int remove (celula *fi) {
   int x;
   celula *p;
   p = fi->prox;  // p aponta primeiro da fila
   x = p->conteudo;
   fi->prox = p->prox;
   free (p);
   return x;  
}

A inserção exige um truque de gosto duvidoso: armazenar o novo elemento na célula-cabeça original:

// Insere um novo elemento com conteudo y na fila fi.
// Devolve o endereço da cabeça da fila resultante.

celula *insere (int y, celula *fi) { 
   celula *nova;
   nova = mallocX (sizeof (celula));
   nova->prox = fi->prox;
   fi->prox = nova;
   fi->conteudo = y;
   return nova;
}

Exercícios