2013/2:AED-2013.10.17: TAD Fila Laboratório

Applets:
http://www.cosc.canterbury.ac.nz/mukundan/dsal/StackAppl.html
http://www.cosc.canterbury.ac.nz/mukundan/dsal/QueueAppl.html
http://www.cosc.canterbury.ac.nz/mukundan/dsal/appldsal.html

// especificação da TAD fila

// definicao da chave da fila
typedef int TipoChave;
// definicao do registro para o item
struct T_Item{
  TipoChave chave;
};
// definicao do tipo TipoItem
typedef struct T_Item TipoItem;
// definição do apontador para celula
typedef struct T_Celula * TipoApontador;
// definição do registro T_Celula
struct T_Celula{
  TipoItem Item; // item
  TipoApontador Prox; // apontador para prox. celula
};
// definicao do TipoCelula
typedef struct T_Celula TipoCelula;
// definicao do registro T_Fila
struct T_Fila{
  int Tamanho;
  int Capacidade;
  TipoApontador Frente, Tras;
};
// definicao do TipoFila
typedef struct T_Fila TipoFila;

// operacoes da TAD FILA

// enfileirar
void Enfileirar(TipoFila * Fila, TipoItem item);
// desenfileira
void Desenfileirar(TipoFila * Fila, TipoItem * item);
// criar uma fila vazia
void CriarFila(TipoFila * Fila, int capacidade);
// verificar se estah cheia
int FilaCheia(TipoFila Fila);
// verificar se estah vazia
int FilaVazia(TipoFila Fila);
// obter frente
void FilaFrente(TipoFila Fila, TipoItem * item);
// imprimir o conteudo da fila
void ImprimirFila(TipoFila Fila);

// IMPLEMENTACOES DAS OPERACOES
// criar uma fila vazia
void CriarFila(TipoFila * Fila, int capacidade)
{
     // 1) criar a celula cabeca
     Fila->Frente = (TipoApontador) 
       malloc(sizeof(TipoCelula));
     // 2) fazer frente e tras apontar para a nova celula
     Fila->Tras = Fila->Frente;
     // 3) inicializar o tras (prox = NULL)
     Fila->Tras->Prox = NULL;     
     // 4) inicializar o tamanho e a capacidade
     Fila->Tamanho = 0;
     Fila->Capacidade = capacidade;
}

// enfileirar
void Enfileirar(TipoFila * Fila, TipoItem item)
{
     // 1) verificar se a FILA está cheia
     if (FilaCheia(*Fila) == 1){
       printf("ERRO: Fila está cheia!");
       return;
     }
     // 2) criar uma nova celula a partir do TRAS
     Fila->Tras->Prox = (TipoApontador)
       malloc(sizeof(TipoCelula));
     // 3) Adicionar o item na nova celula
     Fila->Tras->Prox->Item = Item;
     // 4) inicializar o PROX da nova celula
     // 5) atualizar o TRAS
     // 6) Atualizar o tamanho da FILA
}

// verificar se estah cheia
int FilaCheia(TipoFila Fila)
{   if (Fila.Capacidade == Fila.Tamanho)
    { return 1;
    } else {
      return 0;
    }
}

// verificar se estah vazia
int FilaVazia(TipoFila Fila)
{   if (Fila.Frente == Fila.Tras)
    { return 1;
    } else {
      return 0;
    }    
}











// especificação da TAD fila

// definicao da chave da fila
typedef int TipoChave;
// definicao do registro para o item
struct T_Item{
  TipoChave chave;
};
// definicao do tipo TipoItem
typedef struct T_Item TipoItem;
// definição do apontador para celula
typedef struct T_Celula * TipoApontador;
// definição do registro T_Celula
struct T_Celula{
  TipoItem Item; // item
  TipoApontador Prox; // apontador para prox. celula
};
// definicao do TipoCelula
typedef struct T_Celula TipoCelula;
// definicao do registro T_Fila
struct T_Fila{
  int Tamanho;
  int Capacidade;
  TipoApontador Frente, Tras;
};
// definicao do TipoFila
typedef struct T_Fila TipoFila;

// operacoes da TAD FILA

// enfileirar
void Enfileirar(TipoFila * Fila, TipoItem item);
// desenfileira
void Desenfileirar(TipoFila * Fila, TipoItem * item);
// criar uma fila vazia
void CriarFila(TipoFila * Fila, int capacidade);
// verificar se estah cheia
int FilaCheia(TipoFila Fila);
// verificar se estah vazia
int FilaVazia(TipoFila Fila);
// obter frente
void FilaFrente(TipoFila Fila, TipoItem * item);
// imprimir o conteudo da fila
void ImprimirFila(TipoFila Fila);

// IMPLEMENTACOES DAS OPERACOES
// criar uma fila vazia
void CriarFila(TipoFila * Fila, int capacidade)
{
     // 1) criar a celula cabeca
     Fila->Frente = (TipoApontador) 
       malloc(sizeof(TipoCelula));
     // 2) fazer frente e tras apontar para a nova celula
     Fila->Tras = Fila->Frente;
     // 3) inicializar o tras (prox = NULL)
     Fila->Tras->Prox = NULL;     
     // 4) inicializar o tamanho e a capacidade
     Fila->Tamanho = 0;
     Fila->Capacidade = capacidade;
}

// enfileirar
void Enfileirar(TipoFila * Fila, TipoItem item)
{
     // 1) verificar se a FILA está cheia
     if (FilaCheia(*Fila) == 1){
       printf("ERRO: Fila está cheia!");
       return;
     }
     // 2) criar uma nova celula a partir do TRAS
     Fila->Tras->Prox = (TipoApontador)
       malloc(sizeof(TipoCelula));
     // 3) Adicionar o item na nova celula
     Fila->Tras->Prox->Item = item;
     // 4) atualizar o TRAS
     Fila->Tras = Fila->Tras->Prox;
     // 5) inicializar o PROX da nova celula
     Fila->Tras->Prox = NULL;
     // 6) Atualizar o tamanho da FILA
     Fila->Tamanho++;
}

// desenfileira
void Desenfileirar(TipoFila * Fila, TipoItem * item)
{    TipoApontador aux; // auxiliar
     // 1) se a FILA estiver vazia
     if (FilaVazia(*Fila) == 1){
       // 1.1) mostrar mensagem de erro e sair
       printf("ERRO: Fila estah vazia!\n");
       return;
     }
     // 2) Guardar a celula que está na frente
     aux = Fila->Frente->Prox;
     // 3) Atualizar a FRENTE (PROX)
     Fila->Frente->Prox = Fila->Frente->Prox->Prox;
     // 4) Decrementar o tamanho
     Fila->Tamanho--;
     // 5) Obter o item removido
     *item = aux->Item;
     // 6) liberar a celula da memoria
     free(aux);
     // 7) Atualizar TRAS se fila estiver vazia
     if (FilaVazia(*Fila) == 1)
     {  Fila->Tras = Fila->Frente;
     }
}
// imprime a fila
void ImprimirFila(TipoFila Fila)
{  printf("Fila %d/%d\n", 
     Fila.Tamanho, Fila.Capacidade);
   // 1) pegando o elemento da frente
   TipoApontador aux = Fila.Frente;
   // 2) Enquanto houver itens para navegar
   while (aux->Prox != NULL)
   { // exibir o item atual
     printf ("%d -> ", aux->Prox->Item.chave);      
     // ir para o próximo elemento
     aux = aux->Prox;
   } printf("\n");   
}
// imprime o elemento na frente da fila
void FilaFrente(TipoFila Fila, TipoItem * item)
{  if (FilaVazia(Fila) == 0){ // se FILA NAO for vazia
     *item = Fila.Frente->Prox->Item;  
   }
}
// verificar se estah cheia
int FilaCheia(TipoFila Fila)
{   if (Fila.Capacidade == Fila.Tamanho)
    { return 1;
    } else {
      return 0;
    }
}

// verificar se estah vazia
int FilaVazia(TipoFila Fila)
{   if (Fila.Frente == Fila.Tras)
    { return 1;
    } else {
      return 0;
    }    
}









#include <stdio.h>
#include <stdlib.h>
#include "tad-fila.h"

int main(int argc, char *argv[])
{
  TipoFila fila;
  TipoItem item;
  
  // 1) Criar fila nova
  CriarFila(&fila, 10);
  ImprimirFila(fila);
  // 2) enfileirar itens
  item.chave = 2;
  Enfileirar(&fila, item);
  item.chave = 3;
  Enfileirar(&fila, item);
  // 3) imprimir fila
  ImprimirFila(fila);
  // 4) desenfileirar itens
  Desenfileirar(&fila, &item);
  printf("Desenfileirou: %d\n", item.chave);
  // 5) imprimir fila
  ImprimirFila(fila);
  
  system("PAUSE");
  return 0;
}