Fila Circular Dinâmica

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ó

• publicint dado - levaremos em consideração somente dados inteiros positivos
• publicNoFilaproximo - aponta para o próximo conteúdo da fila.
• (Construtor) - publicNoFila(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ó

publicclassNoFilaCircular {
	publicNoFilaCircularproximo;
	publicint dado;
	
	publicNoFilaCircular(int dado){
		this.proximo = null;
		this.dado = dado;
	}
}

Vejamos agora os atributos e métodos da classe FilaCircularDinamica.

• publicbooleanvazia() - 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.
• publicvoidadicionarFinal(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.
• publicintremoverInicio() - 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) publicFilaCircularDinamica() - 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

publicboolean vazia() {
return inicio == null&& fim == null;
}

Listagem 3: Método para adicionar item na lista

publicvoidadicionarFila(int dado) {
		NoFilaCircular novo = newNoFilaCircular(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

publicintremoverFila() {
	intremovido;

	if (vazia()) {
		removido = -1;
	}elseif (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.

publicStringtoString() {
	String listados = "Numeros" + "\n";
	int numero = 1;

	if (vazia()) {
		return listados = "Não foi possivel encontrar valores cadastrados";
	}elseif (inicio == fim) {
		listados = listados + numero + " - " + inicio.dado;
	}else {
		NoFilaCircularaux = 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

publicbooleanFilaCircularDinamica() () {
	this.inicio = null;
	this.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.