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

• 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”);

• }

• }