/********************************************************

   ROT-FILA
   ========

   Rotinas basicas de manipulacao de FILAS usando vetores:
   - Estruturas de dados com alocacao estatica
   - Insere no final da fila
   - Remocao do inicio da fila
   - Fila circular

   Aplicacao tipica:
   - Lista de elementos a espera de um tratamento,
     onde a ordem de chegada e importante

   Por: Fernando Osorio
   Data da ultima atualizacao: 25/01/2000

*********************************************************/

#include <stdio.h>

#define MAX_FILA 100

#define FALSO      0
#define VERDADEIRO 1

#define OK         1
#define ERRO       0

typedef int Tipo_Dado;

typedef struct
        {
           Tipo_Dado Dado    [MAX_FILA];
           int       Inicio,Fim;
        }  Tipo_Fila;

/***

 => Rotinas de Manipulacao de FILAS - First In, First Out (FIFO)
    Alocacao sequencia

***

void inicializa_fila  (Tipo_Fila *F);
int  insere_fila      (Tipo_Fila *F; Tipo_Dado  Dado);
int  retira_fila      (Tipo_Fila *F; Tipo_Dado *Dado);
void lista_fila       (Tipo_Fila  F);
int  consulta_fila    (Tipo_Fila  F; int Indice; Tipo_Dado *Dado);
int  cheia_fila       (Tipo_Fila  F);
int  vazia_fila       (Tipo_Fila  F);
int  quantidade_fila  (Tipo_Fila  F);
int  acha_fila        (Tipo_Fila  F; Tipo_Dado Dado; int *Indice);

***/

void inicializa_fila (F)
Tipo_Fila *F;
{
  F->Inicio=0;
  F->Fim=0;
}

int insere_fila (F,Dado)
Tipo_Fila *F;
Tipo_Dado Dado;
{
  int prox;

  prox=F->Fim+1;

  if (prox == MAX_FILA)
     prox=0;

  if (prox == F->Inicio)
     return(ERRO);
  else
  {
     F->Dado[F->Fim]=Dado;
     F->Fim=prox;
     return(OK);
  }
}

int retira_fila (F,Dado)
Tipo_Fila *F;
Tipo_Dado *Dado;
{
  if (F->Fim == F->Inicio)
     return(ERRO);
  else
  {
     *Dado= F->Dado[F->Inicio];
     (F->Inicio)++;
     if (F->Inicio >= MAX_FILA)
        F->Inicio=0;
     return(OK);
  }
}

void lista_fila (F)
Tipo_Fila F;
{
   int cont;

   printf("\n");
   cont=F.Inicio;
   while (cont != F.Fim)
   {
      printf("Fila[%d]=%d\n",cont,F.Dado[cont]);
      cont++;
      if (cont >= MAX_FILA)
         cont=0;
   }
   printf("\n");
}

int consulta_fila (F,Indice,Dado)
Tipo_Fila F;
int Indice;
Tipo_Dado *Dado;
{
  if (F.Fim > F.Inicio)
     if ((Indice <= F.Inicio) || (Indice > F.Fim) ||
         (Indice >= MAX_FILA) || (Indice < 0))
        return(ERRO);
  else
     if (((Indice > F.Fim) && (Indice <= F.Inicio)) ||
          (Indice >= MAX_FILA) || (Indice < 0))
        return(ERRO);
     else
     {
        *Dado=F.Dado[Indice];
        return(OK);
     }
}

int acha_fila (F,Dado,Indice)
Tipo_Fila F;
Tipo_Dado Dado;
int *Indice;
{
  int cont;
  int achou;

  achou=FALSO;
  cont = F.Inicio;
  *Indice = NULL;
  while (cont != F.Fim)
  {
     cont++;
     if (cont == MAX_FILA)
        cont=0;

     if (F.Dado[cont] == Dado)
     {
        achou=VERDADEIRO;
        *Indice=cont;
        break;
     }
  }

  if (achou)
     return(OK);
  else
     return(ERRO);
}

int cheia_fila (F)
Tipo_Fila F;
{
  if ((F.Fim+1 == F.Inicio) || (F.Fim+1 > MAX_FILA))
     return(OK);
  else
     return(ERRO);
}

int vazia_fila (F)
Tipo_Fila F;
{
  if (F.Fim == F.Inicio)
     return(OK);
  else
     return(ERRO);
}

int quantidade_fila (F)
Tipo_Fila F;
{
  if (F.Fim > F.Inicio)
     return(F.Fim-F.Inicio);
  else
     return(F.Fim+(MAX_FILA-1)-F.Inicio);
}

/* Programa Principal */

main()
{
  Tipo_Fila Fila;
  int Valor;

  printf("\n>>> ROTINAS DE MANIPULACAO DE FILAS <<<\n\n");

  inicializa_fila(&Fila);

  if (vazia_fila(Fila))
     printf("=> Fila vazia\n");

  if (insere_fila(&Fila,2))
     printf("=> Valor 2 inserido na fila\n");

  if (insere_fila(&Fila,4))
     printf("=> Valor 4 inserido na fila\n");

  if (insere_fila(&Fila,6))
     printf("=> Valor 6 inserido na fila\n");

  printf("\n=> Elementos da fila... [inicio ao fim]\n");
  lista_fila(Fila);

  if (acha_fila(Fila,4,&Valor))
     printf("=> O valor 4 foi achado na posicao %d\n",Valor);

  if (!acha_fila(Fila,5,&Valor))
     printf("=> O valor 5 nao foi achado na fila\n");

  if (retira_fila(&Fila,&Valor))
     printf("=> Valor %d retirado da fila\n",Valor);

  if (retira_fila(&Fila,&Valor))
     printf("=> Valor %d retirado da fila\n",Valor);

  if (retira_fila(&Fila,&Valor))
     printf("=> Valor %d retirado da fila\n",Valor);

  printf("Pressione uma tecla para continuar...\n");
  getch();

  printf("\n=> Elementos da fila... [inicio ao fim]\n");
  lista_fila(Fila);

  if (vazia_fila(Fila))
     printf("=> Fila vazia\n");

  printf("Pressione uma tecla para terminar o programa...\n");
  getch();


}