Fila ADT
Uma fila é um tipo abstrato de dados (ADT: abstract data type) que pode ser implementado em C++ como mostra a classe a seguir.
Começando pela declaração da interface da classe:
// início do arquivo "Fila.h"
//---------------------------------------------------------------------------
#ifndef FilaH
#define FilaH
// interface da classe Fila<ADT>
template <class objectType>
class Fila
{
private:
class Node
{
public:
objectType *objetoCorrente;
Node *nodeSucessor;
public:
Node( objectType* ); // construtor
~Node( void ); // destrutor
};
private:
Node *nodeInicial, *nodeFinal;
int qtdNodes;
public:
Fila( void ); // construtor
~Fila( void ); // destrutor
void Guardar( objectType* );
objectType* Retirar( void );
int Tamanho( void );
};
//---------------------------------------------------------------------------
// Implementação da classe Fila<ADT>
//---------------------------------------------------------------------------
#include "Fila.cpp"
//---------------------------------------------------------------------------
#endif
// fim do arquivo "Fila.h"
A seguir temos a implementação dos métodos:
// início do arquivo "Fila.cpp"
//---------------------------------------------------------------------------
#pragma hdrstop
//---------------------------------------------------------------------------
#pragma package(smart_init)
//---------------------------------------------------------------------------
// Atenção: RETIRAR A LINHA #include "Fila.h"
//---------------------------------------------------------------------------
// construtor da classe "Fila"
template <class objectType>
Fila<objectType> :: Fila( void )
{
this->qtdNodes = 0;
this->nodeInicial = NULL;
this->nodeFinal = NULL;
}
// destrutor da classe "Fila"
template <class objectType>
Fila<objectType> :: ~Fila( void )
{
Node *_nodeCorrente = this->nodeInicial, *_nodeSucessor;
while ( _nodeCorrente != NULL ) {
// guardar ponteiro para node sucessor
_nodeSucessor = _nodeCorrente->nodeSucessor;
// destruir objeto corrente
delete _nodeCorrente->objetoCorrente;
// destruir node corrente
delete _nodeCorrente;
// posicionar no node sucessor
_nodeCorrente = _nodeSucessor;
}
}
// guardar um objeto na fila
template <class objectType>
void Fila<objectType> :: Guardar( objectType *__objetoCorrente )
{
// instanciar um novo node
Node *_nodeCorrente = new Node( __objetoCorrente );
// verificar se a fila está vazia
if ( this->qtdNodes == 0 )
{
// atualizar o node inicial da fila
// para o node recem instanciado
this->nodeInicial = _nodeCorrente;
}
else
{
// atualizar o node sucessor do final corrente da fila
// para o node recem instanciado
this->nodeFinal->nodeSucessor = _nodeCorrente;
}
// atualizar o novo node final da fila
// para o node recem instanciado
this->nodeFinal = _nodeCorrente;
// incrementar qtd de nodes na fila
this->qtdNodes ++;
}
// retirar um objeto da fila
template <class objectType>
objectType* Fila<objectType> :: Retirar( void )
{
// guardar node inicial da fila
Node *_nodeCorrente = this->nodeInicial;
// obter ponteiro do objeto corrente
objectType *_objetoCorrente = _nodeCorrente->objetoCorrente;
// fixar novo início da fila no node sucessor
this->nodeInicial = _nodeCorrente->nodeSucessor;
// decrementar qtd de nodes na fila
this->qtdNodes --;
// se esvaziar, apontar node final para NULL
if ( this->qtdNodes == 0 )
{
this->nodeFinal = NULL;
}
// deletar node corrente
delete _nodeCorrente;
// retornar ponteiro do objeto retirado do início da fila
return ( _objetoCorrente );
}
// consultar a quantidade de objetos na fila
template <class objectType>
int Fila<objectType> :: Tamanho( void )
{
return ( this->qtdNodes );
}
// construtor da classe "Node"
template <class objectType>
Fila<objectType> :: Node :: Node( objectType *__objetoCorrente )
{
this->objetoCorrente = __objetoCorrente;
this->nodeSucessor = NULL;
}
// destrutor da classe "Node"
template <class objectType>
Fila<objectType> :: Node :: ~Node( void )
{
}
// fim do arquivo "Fila.cpp"
Os conceitos básicos de uma fila determinam que os elementos que a formam devem ser organizados pela ordem de chegada, ou seja, o primeiro que chegar à fila será o primeiro a ser retirado dela (FIFO: first-in, first-out); os elementos podem ser representados por "nodes" (ou "nós") que guardam 2 ponteiros: um para a estrutura de dados que desejamos organizar e o outro para o "node" seguinte na ordem de chegada da fila.
Usando a Fila ADT em outros projetos
Como exemplo, foi escolhido um caso de uso de strings do tipo Ansi, mas que poderia ser de outro tipo de dados como float, int, double, etc, inclusive outro tipo ADT como Números Complexos ou Números Racionais.
A seguir temos trechos de códigos para o projeto de teste:
1) Incluir no projeto as definições da classe "Fila":
#include "Fila.h"
2) Definir um ponteiro para um objeto da classe Fila<AnsiString>:
Fila<AnsiString> *minhasstrings;
3) Instanciar o objeto da classe Fila<AnsiString>:
this->minhasstrings = new Fila<AnsiString>();
4) Inserindo objetos AnsiString na fila:
this->minhasstrings->Guardar( new AnsiString( "São Paulo" ) );
this->minhasstrings->Guardar( new AnsiString( "Rio de Janeiro" ) );
this->minhasstrings->Guardar( new AnsiString( "Salvador" ) );
this->minhasstrings->Guardar( new AnsiString( "Recife" ) );
this->minhasstrings->Guardar( new AnsiString( "Fortaleza" ) );
this->minhasstrings->Guardar( new AnsiString( "Manaus" ) );
5) Retirando objetos AnsiString da fila:
this->ListBox1->Clear() ;
// deixar os ultimos da fila para testar funcionalidade do
// método destrutor da Fila<AnsiString>
{
AnsiString *valor = this->minhasstrings->Retirar();
this->ListBox1->Items->Add( (*valor) );
delete valor;
}
6) Destruir o objeto da classe Fila<AnsiString> e consequentemente realizar uma varredura e destruição dos possíveis nodes remanescentes, também destruindo os respectivos objetos do tipo AnsiString associados a estes nodes:
delete this->minhasstrings;
7) Não esquecer de habilitar o CodeGuard para certificar se tudo correrá como previsto, pelo menos durante o desenvolvimento.
Até a próxima.
