3
Obrigado

Algumas palavras de agradecimento nunca são demais.

As filas em linguagem C

Estruturas de dados em fila operam na chamada lógica FIFO - primeiro a entrar, primeiro a sair - e a recuperação é feita na ordem de inserção. O objetivo desse artigo é permitir que o leitor compreenda o uso das filas na linguagem C. Para explicar o algoritmo, optamos por utilizar uma lista simplesmente encadeada para facilitar o entendimento até mesmo por iniciantes em linguagem C.




Requisitos

Para esse artigo, será preciso conhecer os tipos de dados, as estruturas, o uso do typedef, os ponteiros, as funções do usuário, as listas simplesmente encadeadas e as listas duplamente encadeadas.

Definição

A fila é uma estrutura de dados que armazena os dados na ordem FIFO (First In First Out), em português Primeiro a Entrar Primeiro a Sair. A recuperação de dados será feita na ordem de inserção.

Para a nossa explicação, usaremos uma lista simplesmente encadeada. A inserção na fila ocorre na ordem normal. O primeiro elemento da fila será o primeiro elemento digitado; logo, a sua posição fica no início da fila.

Construção do modelo de um elemento da fila

Para estabelecer um dos elemento da fila, usa-se o tipo struct. O elemento da fila conterá um campo dado e um ponteiro seguinte que deve ser do mesmo tipo que o elemento. Caso contrário, ele não poderá apontar para o elemento e permitirá o acesso para o próximo elemento.

typedef struct elementoLista {       
    char *dado;       
    struct elementoLista *seguinte;       
}elemento;


Para controlar a fila, é melhor salvar certos elementos: o primeiro elemento, o último elemento e o número de elementos. Use outra estrutura para isso, mas não há obrigatoriedade, já que podem ser utilizadas variáveis.

typedef struct ListaDetectada{       
  elemento *fim;       
  int tamanho;      
} Fila;

Operações nas filas

Inicialização

Modelo da função:
void inicialização (fila * sequência);


O procedimento deve ser feito antes de qualquer outra operação na fila. Os ponteiros início e fim são posicionados no valor NULL e o tamanho fica com valor 0.

Função:
void inicialização (Fila * sequência){       
  sequência-> início = NULL;       
  sequência->fim = NULL;       
  sequência->tamanho = 0;       
}

Inserção de elemento na fila

Veja o algoritmo de inserção e registro dos elementos:
  • Declaração de elementos a ser inseridos
  • Alocação da memória para o novo elemento
  • Preenchimento do conteúdo do campo de dados
  • Atualização do ponteiro início para o primeiro elemento (topo da fila)
  • Atualização do ponteiro fim (servirá para inserção no fim da fila)
  • Atualização do tamanho da fila


Modelo da função:
int inserir (Fila * sequência, elemento * atual, char *dado);


A primeira imagem exibe o início da inserção, cuja lista tem tamanho 1 depois da inserção.


Na fila, o elemento a ser recuperado é o primeiro a ser inserido. Para isso, a inserção sempre será feita no final da fila. Trata-se da ordem normal de inserção (1°, 2°, 3° etc).


Função:
int inserir (Fila * sequência, elemento * atual, char *dado){       
  elemento *novo_elemento;       
  if ((novo_elemento = (elemento *) malloc (sizeof (elemento))) == NULL)       
    return -1;       
  if ((novo_elemento-> dado = (char *) malloc (50 * sizeof (char)))       
      == NULL)       
    return -1;       
  strcpy (novo_elemento->dado, dado);       

  if(atual== NULL){       
    if(sequência->tamanho == 0)       
      sequência->fim = novo_elemento;       
    novo_elemento->seguinte = sequência->início;       
    sequência-> início = novo_elemento;       
  }else {       
    if(atual->seguinte == NULL)       
      sequência->fim = novo_elemento;       
    novo_elemento->seguinte = atual->seguinte;       
    atual->seguinte = novo_elemento;       
  }       
  sequência->tamanho++;       
  return 0;       
}

Remover elemento da fila

Para remover um elemento da fila, basta excluir o elemento para o qual aponta o ponteiro início. Essa operação não permite recuperar o dado no início da fila (primeiro dado), mas apenas removê-lo.

Modelo da função:
int remover (Fila * sequência);


A função retorna o valor -1 em caso de falha. Caso contrário, o valor retornado será 0.

Etapas: ponteiro remov_elem conterá o endereço do primeiro elemento, ponteiro início apontará para o segundo elemento (após a exclusão do primeiro elemento, o segundo passa para o início da fila) e o tamanho da fila perde uma unidade.


Função:
int remover (Fila * sequência){       
  elemento *remov_elemento;       
  if (sequência->tamanho == 0)       
    return -1;       
  remov_elemento = sequência->início;       
  sequência->início = sequência->início->seguinte;       
  free (remov_elemento->dado);       
  free (remov_elemento);       
  sequência->tamanho--;       
  return 0;       
}

Exibir fila

Para exibir a fila inteira, é preciso se posicionar no início da fila (através do ponteiro início). Em seguida, usando o ponteiro seguinte de cada elemento, a fila será percorrida do primeiro ao último elemento. A condição de parada é dada pelo tamanho da fila.

Função:
void exibir (Fila *sequência){       
  elemento *atual;       
  int i;       
   atual = sequência->início;       

  for(i=0;i<sequência->tamanho;++i){       
    printf(" %s ", atual->dado);       
    atual = atual->seguinte;       
  }       
}

Recuperação do dado no início da fila

Para recuperar o dado no início da fila sem removê-lo, usaremos uma macro que lê os dados do início da fila usando o ponteiro início.

#define fila_dado(sequência)  sequência->início->dado

Exemplo completo

fila.h

/*      fila.h       */
typedef struct elementoLista{         
char *dado;         
struct elementoLista *seguinte;       
} Elemento;       
typedef struct ListaDetectada{         
Elemento *início;  Elemento *fim;  int tamanho;       
} Fila;

/* inicialização */       
void inicialização (fila * sequência);       
/* Inserir*/       
int inserir (fila * sequência, elemento * atual, char *dado);       

/* Remover*/       
int remover (fila * sequência);       

/* FirstInFirstOut */       
#define fila_dado(sequência) 
sequência->início->dado       

/* Exibir a fila */       
void exibir (fila *sequência);

fila_function.h

/*      fila_function.h       */
void inicialização (fila * sequência){         
sequência->início = NULL;         
sequência->fim = NULL;         
sequência->tamanho = 0;       }

/* inserir (adicionar) um elemento na fila */       
int inserir (fila * sequência, elemento * atual, char *dado){         
Elemento *novo_elemento;         
if ((novo_elemento = (elemento *) malloc (sizeof (elemento))) == NULL)
return -1;         
if ((novo_elemento->dado = (char *) malloc (50 * sizeof (char))) == NULL)
return -1;         
strcpy (novo_elemento->dado, dado);         
if(atual == NULL){           
if(sequência->tamanho == 0)             
sequência->fim = novo_elemento;           
novo_elemento->seguinte = sequência->início;           
sequência-> início = novo_elemento;         
}
else 
{           
if(atual->seguinte == NULL)             
sequência->fim = novo_elemento;           
novo_elemento->seguinte = atual->seguinte;           
atual-> seguinte = novo_elemento;         }         
sequência->tamanho++;         
return 0;       
}

/* remover (eliminar) elemento da fila */       
int remover (fila * sequência){         
Elemento *remov_elemento;         
if (sequência->tamanho == 0)           
return -1;         
remov_elemento = sequência->início;         
sequência-> início = sequência->início->seguinte;         
free (remov_elemento->dado);         
free (remov_elemento);         
sequência->tamanho--;         
return 0;       
}

/* exibição da fila */       
void exibir (fila *sequência){         
Elemento *atual;         
int i;         
atual = sequência->início;         
for(i=0;i<sequência->tamanho;++i){           
printf(" %s ", atual->dado);           
atual = atual->seguinte;         
}       
}

fila.c

/*      fila.c       */
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include "fila.h"
#include "fila_function.h"
int main (){          
Fila *sequência;         
char *nome;         
if ((sequência = (fila *) malloc (sizeof (fila))) == NULL)           
return -1;         
if ((nome = (char *) malloc (50 * sizeof (char))) == NULL)           
return -1;         
inicialização (sequência);         
printf ("Inserir uma palavra:");         
scanf ("%s", nome);         
inserir (sequência, sequência->fim, nome);         
printf ("A fila (%de elementos)\n",sequência->tamanho);         
printf("\nInício de la fila [ ");         
exibir (sequência);     

/*primeiro elemento inserido será exibido */         
printf(" ] fim de la fila\n\n");         
printf ("Inserir uma palavra:");         
scanf ("%s", nome);         
Inserir (sequência, sequência->fim, nome);         
printf ("A fila (%de elementos)\n",sequência->tamanho);         
printf("\nInício da fila [ ");         
exibir (sequência);      

/*primeiro elemento inserido será exibido */         
printf(" ] fim da fila\n\n");         
printf ("Inserir uma palavra:");         
scanf ("%s", nome);         
Inserir (sequência, sequência->fim, nome);         
printf ("A fila (%de elementos)\n",sequência->tamanho);         
printf("\nInício de la fila [ ");         
exibir (sequência);      

/*primeiro elemento inserido será exibido */         
printf(" ] fim da fila\n\n");         
printf ("\nO primeiro elemento inserido (FirstInFirstOut) [ %s ] será removido",
fila_dado(sequência));         
printf ("\nO primeiro elemento inserido é removido\n");         
remover (sequência);              

/*remoção do primeiro elemento inserido*/         
printf ("A fila (%d elementos): \n",sequência->tamanho);         
printf("\nInício da fila [ ");         
exibir (sequência);         
printf(" ] fim da fila\n\n");         
return 0;       
}

Veja também

As listas simplesmente encadeadas
As listas duplamente encadeadas
As listas circulares
As pilhas

Foto: © Everypixel.
Este documento, intitulado 'As filas em linguagem C', está disponível sob a licença Creative Commons. Você pode copiar e/ou modificar o conteúdo desta página com base nas condições estipuladas pela licença. Não se esqueça de creditar o CCM (br.ccm.net) ao utilizar este artigo.

Assine nossa newsletter!

Receba toda semana o melhor conteúdo

Assine nossa newsletter!