JAVA – Fila
ATAI
1
Teória de Tipos de Dados Abstractos
1.
Definição de TAD
 Especificar as propriedades fundamentais de um tipo de dado,
de um modo independente da sua implementação numa
linguagem.
2.
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
2
Definição de TAD Fila
3
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).
4
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

5
Exemplo de execução numa fila F
Operação
Saída
F
insere(5)
-
(5)
insere(3)
-
(5,3)
remove( )
5
(3)
insere(7)
-
(3,7)
remove( )
3
(7)
inicio( )
7
(7)
remove( )
7
()
remove( )
"erro"
()
estaVazia( )
Verdade
()
insere(9)
-
(9)
insere(7)
-
(9,7)
tamanho( )
2
(9,7)
insere(3)
-
(9,7,3)
insere(5)
-
(9,7,3,5)
remove( )
9
(7,3,5)
6
Implementação de TAD Fila
7
Passo1: Definição da Interface Fila
public interface Fila {
// Métodos de acesso
public int tamanho( );
public boolean estaVazia( );
public Object inicio( )
throws FilaVaziaException;
//
//
//
//
//
//
//
Retorna o número de
elementos na fila
Vê se a fila
está vazia
Retorna o elemento
do início se a fila
não está vazia
// Métodos de atualização
public void insere( Object elemento )
throws FilaCheiaException;
public Object remove( )
//
throws FilaVaziaException; //
//
//
//
// Insere um
// elemento
// na fila
Retorna e remove o
elemento do inicio
da fila se
chamado com a
fila não vazia
}
8
Implementação de TAD Fila
Passo 2
(com a utilização da estrutura estática)
9
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)
10
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):
7
6
1
5
2
4
0
1
2
3
4
5
6
0
3
7
11
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
12
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- arrayfora-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
f para (f+1) mod N
e
13
Passo2: Escolha da representação concreta do
TAD (cont)
configuração "normal" da fila
configuração wrapped around da fila
14
Passo2: Escolha da representação concreta
do TAD (cont)

Animação (com maxlen = 6):
After
Initially:
adding Martin:
removing
Maggie:
Ralph:
Nelson:
Homer,
the front
Marge,
element:
Bart, Lisa:
0
1
2
elems Nelson
Homer Martin
Marge Bart
front
0
1
2
3
rear
21054
3
4
5
Lisa Maggie Ralph
length
56430
15
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
16
Passo2: Escolha da representação concreta do
TAD Fila (algoritmo)
Algoritmo tamanho( ):
retorna (N - i + f) mod N
Algoritmo estaVazia( ):
Algoritmo remove( ):
se estaVazia( ) então
lança FilaVaziaException
temp <- F[ i ]
F[ i ] <- null
i <- ( i + 1 ) mod N
retorna temp
retorna i = f
Algoritmo inicio( ):
se estaVazia( ) então
lança FilaVaziaException
Algoritmo insere( o ):
se tamanho( ) = N -1 então
lança FilaCheiaException
F[ f ] <- o
f <-( f + 1 ) mod N
retorna F[ i ]
mod em Java: %
17
Implementação de TAD Fila
Passo 2
(com a utilização da estrutura dinâmica)
(lista simplesmente ligada)
18
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
19
Passo2: Escolha da representação concreta do
TAD Fila (cont.)

Representação de uma fila:
fila:
i
f
fila
Vazia:
i
f
Ilustração:
i
f
element
Homer
element
Marge
element
Bart
Lisa
20
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++;
}
21
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;
}
22
Uso de classe Interna
public class FilaDinamica implements Fila{
private No cabeca;
private No cauda;
private class No { Object elemento; No proximo; }
public int tamanho( ){return 0;}
public boolean estaVazia( ) { return (cabeca == null);}
public void insere( Object e ){
No aux = new No();
aux.elemento =e;
aux.proximo = null;
if (estaVazia() ) { cabeca = aux; cauda = aux;}
else { cauda.proximo = aux; cauda =aux;}
}
public Object remove( ){
23
Classe FilaVaziaExceptions
public class FilaVaziaException extends RuntimeException
{
public FilaVaziaException ()
{
super(“Fila esta vazia”);
}
}
24