Primeiro precisamos entender: o que são as estruturas dinâmicas?
As estruturas dinâmicas têm a capacidade de expansão de acordo com a quantidade de elementos que lhes são adicionados. Neste tipo de estrutura, não é atribuído um comprimento fixo, pois seu tamanho limite é a capacidade de memória, onde é muito difícil ocupá-la totalmente. As estruturas mais utilizadas são as filas, pilhas, listas, tabelas de espalhamento e árvores. Neste artigo, explicarei um tipo muito peculiar de estrutura, a fila circular dinâmica.
Antes de começar a falar sobre fila circular dinâmica, devemos saber o que é uma fila em si. Filas são estruturas que seguem a politica de FIFO (Firstin ,First out ), ou seja, o primeiro a entrar é o primeiro a sair. Um exemplo clássico é uma fila de banco, a primeira pessoa que chegou na fila será atendida e sairá do banco e assim por diante, logo, nunca vai acontecer de cortarem sua vez.
Qual a diferença entre uma fila dinâmica e uma fila circular dinâmica?
No caso da fila dinâmica, perdemos os dados quando removidos, por outro lado, na fila circular dinâmica não temos este problema, pois não ocorre a perca dos dados, apenas são alterados os indicadores de inicio e fim da fila. Apenas são realocados os ponteiros.
Cada elemento da lista é chamado de Nó e, portanto, precisaremos definir esta classe em nosso código.
A classe nó funciona como uma espécie de "caixa", onde colocamos conteúdo (podendo ser um objeto ou uma variável) e apontamos para o próximo elemento, fazendo uma espécie de amarração dos dados para podermos percorrê-los.
Neste exemplo usarei a classe nó com os atributos públicos para facilitar o entendimento.
Atributos e Métodos da classe Nó
- public int dado - levaremos em consideração somente dados inteiros positivos
- public NoFila proximo - aponta para o próximo conteúdo da fila.
- (Construtor) - public NoFila(int dado) - neste método construtor, iremos iniciar o dado sempre com o argumento recebido e o campo proximo como nulo.
Listagem 1: Definição da classe Nó
public class NoFilaCircular {
public NoFilaCircular proximo;
public int dado;
public NoFilaCircular(int dado){
this.proximo = null;
this.dado = dado;
}
}
Vejamos agora os atributos e métodos da classe FilaCircularDinamica.
- public boolean vazia() - se necessário, deve ser utilizado para verificar se a lista esta vazia ou não, se estiver vazia o retorno é verdadeiro, caso contrário, falso.
- public void adicionarFinal(int dado) - método responsável pela adição de elementos na lista. Se a lista estiver vazia ele apenas coloca o fim e o inicio apontados na mesma posição, caso contrário, tem que inserir o novo na ultima posição e alterar o indicador.
- public int removerInicio() - remoção do inicio da lista retornando o valor removido (neste caso um inteiro, porém dependendo da sua aplicação pode ser alterado).
- toString() - método responsável pela formatação de Strings no java, (você necessita adicionar Override - sobrescrever), se você não tiver familiaridade com a tecnologia java pode alterar a assinatura e colocar, por exemplo, publicString listar().
- (Construtor) public FilaCircularDinamica() - Nó inicio e fim serão iniciados como nulo (null).
As listagens seguintes mostram o código de cada um dos métodos citados acima.
Listagem 2: Verifica se a lista está vazia através do inicio e fim
public boolean vazia() {
return inicio == null && fim == null;
}
Listagem 3: Método para adicionar item na lista
public void adicionarFila(int dado) {
NoFilaCircular novo = new NoFilaCircular(dado);
if (vazia()) {
inicio = novo;
fim = novo;
fim.proximo = inicio;
} else {
novo.proximo = inicio;
fim.proximo = novo;
fim = novo;
}
}
Listagem 4: Demonstração da remoção de itens da lista
public int removerFila() {
int removido;
if (vazia()) {
removido = -1;
} else if (inicio == fim) {
removido = inicio.dado;
inicio = null;
fim = null;
} else {
removido = inicio.dado;
fim = inicio;
inicio = inicio.proximo;
fim.proximo = inicio;
}
return removido;
}
Listagem 5: Listar a fila do inicio ao fim e do fim ao inicio.
public String toString() {
String listados = "Numeros" + "\n";
int numero = 1;
if (vazia()) {
return listados = "Não foi possivel encontrar valores cadastrados";
} else if (inicio == fim) {
listados = listados + numero + " - " + inicio.dado;
} else {
NoFilaCircular aux = inicio;
if (aux == fim.proximo) {
listados = listados + numero + " - " +aux.dado+"\n";
aux = aux.proximo;
numero++;
}
while (aux != fim.proximo) {
listados = listados + numero + " - " + aux.dado+"\n";
aux = aux.proximo;
numero++;
}
}
return listados;
}
Listagem 6: Construtor inicializando os atributos como vazio na criação do objeto
public boolean vazia() {
return inicio == null && fim == null;
}
Finalizamos, assim, a definição da nossa fila circular dinâmica. Esta estrutura tem grande aplicabilidade, por exemplo, em operações internas de sistemas operacionais.
Muitas vezes, utilizamos vetores quando precisamos tratar de coleções de objetos. Porém, sabemos que vetores têm suas limitações, como a necessidade de definição de um comprimento inicial. Com as filas diâmicas isso não é necessário, pois seu tamanho "auto-expansível", nos tira essa preocupação.
Ficamos por aqui e até o próximo artigo.
