Ninja Code

Olá “PessoALL”.

Nesta postagem abordarei um assunto que muitas vezes nos dá dores de cabeça enquanto estamos estudando Estrutura de Dados, mais especificamente, Filas.

Funcionamento:

Em Estrutura de Dados, uma fila tem a mesma estrutura de uma lista encadeada, porém, seu funcionamento é diferente. Filas possuem a característica FIFO (First In First Out - primeiro a entrar, primeiro a sair).

Podemos fazer uma analogia com uma fila de banco, por exemplo, onde o primeiro cliente a chegar será o primeiro a ser atendido e os próximos clientes a chegar, deverão entrar na fila aguardando o atendimento, seguindo este critério.

Sendo sua idéia principal a característica First In First Out, quando removemos um elemento da fila, deverá sempre ser removido o primeiro elemento. Sendo assim, novos elementos deverão ser inseridos na última posição.

Suponhamos que temos a seguinte fila:

Caso o número 5 seja inserido, teremos a seguinte fila:

Agora, para removermos um elemento da fila, temos que respeitar a característica FIFO, portanto, removeremos sempre o primeiro número, no caso o 1:

Ao removermos o 1, o início da fila passa a ser o próximo elemento, que na nossa fila é o 2.

Agora que já aprendemos o conceito da Fila, podemos ir para a ação! 

Este código foi feito de maneira dinâmica, mas também podemos fazer de me maneira estática usando vetores.

Precisamos definir o nosso tipo fila na nossa biblioteca fila.h:

typedef struct filaNo{
     int dado;
     struct filaNo* prox; // Definição dos nós da fila
  }tfilaNo;                 
typedef struct tfila {     
     tfilaNo* inicio;
     tfilaNo* final;      // Definição do tipo fila
  } tfila;

Quando criamos nosso tipo fila os ponteiros de inicio e fim da fila precisam apontar para null. A função criar_fila faz esta ação.

void cria_fila (tfila *F)
{
   F->inicio = F->final = NULL;
}

O método fila_vazia diz se nossa fila está vazia ou não.

int fila_vazia (tfila F)
{
   if(F.inicio == NULL && F.final == NULL) return 1;
   else return 0;
}

Para inserir um novo nó na fila, precisamos alocar na memória um novo nó, atribuir o valor a este nó, apontar o último nó e o ponteiro do final da fila para este novo nó. Caso a fila esteja vazia, este novo nó será o primeiro e os ponteiros do início e final da fila apontarão para este novo nó.

A nossa função de inserção ficará do seguinte modo:

int inserir_fila (tfila *F, int valor)
{
   tfilaNo *novo;
   novo = (tfilaNo*) malloc(sizeof(tfilaNo));
   if (novo == NULL) return 0;  /* Erro ao alocar o novo nó */
   novo->dado = valor;   //
   novo->prox = NULL;    //Atribuição do valor e apontando o próximo para NULL
   if (fila_vazia(*F))
      F->inicio = novo;  // Se a fila estiver vazia, o novo nó sera o primeiro da fila
   else
      (F->final)->prox = novo;
   F->final = novo;     // Senão, o ponteiro para o final da fila apontará para o novo nó
   return 1;
}

Para removermos um nó da fila, usaremos a função auxiliar primeiro_fila, como o nome já diz, retorna o primeiro elemento da fila para que possamos removê-lo.

int primeiro_fila (tfila F, int *dado){
   if (fila_vazia(F)) return 0;
      *dado = (F.inicio)->dado;
   return 1;
}

Na função remover_fila, fazemos a chamada da função primeiro_fila. Caso o nó retornado seja o último da fila, o ponteiro final da fila apontará para null. O ponteiro do início da fila apontará para onde o nó que será removido aponta. Caso ele seja o último, o ponteiro início apontará para null, já que o próximo nó do que estamos removendo aponta para null.

int remover_fila (tfila *F, int *valor)
{
   tfilaNo *aux;
   if (fila_vazia(*F)) return 0;  /* fila vazia  */
   primeiro_fila(*F,valor);     // Remove o primeiro nó
   if (F->inicio == F->final)   // Se existir somente um nó na fila, apontamos o final da fila para NULL
      F->final = NULL;
   aux = F->inicio;               // Atribuímos o nó retornado da fila ao nó auxiliar 
   F->inicio = (F->inicio)->prox; // O início da fila apontará para o próximo nó do que estamos removendo
   free(aux);                   
   return 1;
}

Tendo nossos métodos principais prontos, podemos criar a fila da seguinte maneira no nosso método main().

int main(int argc, char *argv[])
{
  tfila doc;                                  
  int a;
  
  cria_fila(&doc);   
  inserir_fila (&doc ,1);
  inserir_fila (&doc ,2);
  inserir_fila (&doc ,3);
  inserir_fila (&doc ,4);
  inserir_fila (&doc ,5);  
  
  while(!fila_vazia(doc)){
        remover_fila(&doc,&a);      
        printf("    %d\n", a);
  }
  
  system("PAUSE");	
  return 0;
}

Inserimos os números de 1 a 5 na nossa fila e, em seguida, removemos os valores da fila enquanto ela não estiver vazia. Executando nosso código, temos o seguinte resultado:

Espero que este exemplo ajude. Abaixo estão algumas referências.

Referências:

[1] http://java2s.com/Code/C/Data-Structure-Algorithm/QueueinC.htm

[2] http://msdn.microsoft.com/pt-br/library/tze823w7(v=vs.90).aspx

[3] http://forum.clubedohardware.com.br/estruturas-dados-pilhas/702596

[4] Herbert Schildt, C Completo e Total 3ª Ed.

Se você deseja fazer o download do projeto (Dev-C++) segue -> Fila.rar (7.99 kb).

Até a próxima.

Portanto, qualquer que me confessar diante dos homens, eu o confessarei diante de meu Pai, que está nos céus. (Mateus 10:32)

Tags: c, fila, FIFO, estrutura de dados, dev-c++, First In First Out