#ifndef _FILA_H_
#define _FILA_H_

#include "comum.h"

/* Tipo abstrato Fila Circular: estrutura ligada e dinâmica.
   Sacrifica-se um elemento (nó-cabeça) a fim de otimizar os
   algoritmos. O ponteiro da fila aponta para o último elemento que
   por sua vez aponta para o nó-cabeça. O nó-cabeça aponta para o
   início da fila. */
 
typedef struct fila {
  int info; /* informação */  
  struct fila *prox; /* apontador para o próximo elemento */
} Fila;

/* Operações sobre Fila */

Fila *filCria(); /* Cria fila vazia. */

void filDestroi(Fila **f); /* Destrói fila. */

void filInsere(Fila **f, int x); /* Insere elemento x. */

int filRemove(Fila **f); /* Remove elemento do início da fila. */

bool filVazia(Fila *f); /* Retorna true se a fila estiver vazia e
                            false no caso contrário. */

Fila *filBusca(Fila *f, int x); /* Retorna o ponteiro para o elemento
                                   x, se este for encontrado, e NULL
                                   no caso contrário. Usa busca linear
                                   obviamente e o nó-cabeça como
                                   sentinela. */


/* Tipo abstrato Fila Circular (implementação seqüencial).
   Sacrifica-se um elemento (nó-cabeça) a fim de distinguir entre fila
   vazia e fila cheia, além de otimizar os algoritmos. O nó-cabeça e
   os índices de início e fim da fila variam durante a manutenção da
   fila. O índice fim aponta para o último elemento inserido e o
   índice inicio aponta para o nó-cabeça. O primeiro nó após o nó
   cabeça representa o primeiro elemento da fila. */

 
typedef struct filas {
  int *info; /* informação */  
  int nmax; /* número máximo de elementos que podem ser armazenados na fila */
  int inicio,fim; /* índices de início e fim da fila, respectivamente */  
} FilaS;

/* Operações sobre Fila (implementação seqüencial) */

FilaS *filSCria(int nmax); /* Cria fila vazia com capacidade para
                             armazenar nmax elementos (i.e. info tem
                             tamanho nmax+1) e inicializa inicio=fim=0. */

void filSDestroi(FilaS *f); /* Destrói fila. */

void filSInsere(FilaS *f, int x); /* Insere elemento x. */

int filSRemove(FilaS *f); /* Remove elemento do início da fila. */

bool filSVazia(FilaS *f); /* Retorna true se a fila estiver vazia e
                             false no caso contrário. */

bool filSCheia(FilaS *f); /* Retorna true se a fila estiver cheia e
                             false no caso contrário. */

int filSBusca(FilaS *f, int x); /* Retorna o índice do elemento x, se
                                   este for encontrado, e -1 no caso
                                   contrário. Usa busca linear e o
                                   nó-cabeça como sentinela. */


#endif