As filas em linguagem C

Novembro 2016


As filas - Primeiro a Entrar Primeiro a Sair


Fila = estrutura de dados

Requisitos

Os tipos de dados
As estruturas
O uso do typedef
Os indicadores
As funções do usuário
As listas simplesmente encadeadas
As listas duplamente encadeadas

Para entender o algoritmo, eu usarei uma lista simplesmente ligada (ou encadeada). Assim sendo, a compreensão das listas encadeadas é necessária.

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 desenvolver, escolhi uma lista simplesmente encadeada. A integração na fila é feita na ordem normal, o primeiro elemento da fila será o primeiro elemento digitado; logo, a sua posição fica no início da fila.

A construção do protótipo 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 indicador seguinte. Este 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,
o número de elementos.

Use outra estrutura (isso não é obrigatório, variáveis podem ser utilizadas).
Veja a composição:
typedef struct ListaDetectada{       
elemento *fim;
int tamanho;
} Pilha;

Operações nas filas

Inicialização

Protótipo da função:
void inicialização (fila * sequência);
O procedimento deve ser feito antes de qualquer outra operação na fila e inicializa os indicadores de início e de fim com o NULL, e o tamanho com o valor 0.

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

Inserção de um elemento na fila

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

Protótipo da função:
int alinhar (Fila * sequência, elemento * inacabada, char *dado);
A primeira imagem exibe o início da inserção, cuja lista tem o tamanho1 depois da inserção.

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


A função
int alinhar (Fila * sequência, elemento * inacabada, 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(inacabada == 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(inacabada->seguinte == NULL)
sequência->fim = novo_elemento;
novo_elemento->seguinte = inacabada->seguinte;
inacabada->seguinte = novo_elemento;
}
sequência->tamanho++;
return 0;
}

C. Tirar um elemento da fila

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

Protótipo da função:
int de_filar (Fila * sequência);
A função volta -1 se falha, caso contrário ela retorna 0.

Passos :
O indicador remov_elem conterá o endereço do primeiro elemento
O indicador de início apontará para o segundo elemento (após a exclusão do primeiro elemento, o segundo passará para o início da fila)
O tamanho da fila será decrementado de um elemento


A função
int de_filar (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 da fila

Para exibir a fila inteira, é preciso se posicionar no início da fila (você poderá fazer isso com o indicador de início). Em seguida, usando o indicador "seguinte" de cada elemento, a fila será atravessada do primeiro até o último elemento. O modo de parada é dado pelo tamanho da fila.

A função
void exibe(Fila *sequência){       
elemento *inacabada;
int i;
inacabada = sequência->início;

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

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

Para recuperar o dado no início da fila sem removê-lo, eu usei um macro. O macro lê os dados do início da fila usando o indicador de início.
#define fila_dado(sequência)  sequência->início->dado

Exemplo completo

file.h

/*********************\       

  • file.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); /* ALINHAR*/ int alinhar (fila * sequência, elemento * inacabada, char *dado); /* DE_FILAR*/ int de_filar (fila * sequência); /* FirstInFirstOut */ #define fila_dado(sequência) sequência->início->dado /* Exibe a fila */ void exibe(fila *sequência);

file_function.h

/***********************\       

  • file_function.h * \***********************/ void inicialização (fila * sequência){ sequência->início = NULL; sequência->fim = NULL; sequência->tamanho = 0; } /* alinhar (adicionar) um elemento na fila */ int alinhar (fila * sequência, elemento * inacabada, 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(inacabada == 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(inacabada->seguinte == NULL) sequência->fim = novo_elemento; novo_elemento->seguinte = inacabada->seguinte; inacabada-> seguinte = novo_elemento; } sequência->tamanho++; return 0; } /* de_filar (remover) um elemento de la fila */ int de_filar (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 exibe(fila *sequência){ elemento *inacabada; int i; inacabada = sequência->início; for(i=0;i<sequência->tamanho;++i){ printf(" %s ", inacabada->dado); inacabada = inacabada->seguinte; } }

file.c

/*********************\       

  • file.c * \*********************/ #include<stdio.h> #include<stdlib.h> #include<string.h> #include "file.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 ("Entre uma palavra:"); scanf ("%s", nome); alinhar (sequência, sequência->fim, nome); printf ("A fila (%de elementos)\n",sequência->tamanho); printf("\nInício de la fila [ "); exibe (sequência); /*o primeiro entrado será exibido */ printf(" ] fim de la fila\n\n"); printf ("Entre uma palavra:"); scanf ("%s", nome); alinhar (sequência, sequência->fim, nome); printf ("A fila (%de elementos)\n",sequência->tamanho); printf("\nInício da fila [ "); exibe (sequência); /*o primeiro entrado será exibido */ printf(" ] fim de la fila\n\n"); printf ("Entre uma palavra:"); scanf ("%s", nome); alinhar (sequência, sequência->fim, nome); printf ("A fila (%de elementos)\n",sequência->tamanho); printf("\nInício de la fila [ "); exibe (sequência); /*o primeiro entrado será exibido */ printf(" ] fim de la fila\n\n"); printf ("\nO primeiro entrado (FirstInFirstOut) [ %s ] será removido", fila_dado(sequência)); printf ("\nO primeiro entrado é removido\n"); de_filar (sequência); /* exclusão do primeiro elemento entrado */ printf ("A fila (%d elementos): \n",sequência->tamanho); printf("\nInício da fila [ "); exibe (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

Veja também :
Este documento, intitulado « As filas em linguagem C »a partir de CCM (br.ccm.net) está disponibilizado sob a licença Creative Commons. Você pode copiar, modificar cópias desta página, nas condições estipuladas pela licença, como esta nota aparece claramente.