Estrutura de dados em C -> Fila Circular com operador módulo

Publicado por Thiago Gallo 29/10/2004 (última atualização em 09/10/2010)

[ Hits: 23.564 ]

Download filaCircular.c

Download 1285949702.filacircular.cpp (versão 2)




Exemplo de implementacao de uma fila circular utilizando o operador módulo (%) para simplificar as coisas. Como vcs podem ver, fica bem simples e eficiente :P

PS: o codigo para download esta melhor organizado e comentado!

  



Versões atualizadas deste script

Versão 2 - Enviado por Vinicius Miqueloti em 01/10/2010

Changelog: Script fila circular para corrigir erros do codigo original.

Correções:

1 - Corrigido função remover (agora apaga os elementos ao remover, e quando a fila está vazia as variaveis que controlam a fila são reiniciadas para que assim o proximo elemento a ser inserido entre na primeira posicao do vetor.)

2 - Adicionado função mostrafila (para facilitar a utilização do codigo e torna-lo legivel.)

3 - Adicionado menu de utilização (para depurar e compreender melhor a lógica de funcionamento da fila circular, agora é possivel visualizar passo a passo cada adição e remoção de elementos quando quisér e o efeito causado por elas na fila.)

Download 1285949702.filacircular.cpp


Esconder código-fonte

#include <stdio.h>
#include <stdlib.h> // comente esta linha se for compilar no linux

#define MAX 4 // numero maximo de elementos na fila

// cria uma fila vazia
int comeco = 0;   // comeco da fila
int tamanho = 0;  // tamanho da fila (numero de elementos)
int queue[MAX];   // vetor da fila

void inserir( int );    // inserir elementos no fim da fila
void remover( void );   // remover elementos do comeco da fila

int main(void)
{
   int i; // contador
   
   inserir(1);
   inserir(10);
   inserir(100);
   inserir(1000);
   remover();
   inserir(6);
   remover();
   inserir(60);
   
   //// mostra fila na tela ////
   for(i = 0; i < MAX; i++)
      printf("fila[%i] = %i\n", i, queue[i]);
   
//   system("pause"); // comente esta linha se for rodar no linux
   return ( 0 );
    
} // fim main    

void inserir( int elemento )
{
   //// checa se a fila esta cheia ////
   if( tamanho == MAX )
      printf("\nfila cheia\n");

   else {
      //// converte os valores virtuais (tamanho e comeco) para o valor real utilizando o operador modulo ////
      queue[ ((comeco + tamanho) % MAX) ] = elemento; 
      //// incrementa tamanho da fila (elemento foi inserido) ////
      tamanho ++; 
   } 
   
} // fim funcao

void remover(void)
{
   //// checa se a fila esta vazia ////
   if( tamanho == 0 )
      printf("\nfila vazia\n");
   
   else {
      //// apaga o primeiro elemento da fila deslocando o ponteiro do comeco para proximo elemento ////
      comeco ++;
      //// decrementa o contador de tamanho (um valor foi removido) ////
      tamanho --;
   }
   
} // fim funcao

Scripts recomendados

Aula basica de C

Labirinto de Teseu

Determinando resultado de uma partida futebol (iniciante)

Conversor binário

Binário para decimal


  

Comentários
[1] Comentário enviado por Miqueloti em 01/10/2010 - 09:40h

A função remover está incorreta, ela apenas aponta para o proximo elemento na fila incrementando a variavel global começo, deveriamos antes zerar o valor do elemento removido, isto é, literalmente remover, não apenas apontar o proximo elemento.

Com o codigo do jeito que está, caso seja exibido o vetor após a função remover ser executada, o programa irá exibir o vetor com informações incorretas (um ou mais elementos não serão removidos mesmo após ter sido executado a função remover. Estes elementos apenas serao sobreescritos caso executemos a funcao inserir até a fila ficar cheia, por isto o print deste codigo exibe corretamente o final do vetor, mais caso seja feito o teste de mesa será identificado o seu erro.)

a correcao é simples, uma linha será adicionada na funcao remover:

void remover(void)
{
// checa se a fila esta vazia
if( tamanho == 0 )
printf("\nfila vazia\n");

else {
// (LINHA QUE FOI ADICIONADA) apaga o primeiro elemento da fila
queue[comeco] = 0;
// indica que a fila comeca em uma posicao a mais
comeco ++;
// decrementa o contador de tamanho de elementos
tamanho --;
}

Seria interessante também fazer uma função chamada mostrafila, para que seja mais facil vizualizar a inserção e remoção de elementos.

Enfim, a logica do código é muito boa, e o mesmo está extremamente bem comentado. Devo parabenizálo pois vai ser muito util para quem está ingressando nos estudos. As resalvas feitas são apenas para melhorar o entendimento dos estudantes que acessarem este exemplo. Outra dica é, Use e Abuse de funções, neste exemplo uma função mostrafila se faz mais do que necessário.

[2] Comentário enviado por Miqueloti em 01/10/2010 - 13:17h

Desconsiderem o codigo acima, pois o mesmo ainda tem bugs, o codigo correto para a remoção segue abaixo:

// funcao para remover elemento
void remover(void)
{
int i;
/* Verifica se a fila esta no ultimo elemento. Caso esteja, reinicia
a fila circular*/
if( tamanho < 2 )
{
printf("\nUltimo elemento removido, fila vazia!\n");
for (i=0; i<4; i++) // apaga elementos da fila vazia
queue[i] = 0;

comeco = 0; // reinicia o marcador de comeco da fila
tamanho = 0; // zera o contador de elementos da fila
}
else
{
// apaga o primeiro elemento da fila
queue[comeco] = 0;

// indica o novo comeco da fila
if (comeco < 3)
comeco ++;

// caso esteja no final do vetor, volta a fila para o comeco
else
comeco = 0;

// decrementa o contador de tamanho de elementos
tamanho --;
}

} // fim funcao

Segue também um codigo que desenvolvi com menu para melhor vizualização de como funciona uma fila circular:

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>

#define MAX 4 // numero maximo de elementos na fila

// variaveis globais para funcionamento da fila circular
int comeco = 0; // comeco da fila
int tamanho = 0; // tamanho da fila (numero de elementos)
int queue[MAX]; // vetor da fila

// funcao para inserir elemento
void inserir( int elemento )
{
// checa se a fila esta cheia
if( tamanho == MAX )
printf("\nfila cheia\n");

else {
/* converte os valores virtuais (tamanho e comeco) para o
valor real utilizando o operador modulo */
queue[ ((comeco + tamanho) % MAX) ] = elemento;
// incrementa tamanho da fila (elemento foi inserido)
tamanho ++;
}

} // fim funcao

// funcao para remover elemento
void remover(void)
{
int i;
/* Verifica se a fila esta no ultimo elemento. Caso esteja, reinicia
a fila circular*/
if( tamanho < 2 )
{
printf("\nUltimo elemento removido, fila vazia!\n");
for (i=0; i<4; i++) // apaga elementos da fila vazia
queue[i] = 0;

comeco = 0; // reinicia o marcador de comeco da fila
tamanho = 0; // zera o contador de elementos da fila
}
else
{
// apaga o primeiro elemento da fila
queue[comeco] = 0;

// indica o novo comeco da fila
if (comeco < 3)
comeco ++;

// caso esteja no final do vetor, volta a fila para o comeco
else
comeco = 0;

// decrementa o contador de tamanho de elementos
tamanho --;
}

} // fim funcao

// funcao para printar a fila na tela
void mostrafila(void)
{
int i; // contador

printf("\nFila Circular: \n");

for(i = 0; i < MAX; i++)
printf("fila[%d] = %d\n", i, queue[i]);
} // fim funcao

int main(void)
{
int n, x; // variaveis para utilizacao de um menu

clrscr();// limpa a tela do programa

while (n!=4) // menu para inserir, remover, mostrar elementos da fila
{
printf("Algoritmo de fila circular - Diego Albuquerque\n");
printf("\n\nDigite a opcao desejada:\n\n 1 Inserir um \
elemento\n\n 2 Retirar um elemento\n\n 3 Mostrar fila\n\n 4 Sair\n\n");
scanf ("%d",&n);
switch (n)
{
case 1:
printf("\nDigite um numero inteiro para \
inserir na fila. \n");
scanf("%d",&x);
inserir(x);
printf("\nPressione enter para continuar!\n");
getch();
clrscr();
break;
case 2:
remover();
printf("\nPressione enter para continuar!\n");
getch();
clrscr();
break;
case 3:
mostrafila();
printf("\nPressione enter para continuar!\n");
getch();
clrscr();
break;
case 4:
break;
default:
printf("\nNumero Invalido!!!");
printf("\nDigite um numero entre 1 e 4\n");
printf("\nPressione enter para continuar!\n");
getch();
clrscr();
} // fim case
} // fim while

return (0);

} // fim main

[3] Comentário enviado por edududu88 em 15/10/2016 - 11:54h

Algumas melhorias

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#define MAX 100 // numero maximo de elementos que uma fila suporta

struct Fila {
int comeco;
int tamanho;
int tamanho_maximo; // tamanho máximo da fila
int queue[MAX];
};

// funcao para inserir elemento
void inserir(struct Fila* f, int elemento)
{
// checa se a fila esta cheia
if( f->tamanho == f->tamanho_maximo )
printf("\nfila cheia\n");

else {
/* converte os valores virtuais (tamanho e comeco) para o
valor real utilizando o operador modulo */
f->queue[ ((f->comeco + f->tamanho) % f->tamanho_maximo) ] = elemento;
// incrementa tamanho da fila (elemento foi inserido)
f->tamanho ++;
}

} // fim funcao

// funcao para remover elemento
void remover(struct Fila* f)
{
int i;
/* Verifica se a fila esta no ultimo elemento. Caso esteja, reinicia
a fila circular*/
if( f->tamanho < 2 )
{
printf("\nUltimo elemento removido, fila vazia!\n");
for (i=0; i<f->tamanho_maximo; i++) // apaga elementos da fila vazia
f->queue[i] = 0;

f->comeco = 0; // reinicia o marcador de comeco da fila
f->tamanho = 0; // zera o contador de elementos da fila
}
else
{
// apaga o primeiro elemento da fila
f->queue[f->comeco] = 0;

// indica o novo comeco da fila
if (f->comeco < f->tamanho_maximo-1)
f->comeco ++;

// caso esteja no final do vetor, volta a fila para o comeco
else
f->comeco = 0;

// decrementa o contador de tamanho de elementos
f->tamanho --;
}

} // fim funcao

int primeiro(struct Fila f){
if (f.tamanho > 0)
return f.queue[f.comeco];
else
return -1;
}

// funcao para printar a fila na tela
void mostrafila(struct Fila f)
{
int i; // contador

printf("\nFila Circular: \n");

for(i = 0; i < f.tamanho_maximo; i++)
printf("fila[%d] = %d\n", i, f.queue[i]);
} // fim funcao


// funcao para printar a fila na tela da forme que ele é
void mostrafilaOrdem(struct Fila f)
{
int i; // contador

printf("\nFila Circular: \n");
printf("\nComeco: %d", f.comeco);
printf("\nTamanh: %d", f.tamanho);
printf("\nTamMax: %d \n", f.tamanho_maximo);

while(f.tamanho>0){
printf(" %d ", f.queue[f.comeco]);
if( f.tamanho < 2 )
{
f.tamanho = 0;
}
else
{
if (f.comeco < f.tamanho_maximo-1)
f.comeco ++;
else
f.comeco = 0;
f.tamanho --;
}
}

} // fim funcao

int main(void)
{

//Fila teste
struct Fila teste;
teste.comeco = 0;
teste.tamanho = 0;
teste.tamanho_maximo = 10;


int n, x; // variaveis para utilizacao de um menu

system("cls");

while (n!=6) // menu para inserir, remover, mostrar elementos da fila
{
printf("Algoritmo de fila circular - Diego Albuquerque\n");
printf("\n\nDigite a opcao desejada:\n\n 1 Inserir um \
elemento\n\n 2 Retirar um elemento\n\n 3 Mostrar fila\n\n 4 Mostrar estrutura\n\n 5 Primeiro\n\n6 Sair\n\n");
scanf ("%d",&n);
switch (n)
{
case 1:
printf("\nDigite um numero inteiro para \
inserir na fila. \n");
scanf("%d",&x);
inserir(&teste, x);
printf("\nPressione enter para continuar!\n");
getch();
system("cls");
break;
case 2:
remover(&teste);
printf("\nPressione enter para continuar!\n");
getch();
system("cls");
break;
case 3:
mostrafilaOrdem(teste);
printf("\nPressione enter para continuar!\n");
getch();
system("cls");
break;
case 4:
mostrafila(teste);
printf("\nPressione enter para continuar!\n");
getch();
system("cls");
break;
case 5:
printf("Primeiro: %d", primeiro(teste));
printf("\nPressione enter para continuar!\n");
getch();
system("cls");
case 6:
break;
default:
printf("\nNumero Invalido!!!");
printf("\nDigite um numero entre 1 e 5\n");
printf("\nPressione enter para continuar!\n");
getch();
system("cls");
} // fim case
} // fim while

return (0);

} // fim main


Contribuir com comentário




Patrocínio

Site hospedado pelo provedor RedeHost.
Linux banner
Linux banner

Destaques

Artigos

Dicas

Tópicos

Top 10 do mês

Scripts