Como funciona uma fila circular dinamica



Primeiro precisamos entender.O que são as estruturas dinamica ?

As estruturas dinamicas tem a capacidade de aumento de acordo com o decorrer da aplicação , neste tipo de estrutura  não é atribuito um final, pois  seu tamanho limite é a capacidade de memoria , onde é muito dificil ocupa-lá totalmente.As estruturas mais utilizadas são as filas , pilhas , listas , tabelas de espalhamento e arvorés, neste artigo explicarei um tipo muito peculiar de estrutura a fila circular dinamica.

Antes de começar a falar sobre fila circular dinamica , devemos saber o que é uma fila em si. São estruturas  seguem a politica de FIFO (First in , First out ) ou seja primeiro a entrar é o primeiro a sair , um exemplo classico é uma fila de banco , a primeira pessoa que chegou na fila será atendida e sairá do banco e assim por diante ou sejá nunca vai acontecer de cortarem sua vez.

Qual a diferença de uma fila dinamica e uma fila circular dinamica ?

Resposta : no caso da fila dinamica perdemos os dados quando removidos , por outro lado  na fila circular dinamica 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.

 

Nós precisamos da uma classe Nó ,porém o que seria esta classe nó ?

Classe nó , funciona como uma especie de "caixa" , onde colocamos conteudo(podendo ser um objeto ou uma variavel) e apontamos para o proximo conteudo,fazemos uma especie de amarração dos dados para podermos percorre-los .

 Neste exemplo usarei a classe nó com os atributos publicos para facilitar o entendimento.

Atributos e Metodos

  • public int dado - levaremos em consideração somentes dados inteiros positivos
  • public NoFila proximo - aponta para o proximo conteudo da fila.
  • (Construtor) - public NoFila( int dado) - neste metodo construtor iremos iniciar o dado sempre com o argumento recebido e campo proximo como nulo.

 

 

 

Listagem 1 - como fazer a criação da classe Nó

 

[CODE]

public class NoFilaCircular {

   public NoFilaCircular proximo;

   public int dado;

  

   public NoFilaCircular(int dado){

         this.proximo = null;

         this.dado = dado;

   }

}

[/CODE]

 

 

Quais metodos são necessarios na classe FilaCircularDinamica?

  • public boolean vazia() - se necessario deve ser utilizado para verificar se a lista esta vazia ou não , se estiver vazia o retorno é verdadeiro , caso contrario falso.

 

Listagem 2 - Verifica se a lista esta faziia através do inicio e fim

 

[CODE]

public boolean vazia() {

         return inicio == null && fim == null;

   }

[/CODE]

 

  • public void adicionarFinal(int dado) - metodo responsavel 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 contrario tem que inserir o novo na ultima posição e alterar o indicador.

 

Listagem 3 - Metodo para adicionar item na lista .

 

[CODE]

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;

         }

 

   }

[/CODE]

 

 

  • 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).

Listagem 4 - Demonstração da remoção de itens da lista

[CODE]

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;

   }

[/CODE]

 

toString() - metodo responsavel pela formatação de Strings no java , (você necessida adicionar Override - sobrescrever), se você não tiver familiaridade com a tecnologia java pode alterar a assinatura e colocar, por exemplo: public String listar()

Listagem 5 - Mostra onde realmente a magica acontece, vai listar a lista do inicio ao fim e do fim ao inicio.

[CODE]

 

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;

 

   }

[/CODE]

 

Listagem 6- Construtor inicializando os atributos como vazio na criação do objeto.

[CODE]

public boolean vazia() {

         return inicio == null && fim == null;

   }

[/CODE]


Autor: Caio Felipe Da Silva Portugal


Artigos Relacionados


Vento

Ja Ta Na Hora

Mulher Ii

Um Dia Sem Você

A Destinação Da Sabedoria

Poesia

Inexplicável