Java – Fila Teória de Tipos de Dados Abstractos Definição de tad



Yüklə 445 b.
tarix18.04.2018
ölçüsü445 b.
#39090


  • JAVA – Fila


Teória de Tipos de Dados Abstractos

  • Definição de TAD

    • Especificar as propriedades fundamentais de um tipo de dado, de um modo independente da sua implementação numa linguagem.
  • Implementação de TAD em JAVA

    • Passo1: Definição da Interface Descrição os nomes dos métodos que o TAD suporta e como eles são declarados e usados
    • Passo2: Escolha da representação concreta do TAD Decisão: Estrutura estática ou dinâmica.
    • Passo3: Implementação da interface Uso do mecanismo de classes


  • Definição de TAD Fila



Definição do TAD Fila (linguagem natural)

  • Uma fila é um contentor de objectos que são inseridos e removidos de acordo com o princípio primeiro-a-entrar-primeiro-a-sair (PEPS) ou first-in-first-out (FIFO).

  • Objectos podem ser inseridos sempre que necessário, mas apenas o inserido a mais tempo (o primeiro) pode ser removido.

  • Dizemos que os elementos são inseridos no final da fila (rear/tail) e removidos do início da fila (front/head).

  • O nome fila deriva de uma analogia com uma fila de pessoas.

  • As operações fundamentais são inserir na fila (ensere/enqueue) e remover da fila (remove/dequeue).



Definição do TAD Fila (operações)

  • O ADT fila suporta os seguintes métodos fundamentais:

    • insere(o): Insere o objecto o no final da fila
      • Entrada: Objecto; Saída: Nenhuma
    • remove(): Remove e retorna o objecto do início da fila - um erro ocorre se a fila está vazia
      • Entrada: Nenhuma; Saída: Objecto
  • Adicionalmente temos os seguintes métodos:

    • tamanho(): Retorna o número de objectos na fila
      • Entrada: Nenhuma; Saída: Inteiro
    • estaVazia(): Retorna um valor booleano indicando se a fila está vazia
      • Entrada: Nenhuma; Saída: Booleano
    • inicio(): Retorna o objecto do inicio da fila, sem removê-lo - um erro ocorre se a fila está vazia
      • Entrada: Nenhuma; Saída: Objecto


Exemplo de execução numa fila F



  • Implementação de TAD Fila



Passo1: Definição da Interface Fila

  • public interface Fila {

  • // Métodos de acesso

  • public int tamanho( ); // Retorna o número de

  • // elementos na fila

  • public boolean estaVazia( ); // Vê se a fila

  • // está vazia

  • public Object inicio( ) // Retorna o elemento

  • throws FilaVaziaException; // do início se a fila

  • // não está vazia

  • // Métodos de atualização

  • public void insere( Object elemento ) // Insere um

  • throws FilaCheiaException; // elemento

  • // na fila

  • public Object remove( ) // Retorna e remove o

  • throws FilaVaziaException; // elemento do inicio

  • // da fila se

  • // chamado com a

  • // fila não vazia

  • }



  • Implementação de TAD Fila

  • Passo 2

  • (com a utilização da estrutura estática)



Passo2: Escolha da representação concreta do TAD (cont)

  • Vamos usar um array de tamanho fixo para implementar uma fila F, de N entradas (p.e.: N = 1.000) para armazenar os elementos

  • Uma solução, seria fazer F[0] sempre ser o início da fila e deixar a fila crescer a partir daí

  • Esta solução não seria eficiente e requereria mover todos os elementos da fila quando houvesse uma remoção, requerendo bastante tempo de processamento para a operação remove

  • Para obtermos um tempo constante na execução de cada método, nós precisamos de uma solução de configuração diferente

  • Solução: Uso de array circular

  • Cada método da implementação do ADT fila através de um array circular é executado no tempo O(1)



Passo2: Escolha da representação concreta do TAD (cont)

  • Num array circular de tamanho n, todo o elemento possui um sucessor e antecessor, em particular:

    • O sucessor de a[n–1] é a[0]
    • O antecessor de a[0] é a[n–1].
  • Maneira alternativas de visualizar um array circular (tamanho 8):



Passo2: Escolha da representação concreta do TAD (cont)

  • Para evitar mover os objectos colocados em F, nós definimos duas variáveis i e f, que têm os seguintes significados:

    • i é o índice da célula do array na fila F que armazena o primeiro elemento da fila
    • f é o índice da próxima célula disponível do array na fila F
    • i = f significa que a fila está vazia e no começo, i = f = 0
  • Quando queremos remover um elemento do início da fila, nós podemos simplesmente incrementar i para o índice da próxima célula

  • Quando queremos inserir um elemento no final da fila, nós podemos simplesmente incrementar f para o índice da próxima célula disponível em F



Passo2: Escolha da representação concreta do TAD (cont)

  • Este esquema requer um tempo constante para execução de cada método porém, apresenta um problema:

    • após N-1 inserções e remoções de um único elemento, teremos i = f = N-1 e a próxima inserção causará um erro índice-de- array-fora-de-limites
  • Para evitar este problema, definiremos o array F como circular, isto é, o array vai de F[0] até F[N-1] e F[0] segue F[N-1]

  • A circularidade é obtida incrementando:

    • i para (i+1) mod N e
    • f para (f+1) mod N


Passo2: Escolha da representação concreta do TAD (cont)



Passo2: Escolha da representação concreta do TAD (cont)

  • Animação (com maxlen = 6):



Passo2: Escolha da representação concreta do TAD (cont)

  • Isto resolve o problema parcialmente pois, as situações de fila vazia e fila cheia serão representadas, ambas, por i = f

  • A solução apresentada aqui é limitar o número máximo de elementos na fila a N-1 e lançar uma excepção FilaCheiaException para sinalizar que não é possível fazer mais inserções

  • A computação do tamanho da fila será dada por:

  • (N-i+f) mod N



Passo2: Escolha da representação concreta do TAD Fila (algoritmo)



  • Implementação de TAD Fila

  • Passo 2

  • (com a utilização da estrutura dinâmica)

  • (lista simplesmente ligada)



Passo2: Escolha da representação concreta do TAD Fila (cont.)

  • As remoções serão feitas na cabeça da lista e as inserções na cauda da lista

  • Cada método da implementação do ADT fila através de uma lista simplesmente encadeada executa no tempo O(1)

  • A implementação do ADT fila através de uma lista simplesmente encadeada não limita o número de elementos na fila



Passo2: Escolha da representação concreta do TAD Fila (cont.)

  • Representação de uma fila:



Passo2: Escolha da representação concreta do TAD Fila (cont.)

  • public void insere( Object obj );

  • // coloca um novo objecto na final da fila

  • No no = new No( );

  • no.setElemento( obj );

  • no.setProximo( null ); // o no será o novo

  • // no cauda

  • if( estaVazia() )

  • cabeca = no; // caso especial da fila

  • // previamente vazia

  • else

  • cauda.setProximo( no ); // adiciona o no à

  • // cauda da lista

  • cauda = no; // actualiza a referência para o

  • // no cauda

  • tamanho++;

  • }



Passo2: Escolha da representação concreta do TAD Fila (cont.)

  • public Object remove( )

  • throws FilaVaziaException {

  • // Remove o primeiro objecto da fila

  • Object obj;

  • if (estaVazia())

  • throw new FilaVaziaException();

  • obj = cabeca.getElemento( );

  • cabeca = cabeca.getProximo( );

  • tamanho--;

  • if( tamanho == 0 )

  • cauda = null; // a pilha agora está vazia

  • return obj;

  • }



Uso de classe Interna



Classe FilaVaziaExceptions

  • public class FilaVaziaException extends RuntimeException

  • {

  • public FilaVaziaException ()

  • {

  • super(“Fila esta vazia”);

  • }

  • }




Yüklə 445 b.

Dostları ilə paylaş:




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©genderi.org 2022
rəhbərliyinə müraciət

    Ana səhifə