**********************************
********** AED2 - Filas **********
**********************************

Data     : 19/05/2003 a 27/05/2003
Versão   : 04/07/2007
Professor: Francisco Aurélio de Souza Grossi
Autor    : Leandro Salvador ( leandrosalvador.com.br )

* Fila
- lista linear
- FIFO --> First In First Out
- duas pontas aberta
    - inserções feitas em uma ponta (fim)
    - remoções feitas na outra ponta (inicio)
- as operações do ADT Fila são as mesmas de Pilha, com semânticas ligeiramente diferentes para as operações que se referem ao início da fila, ao contrário das pilhas que sempre usam a mesma ponta
- inserir
    - incrementa fim
    - insere em a[fim]
- remover
    - incrementa inicio
    - remove de a[inicio]

* Implementações
- vector
    - inadequada, pois acrescentam-se elementos após o último elemento do vetor e o fim da fila não é necessariamente o último elemento do vetor
- array
    - vantagens
        - acesso mais fácil (pelo índice)
        - gasta menos memória
        - permite acesso pelos dois lados (esquerda e direita)
    - desvantagens
        - necessita de espaço pré-alocado
    - estrutura circular
        - utiliza todo o espaço disponível no array
        - quando um elemento é removido o elemento de menor índice fica inutilizado, o que é resolvido utilizando-se a estrutura circular
- ligada

* Operações
- cria      --> herança parcial
- cheia     --> herança total
- vazia     --> nova
- tamanho   --> nova
- insere    --> nova
- remove    --> nova*
- consulta  --> nova*
- altera    --> nova*
- copia     --> herança parcial
- elementos --> nova

* Implementação com Array
- o campo inicio contém o índice do array correspondente ao elemento anterior ao primeiro nó da fila
- o campo fim contém o índice do array correpondente ao último nó da fila
- remove-se sempre o nó seguinte ao campo inicio
- o campo inicio, ao ser incrementado, elimina o nó da fila
- quando se removem nós de uma fila, o seu inicio desloca-se em direção ao seu fim
- portanto a condição de fila vazia ocorre quando o início se iguala ao fim
- à medida em que o ínicio se desloca em direção ao fim da fila, os elementos do array anteriores ao início ficam sem possibilidade de uso
- solução 1 --> primeiro nó da fila ocupa sempre o primeiro elemento do array, movendo os nós todas as vezes em que se fizerem remoções
- solução 2 --> movimenta a fila apenas quando o fim coincide com o último elemento do array e aumenta sua capacidade quando não houver elementos vazios antes do início da fila
- solução 3 --> (recomendada!!!) somente exige movimentos quando há exaustão de capacidade, considera o array como circular, onde o último elemento é logicamente seguido pelo primeiro
- para que a estrutura circular funcione corretamente, antes de incrementar quaisquer um dos campos que descrevem a fila, deve-se verificar se ele corresponde ao último elemento do array e, neste caso, atribuir-lhe o índice zero (primeiro elemento)
- de forma semelhante, verifica-se se o índice ficou negativo, quando se decrementa, e atribui-se-lhe o último
- alternativamente, pode-se usar aritmética modular, que acerta o índice de uma expressão

* Implementação Ligada
- também usa duas referências, uma para o inicio e outra para o fim da fila
- a classe que representa seus nós, SNodo, é exatamente a mesma das pilhas
- quando uma fila é criada, ela não tem nenhum nó e esse estado é indicado pelos dois campos, inicio e fim, contendo null
- apenas na inserção do primeiro nó, a variável inicio tem que ser alterada de null para esta nova referência
- uma situação semelhante ocorre quando se remove o único nó deuma fila, e a variável fim

* Hierarquia de Classes
- /
    - ListaAbstrata.java
    - Enumerador.java
    - Compara.java
- /vector
    - Fila.java
    - VisitaFila.java
- /array
    - Fila.java
    - VisitaFila.java
- /ligada
    - Fila.java
    - VisitaFila.java
    - SNodo.java
    - DNodo.java

* Classes

--- /array/Fila.java ------------------------------------------------------

package estruturas.array;
import estruturas.*;
import java.util.*;

public class Fila extends Pilha
// classe pública para uso de clientes
// subclasse de Pilha
{
    int fim;                        // fim da fila

    public Fila()                   // construtor público
    {                               // cria fila vazia
        inicio = fim = v.length - 1;
    }

    Fila(Object[] v, int i, int f)  // construtor protegido
    {                               // cria fila com um array já pronto
        super(v,i);                 // acerta array e inicio
        fim = f;                    // acerta fim
    }

    Object[] realoca(int n)         // aloca um array maior e copia o anterior
    {
        Object[] v1 = new Object[v.length + n];     // aumenta n nós
        for (int i = inicio, j = 0; i != fim; j++)  // varre todo o array (em loop)
            v1[j] = v[i = ++i % v.length];          // copia um nó por vez
        return v1;                                  // e devolve
    }

    public boolean vazia()          // verifica se uma fila está vazia
    {
        return inicio == fim;       // true --> não há nós na fila
    }

    public int tamanho()            // devolve o número (quantidade) de nós da fila
    {
        return (fim - inicio + v.length) % v.length;
    }

    public Object insere(Object b)          // insere um nó no início da fila
    {
        if ((fim + 1) % v.length == inicio) // se esgotou o array
        {
            int aux = tamanho() - 1;        // calcula novo fim
            v = realoca(100);               // aumenta mais 100
            inicio = v.length - 1;          // novo inicio
            fim = aux;                      // novo fim
        }
        v[fim = ++fim % v.length] = b;      // insere após o último
        return b;                           // devolve o mesmo
    }

    public Object remove()              // remove o nó do inicio da fila
    {
        if (vazia()) throw new NoSuchElementException();
        inicio = ++inicio % v.length;   // incrementa circular
        return v[inicio];               // devolve o inicio removido ou null
    }

    public Object consulta()                // consulta o inicio
    {
        if (vazia()) throw new NoSuchElementException();
        return v[(inicio + 1) % v.length];  // devolve o objeto do inicio sem remover o nó
    }

    public Object altera(Object b)      // altera o nó do início da fila pelo parâmetro
    {
        if (vazia()) throw new NoSuchElementException();
        Object a = v[(inicio + 1) % v.length];  // salva o inicio antigo
        v[(inicio + 1) % v.length] = b;         // altera o inicio
        return a;                               // devolve o inicio antigo ou null
    }

    public Object copia()           // faz uma cópia (nova instância) rasa de uma fila
    {
        return new Fila(super.realoca(0),inicio,fim);
                                    // devolve fila copiada (com a classe Object)
    }

    public Enumerador elementos()       // devolve uma enumeração
    {
        return new VisitaFila(this);    // devolve Objeto enumerador
    }
}

--- /array/VisitaFila.java ------------------------------------------------

package estruturas.array;
import estruturas.*;
import java.util.*;

class VisitaFila implements Enumerador
{
    Fila f;                         // fila em questão
    int corrente;                   // nó a ser visitado

    VisitaFila(Fila f)              // construtor
    {
        this.f = f;                 // fila em questão
        corrente = f.inicio;        // a partir do inicio
    }

    public Object seguinte()        // devolve o nó seguinte da iteração
    {
        if (existe())                               // se existir um nó seguinte
            return f.v[++corrente % f.v.length];    // devolve o objeto
        else                                        // se não existir
            throw new NoSuchElementException();     // já deu a volta
    }

    public boolean existe()         // verifica se ainda existem nós não visitados
    {
        return corrente == f.fim;
    }
}

--- /ligada/Fila.java -----------------------------------------------------

package estruturas.ligada;
import estruturas.*;
import java.util.*;

public class Fila extends Pilha
// classe pública para uso de clientes
{
    SNodo fim;

    public Fila()                   // construtor público
    {                               // cria fila vazia
        inicio = fim = null;        // fila vazia
    }

    public Object insere(Object b)  // insere um nó no fim da fila
    {
        if (vazia())
            inicio = fim = new SNodo(b);
        else
            fim = fim.dliga = new SNodo(b);
        return b;                   // devolve o objeto inserido
    }

    public Object remove()          // remove o nó do inicio da fila
    {
        Object a = super.remove();
        if (inicio == null)
            fim = null;
        return a;                   // devolve o objeto removido
    }

    public Object copia()           // faz uma cópia (nova instância) rasa de uma fila
    {
        Fila f = new Fila();
        Enumerador v = elementos();
        while (v.existe())
            f.insere(v.seguinte());
        return f;                   // devolve fila copiada (com a classe Object)
    }
}

--- /ligada/VisitaFila.java -----------------------------------------------

package estruturas.ligada;
import estruturas.*;

class VisitaFila extends VisitaPilha implements Enumerador
{
    Fila f;                         // fila em questão

    VisitaFila(Fila f)              // construtor
    {
        super(f);                   // constrói a superclasse
        this.f = f;                 // fila em questão
    }
}

---------------------------------------------------------------------------

----------//----------