PRG29003: Etapa 2: A construção da prglib
Desde o início do semestre foi usada a biblioteca prglib, que contém implementações das estruturas de dados estudadas. Na primeira etapa da disciplina se enfatizou conhecer e usar essas estruturas de dados. Na segunda etapa o foco está em implementá-las, e o resultado esperado é a implementação da prglib pelas equipes. As versões da prglib a serem criadas devem ser compatíveis com a versão original, de forma que os projetos que foram realizados possam ser recompilados e funcionarem corretamente.
Os arquivos da prglib são:
- prglib.h: inclui todas as declarações das estruturas de dados
- libs/fila.h: declara a fila
- libs/pilha.h: declara a pilha
- libs/lista.h: declara a lista
- libs/hash.h: declara a tabela hash
- libs/arvore.h: declara a árvore de pesquisa binária
- libs/fila-impl.h: define (implementa) a fila
- libs/pilha-impl.h: define a pilha
- libs/lista-impl.h: define a lista
- libs/hash-impl.h: define a tabela hash
- libs/arvore-impl.h: define a árvore de pesquisa binária
Os arquivos de declarações praticamente não são modificados em relação à prglib original. O esforço deve se concentrar nos arquivos de implementação, onde de fato serão programados os métodos que contêm os algoritmos dessas estruturas de dados. Para facilitar essa tarefa, a nova prglib é fornecida na forma de um conjunto de arquivos com os esqueletos das estruturas de dados:
O início da implementação se dá pelas estruturas de dados mais simples: fila e pilha. Com elas se pode recompilar o projeto 1.
Filas
De forma geral, uma fila é uma estrutura de dados que funciona como mostrado na figura abaixo:
Filas podem ser implementadas usando um vetor. No entanto, isso somente tem utilidade para filas de pequeno tamanho e cuja capacidade seja conhecida de antemão. Esse tipo de fila é chamado de fila circular, podendo ser imaginada como a figura a seguir:
Fila circular: os números são os índices do vetor que contém a fila
Uma fila circular possui uma área de memória limitada para armazenamento sequencial dos dados, a qual pode guardar uma quantidade máxima de dados. A fila circular usa essa área de memória de forma a poder identificar o início e final da fila. Novos dados são adicionados no fim da fila, e dados são retirados sempre do início da fila. O funcionamento da fila circular pode ser exemplificado pela seguinte figura, em que os números 5, 8, 2, 6 e 4 são enfileirados (além do número 5 ser desenfileirado em algum momento):
Deve-se observar que dados são guardados na área de memória, e não mudam de posição. O controle sobre o início e final da fila se faz por meio de dois atributos, chamados convenientemente de inicio e fim. Assim, um novo dado é enfileirado na posição indicada por fim, e em seguida o fim da fila avança para a próxima posição livre. Um dado desenfileirado é retirado da posição indicada por inicio, após o que inicio avança para a próxima posição. Em ambos os casos, se a próxima posição estiver fora da área de memória, então volta-se para sua primeira posição (como mostrado no avanço do fim da fila nos exemplos e) e f)), e por isso esse tipo de fila se chama fila circular. Desta forma, as operações de enfileiramento e desenfileiramento podem ser implementadas por algoritmos bastante simples e com baixo custo computacional.
Implementação da fila circular
A fila a ser criada deve ser capaz de guardar qualquer tipo de dado, sem necessitar de qualquer modificação em seu código-fonte. Assim, a fila torna-se genérica e reutilizável em outros programas. Há mais de uma abordagem para tornar uma fila (ou qualquer outra estrutura de dados) capaz de guardar qualquer coisa. Nesta disciplina de PRG2 será usada uma abordagem com templates, por sua simplicidade.
A fila utilizada no projeto 1 está definida da seguinte forma:
#ifndef FILA_H
#define FILA_H
namespace prglib {
template <typename T> class fila : public std::queue<T> {
public:
fila(unsigned int max_itens);
fila(const fila<T>& orig);
virtual ~fila();
fila<T>& operator=(const fila<T> & outra);
void enfileira(const T & algo);
T desenfileira();
const T & frente() const;
bool vazia() const;
bool cheia() const;
unsigned int comprimento() const;
unsigned int capacidade() const;
private:
// qtde de dados na fila, e capacidade da fila
unsigned int N, cap;
// a área de memoria onde são armazenados os dados (um vetor)
T * buffer;
// posições do ínício e fim da fila
unsigned int inicio, fim;
};
} // fim do namespace
#endif /* FILA_H */
Arquivo libs/fila.h
A implementação dos métodos da fila deve ser feita no arquivo libs/fila-impl.h.
A implementação da fila pode ser testada com este pequeno programa:
#include<iostream>
#include <prglib.h>
using namespace std;
using prglib::fila;
int main() {
fila<int> f1(10); // cria uma fila chamada "f1", com capacidade 10
// enfileira os números 5, 8, 2 e 4 na fila "f1"
f1.enfileira(5);
f1.enfileira(8);
f1.enfileira(2);
f1.enfileira(4);
// desenfileira um por um dos dados da fila, mostrando-os na tela, até
// que a fila fique vazia
while (not f1.vazia()) cout << "Dado: " << f1.desenfileira() << endl;
return 0;
}
Programa de teste da fila
Atividade
- Inicie a implementação de sua fila. Entenda os atributos da fila, e como eles são usados para armazenar os dados. Veja também as operações típicas da fila, e pense em como implementá-las segundo o modelo de uma fila circular.
- Teste sua fila com o programa exemplo.