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 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 // 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 // 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 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 }
Uso de classe Interna
Classe FilaVaziaExceptions public class FilaVaziaException extends RuntimeException { public FilaVaziaException () { super(“Fila esta vazia”); } }
Dostları ilə paylaş: |