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.
- Fila em c
- Filas em c - Melhores respostas
- Fila c - Melhores respostas
- Variaveis c++ - Dicas -C++
- Lista duplamente encadeada em c - Dicas -C
- Condicionais em c - Dicas -C
- Lista circular em c - Dicas -C
- Falcon c++ - Downloads - Programação
Assine nossa newsletter!
