Representação de uma Fila em um Vetor

 - Fila Linear
 - Fila Circular
               0           (MAX -1)
               _____________
Fila Dupla -> |x|...|_|x|x|x|       Situação genérica
               î     î   
              fim  inicio  
#define MAX ...

typedef ... TipoDoElemento;

int inicio, fim tamanho; /* fim = (inicio + tamanho) mod MAX */

TipoDoElemento FilaCircular[MAX];

void InsereFilaCircular( TipoDoElemento x )
{
  if( tamanho == MAX )
    OVERFLOW();

  tamanho++;
  fim = (fim + 1)%MAX;
  FilaCircular[fim] = x;
}

void RemoveFilaCircular( TipoDoElemento *x )
{
  if( tamanho == 0 )
    Underflow();
  else
  {

    tamanho--;
    inicio = (inicio + 1)%MAX;
    *x = FilaCircular[inicio];
  }
}

  Pergunta:

   Qual a utilidade de 'tamanho' ???
  
  Ora, existem dois casos onde 'inicio == fim':
   - Quando a fila esta vazia;
   - Quando a fila esta completamente cheia.

  Resolvemos isso utilizando 'tamanho'.

    Fila Dupla em Alocação Sequencial  

               0                    (MAX -1)
               ______________________
Fila Dupla -> |_|...|_|x|x|x|_|..._|_|
                     î     î
                    esq   dir

#define MAX ...

typedef ... TipoDoElemento;

int esquerda, direita;

TipoDoElemento FilaDupla[MAX];

void InicializaFilaDupla()
{
  esquerda = direita = MAX/2;
}

void InsereDireitaFilaDupla( TipoDoElemento x )
{
  if( direita == (MAX - 1)  )
    Overflow();

  FilaDupla[++direita] = x;
}

void InsereEsquerdaFilaDupla( TipoDoElemento x )
{
  if( esquerda == -1 )
    Overflow();

  FilaDupla[esquerda--] = x;
}


void RemoveDireitaFilaDupla( TipoDoElemento *x )
{
  if( direita == esquerda )
    Underflow();
  else
  {
    *x = FilaDupla[direita--];
    if( esquerda == direita)
      InicializaFilaDupla();
  }
}

void RemoveEsquerdaFilaDupla( TipoDoElemento *x )
{
  if( direita == esquerda )
    Underflow();
  else
  {
    *x = FilaDupla[++esquerda];
    if( esquerda == direita)
      InicializaFilaDupla();
  }
}


    Alocação Ligada para Listas Lineares

  A sequencia dos elementos de uma lista linear é dada através de ligações. 
Assim cada nó da lista contém dois campos:
  _
 |  info: informação do nó
<
 |_ prox: "endereço"do próximo elemento da lista


  Representação Gráfica:

          ___     ___     ___     ___
lista -> |_|_|-> |_|_|-> |_|_|-> |_|_|-|
                                       ~


    Lista Livre
  
  Lista ligada contendo todos os nós que não estão sendo utilizados pelo programa
 em um determinado instante. Sempre que o programa necessita de um novo nó, o 1º(primeiro)
 nó da lista livre é removido e utilizado.
  Sempre que um nó não é mais necessário, ele deve ser inserido na lista livre. 

typedef ... TipoInfo;
typedef struct no1{
        TipoInfo   info;
        struct no1 *prox;
        } No, *apontNo;

apontNo livre;

void InicializaListaLivre()
{
  livre = NULL;
}

void ExtraiNo( apontNo *p )
{
  if( livre == NULL )
  {
    *p = (No *)malloc(sizeof(No));
    if( *p == NULL )
      Overflow();
  }
  else
  {
    *p    = livre;
    livre = livre->prox;
  }
}

void DevolveNo( apontNo p )
{
  p->prox = livre;
  livre   = p;
}

    Listas Lineares Ligadas

(1) Manipulação de uma Pilha

void InicializaPilha()
{
  topo = NULL;
}

void Empilha( TipoInfo x )
{
  apontNo p;

  ExtraiNo(&p);
  p->info = x;
  p->prox = topo;
  topo = p;
}

void Desempilha( TipoInfo *x )
{
  apontNo p;
  if( topo == NULL )
    Underflow();
  else
  {
    p  = topo;
    *x = p->info;
    topo = topo->prox;
    DevolveNo(p);
  }
}
 
  (2) Manipulação de uma Fila em Lista Ligada 

   ___     ___     ___     ___
  |_|_|-> |_|_|-> |_|_|-> |_|_|-|
    î                       î   ~
  inicio                   fim


void InicializaFila()
{
  inicio = fim = NULL;
}

void InsereFila( TipoInfo x )
{
  apontNo p;

  ExtraiNo(&p);
  p->info = x;
  p->prox = NULL;

  if( fim == NULL )
    inicio = p;
  else
    fim->prox = p;

  fim = p;  
}

void RemoveFila( TipoInfo *x )
{
  apontNo p;
  
  if( inicio == NULL )
    Underflow();
  else
  {
    p = inicio;
    *x = p->info;
    inicio = inicio->prox;
    
    if( inicio == NULL )
      fim = NULL;

    DevolveNo(p);
  }
}

Exercícios da aula:

1- Implementar uma fila dupla circular em alocação sequencial. 
Testar com uma fila de inteiros.

2- Implementar uma fila dupla em alocação ligada. Testar a implementação.