***********************************
********** AED2 - Pilhas **********
***********************************

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

* Pilha
- lista linear
- FILO --> First In Last Out
- uma ponta aberta
    - fazem todas as inserções
    - se removem quaisquer nós
- array é a estrutura básica ideal para implementação de pilhas
- nós são objetos da classe cósmica Object
- elementos do vetor contêm referências que podem apontar áreas dinâmicas distintas ou comuns a outros elementos

* Implementações
- vector --> evita problemas usando composição ao invés de herança
- array  --> tem vantagens em relação a vetores e deve ser a preferida
- ligada --> evita os movimentos dos nós quando as estruturas têm que crescer

* Operações
- cria      --> cria uma pilha vazia
- cheia     --> verifica se a pilha está cheia
- vazia     --> verifica se a pilha está vazia
- tamanho   --> devolve a quantidade de nós
- insere    --> insere um nó no topo
- remove    --> remove o nó do topo
- consulta  --> consulta o nó do topo sem removê-lo
- altera    --> substitui o nó do topo
- copia     --> devolve uma cópia rasa da pilha
- elementos --> devolve uma enumeração dos nós

* Interface
- não é obrigatório, mas recomendado
- descreve as operações do ADT
- obriga as implementações a incluir todos os métodos
- documenta as operações disponíveis para os usuários

* Implementação com Vetores
- não é tão eficiente para acessar os nós quanto a implementação feita com arrays
- vantagem de usar métodos já existentes da classe Vector
- a estrutura dinâmica da linguagem Java faz a maior parte do trabalho
- lado fechado da pilha --> elemento de índice "zero" do vetor
- a pilha cresce em direção ao fim do vetor
- índice do topo é o tamanho do vetor (length)
- quantidade de nós é o tamanho corrente do vetor
- a pilha, conceitualmente, nunca fica cheia, pois as estruturas são dinâmicas e podem crescer enquanto houver memória disponível no sistema
- para inserir um nó na pilha basta acrescentá-lo ao fim do vetor

* Implementação com Array
- é mais eficiente do que a implementação feita com arrays porque o acesso aos elementos de um array é mais direto e eficiente
- desvantagem de ser um pouco mais trabalhosa, pois o array tem que ser realocado por programa
- deve ser a preferida em relação à implementação com vetor
- o campo corrente começa com o valor do topo e indica a posição (índice do array) do nó visitado
- para cada chamada do método a posição corrente é decrementada até ser negativa

* Implementação Ligada
- vantagem de evitar os movimentos dos nós que inevitavelmente acontecem quando as estruturas seqüênciais que armazenam os nós (vetor ou array) têm que crescer
- a relação entre os nós é feita através de referências contidas nos nós da lista
- os objetos são sempre dinâmicos
- não é necessário movimentar os objetos, uma vez que com essas ligações não há exigência de contigüidade
- a criação de uma pilha é implementada por um construtor que simplesmente atribui o valor null ao topo da pilha
- de forma semelhante à implementação com arrays, precisamos de uma variável de instância inicio, da classe SNodo, para apontar o topo da pilha
- não há necessidade de espaço reservado previamente, pois os nós são criados dinamicamente no momento da inserção
- para saber o tamanho da pilha temos que percorrê-la inteira para contar os nós
- deve-se criar uma variável de instância para armazenar o número de nós
    - zerada na criação
    - incrementada na inserção
    - decrementada na remoção
- a pilha está vazia quando não houver nós na pilha, ou seja, quando o seu topo contiver null
- para inserir um novo nó na pilha
    - criação de um novo nós e atribuição de 9 ao seu campo oinfo
    - atribuição do topo anterior ao campo dliga
    - atribuição desta referência à variável inicio (topo)
    - devolução do objeto inserido
- para remover um nó da pilha
    - salvamento temporário do campo oinfo do incio (9, no exemplo)
    - atribuição do campo dliga do topo ao topo
    - devolução do campo oinfo salvo no primeiro passo
- classe SNodo
    - além da classe que descreve a pilha, a implementação ligada usa a classe SNodo para os nós
    - também usada para filas, deques e listas genéricas
    - representa a estrutura dinâmica dos nós
    - tem duas variáveis de instância
        - oinfo --> informação do cliente
        - dliga --> faz a ligação com o nó vizinho
    - tanto a classe como as variáveis de instância têm uso restrito, pois os usuários não precisam acessá-las diretamente
    - a definição de vários construtores dão flexibilidade às classes que criam nós dinâmicos

* Desempenho
- OPERAÇÃO  VETOR   ARRAY   LIGADA
  cria      O(1)    O(1)    O(1)
  destrói   O(1)    O(1)    O(1)
  vazia     O(1)    O(1)    O(1)
  tamanho   O(1)    O(1)    O(n)    --> desvantagem ligada
  insere    O(n)    O(n)    O(1)    --> vantagem ligada
  remove    O(1)    O(1)    O(1)
  consulta  O(1)    O(1)    O(1)
  altera    O(1)    O(1)    O(1)
  cópia     O(n)    O(n)    O(n)
- para evitar a complexidade linear da operação tamanho na alocação ligada, cria-se uma variável de instância
        - zerada na criação
        - incrementada na inserção
        - decrementada na remoção

* Classe Padrão Stack
- AbstractList --> Vector --> Stack
- implementa uma pilha com seis operações
- cria
    - public Stack()
    - cria uma nova instância de uma pilha e devolve uma pilha vazia
    - usa o construtor padrão da classe Vector
    - cria um vetor vazio
    - quando o vetor precisar crescer ele dobra de tamanho
- vazia
    - public boolean empty()
    - pilha vazia --> true
    - pilha não vazia --> false
- insere
    - public Object push(Object item)
    - insere (empilha) um novo item no topo da pilha
    - devolve o mesmo objeto empilhado
- remove
    - public Object pop()
    - remove (desempilha) o objeto do topo da pilha e o devolve
    - se a pilha estiver vazia --> exceção EmptyStackException
- consulta
    - public Object peek()
    - devolve o objeto do topo sem removê-lo da pilha
    - se a pilha estiver vazia --> exceção EmptyStackException
- pesquisa
    - public int search(Object item)
    - devolve o índice do primeiro objeto encontrado igual ao parâmetro
    - considera o topo como tendo índice "um"
    - a igualdade é polimorficamente testada com o método equals()
    - se o objeto não existir --> devolve -1

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

* Classes

--- /Compara.java ---------------------------------------------------------

package estruturas;

public interface Compara
{
    public abstract boolean igual(Compara c);
    public abstract boolean maior(Compara c);
    public abstract boolean menor(Compara c);
}

--- /Enumerador.java ------------------------------------------------------

package estruturas;

public interface Enumerador
{
    public abstract Object seguinte(); // retorna o nó seguinte da enumeração
    public abstract boolean existe();  // verifica se ainda existem nós não visitados
}

--- /ListaAbstrata.java ---------------------------------------------------

package estruturas;

public interface ListaAbstrata
{
    public abstract boolean cheia();         // verifica se uma lista está cheia
    public abstract boolean vazia();         // verifica se uma lista está vazia
    public abstract int tamanho();           // devolve o número de nós
    public abstract Object insere(Object o); // insere um nó na lista
    public abstract Object remove();         // remove um nó da lista
    public abstract Object consulta();       // consulta um nó da lista
    public abstract Object altera(Object o); // substitui um nó da lista
    public abstract Object copia();          // devolve uma cópia rasa da lista
    public abstract Enumerador elementos();  // devolve uma enumeração para os nós
}

--- /vector/Pilha.java ----------------------------------------------------

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

public class Pilha implements ListaAbstrata
// classe pública para uso de clientes
{
    Vector v;                       // armazenamento

    public Pilha()                  // construtor público
    {                               // cria pilha vazia
        v = new Vector(100,100);    // aloca com 100 nós
    }

    private Pilha(Object v)         // construtor privado
    {                               // cria pilha com um vetor já pronto
        this.v = (Vector) v;        // usado na cópia
    }

    public boolean cheia()          // verifica se uma pilha está cheia
    {
        return false;               // a pilha nunca fica cheia
    }

    public boolean vazia()          // verifica se uma pilha está vazia
    {
        return v.size() == 0;       // true --> não há nós na pilha
    }

    public int tamanho()            // devolve o número (quantidade) de nós da pilha
    {
        return v.size();            // devolução
    }

    public Object insere(Object b)  // insere um nó no topo da pilha
    {
        v.addElement(b);            // insere após o último
        return b;                   // devolve o objeto inserido
    }

    public Object remove()              // remove o nó do topo da pilha
    {
        if (vazia()) throw new NoSuchElementException();
        Object a = v.lastElement();     // salva o topo antigo
        v.removeElementAt(v.size()-1);  // elimina o topo antigo
        return a;                       // devolve o topo removido ou null
    }

    public Object consulta()        // consulta o topo
    {
        if (vazia()) throw new NoSuchElementException();
        return v.lastElement();     // devolve o objeto do topo sem remover o nó
    }

    public Object altera(Object b)      // altera o nó do topo da pilha pelo parâmetro
    {
        if (vazia()) throw new NoSuchElementException();
        Object a = v.lastElement();     // salva o topo antigo
        v.setElementAt(b,v.size()-1);   // altera o topo;
        return a;                       // devolve o topo antigo ou null
    }

    public Object copia()            // faz uma cópia (nova instância) rasa de uma pilha
    {
        return new Pilha(v.clone()); // devolve pilha copiada (com a classe Object)
    }

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

--- /vector/VisitaPilha.java ----------------------------------------------

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

class VisitaPilha implements Enumerador
{
    Pilha p;                        // pilha em questão
    int corrente;                   // nó a ser visitado

    VisitaPilha(Pilha p)            // construtor
    {
        this.p = p;                 // pilha em questão
        corrente = p.v.size();      // a partir do topo
    }

    public Object seguinte()        // devolve o nó seguinte da iteração
    {
        if (existe())                               // se existir um nó seguinte
            return p.v.elementAt(--corrente);       // 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 > 0;
    }
}

--- /array/Pilha.java -----------------------------------------------------

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

public class Pilha implements ListaAbstrata
// classe pública para uso de clientes
{
    Object[] v;                     // armazenamento
    int inicio;                     // índice do topo

    public Pilha()                  // construtor público
    {                               // cria pilha vazia
        v = new Object[100];        // aloca com 100 nós
        inicio = -1;                // inicializa topo
    }

    Pilha(Object[] v, int inicio)   // construtor protegido
    {                               // cria pilha com um array já pronto
        this.v = v;                 // usado na cópia
        this.inicio = inicio;       // acerta topo
    }

    public void destroi()           // destrói a estrutura
    {
        inicio = -1;                // faz ficar vazia
    }

    Object[] realoca(int n)         // aloca um array maior e copia o anterior
    {
        Object[] v1 = new Object[v.length+n];   // aumenta n nós
        System.arraycopy(v,0,v1,0,v.length);    // copia o antigo
        return v1;                              // e devolve
    }

    public boolean cheia()          // verifica se uma pilha está cheia
    {
        return false;               // a pilha nunca fica cheia
    }

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

    public int tamanho()            // devolve o número (quantidade) de nós da pilha
    {
        return inicio + 1;          // devolução
    }

    public Object insere(Object b)  // insere um nó no topo da pilha
    {
        if (inicio == v.length - 1) // se esgotou o array
            v = realoca(100);       // aumenta mais 100
        v[++inicio] = b;            // insere após o último
        return b;                   // devolve o objeto inserido
    }

    public Object remove()          // remove o nó do topo da pilha
    {
        if (vazia()) throw new NoSuchElementException();
        return v[inicio--];         // devolve o topo removido ou null
    }

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

    public Object altera(Object b)  // altera o nó do topo da pilha pelo parâmetro
    {
        if (vazia()) throw new NoSuchElementException();
        Object y = v[inicio];       // salva o topo antigo
        v[inicio] = b;              // altera o topo
        return y;                   // devolve o topo antigo ou null
    }

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

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

--- /array/VisitaPilha.java -----------------------------------------------

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

class VisitaPilha implements Enumerador
{
    Pilha p;                        // pilha em questão
    int corrente;                   // nó a ser visitado

    VisitaPilha(Pilha p)            // construtor
    {
        this.p = p;                 // pilha em questão
        corrente = p.inicio;        // a partir do topo
    }

    public Object seguinte()        // devolve o nó seguinte da iteração
    {
        if (existe())                               // se existir um nó seguinte
            return p.v[corrente--];                 // 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 >= 0;
    }
}

--- /ligada/Pilha.java ----------------------------------------------------

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

public class Pilha implements ListaAbstrata
// classe pública para uso de clientes
{
    SNodo inicio;

    public Pilha()                  // construtor público
    {                               // cria pilha vazia
        inicio = null;              // pilha vazia
    }

    private Pilha(SNodo no)         // construtor privado
    {                               // cria pilha a partir de uma referência
        inicio = no;                // a partir deste nó
    }

    public boolean cheia()          // verifica se uma pilha está cheia
    {
        return false;               // a pilha nunca fica cheia
    }

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

    public int tamanho()            // devolve o número (quantidade) de nós da pilha
    {
        int n = 0;                  // contador
        for (SNodo s = inicio; s != null; n++) s = s.dliga;
        return n;                   // devolução
    }

    public Object insere(Object b)      // insere um nó no topo da pilha
    {
        inicio = new SNodo(b,inicio);   // cria novo nó no topo
        return b;                       // devolve o objeto inserido
    }

    public Object remove()              // remove o nó do topo da pilha
    {
        if (vazia()) throw new NoSuchElementException();
        Object removido = inicio.oinfo; // salva o topo antigo
        inicio = inicio.dliga;          // elimina topo antigo
        return removido;                // devolve o topo removido ou null
    }

    public Object consulta()        // consulta o topo
    {
        if (vazia()) throw new NoSuchElementException();
        return inicio.oinfo;        // devolve o objeto do topo sem remover o nó
    }

    public Object altera(Object b)  // altera o nó do topo da pilha pelo parâmetro
    {
        if (vazia()) throw new NoSuchElementException();
        Object a = inicio.oinfo;    // salva o topo antigo
        inicio.oinfo = b;           // altera o topo
        return a;                   // devolve o topo antigo ou null
    }

    public Object copia()           // faz uma cópia (nova instância) rasa de uma pilha
    {
        if (vazia()) return new Pilha();
        Pilha p = (Pilha) (new Pilha(inicio.dliga)).copia();
        p.inicio = new SNodo(inicio.oinfo,p.inicio);
        return p;                   // devolve pilha copiada (com a classe Object)
    }

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

--- /ligada/VisitaPilha.java ----------------------------------------------

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

class VisitaPilha implements Enumerador
{
    Pilha p;                        // pilha em questão
    SNodo corrente;                 // nó a ser visitado

    VisitaPilha(Pilha p)            // construtor
    {
        this.p = p;                 // pilha em questão
        corrente = p.inicio;        // a partir do topo
    }

    public Object seguinte()        // devolve o nó seguinte da iteração
    {
        if (existe())                   // se existir um nó seguinte
        {
            Object b = corrente.oinfo;  // salva visitado
            corrente = corrente.dliga;  // próximo nó
            return b;                   // devolve o objeto
        }
        else throw new NoSuchElementException(); // deu a volta
    }

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

--- /ligada/SNodo.java ----------------------------------------------------

package estruturas.ligada;

class SNodo                         // nó com uma ligação simples
{
    protected Object oinfo;         // informação do cliente
    protected SNodo  dliga;         // liga com o próximo nó

    SNodo()                         // cria um nó vazio
    {
        this(null, null);           // objeto e ligação null
    }

    SNodo(Object oinfo)             // cria um nó apenas com a informação
    {
        this(oinfo, null);          // ligação null
    }

    SNodo(Object oinfo, SNodo dliga)// cria um nó com informação e ligação
    {
        this.oinfo = oinfo;         // objeto do cliente
        this.dliga = dliga;         // ligação
    }
}

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

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