*********************************** ********** AED2 - Deques ********** *********************************** Data : 23/05/2003 a 27/05/2003 Versão : 04/07/2007 Professor: Francisco Aurélio de Souza Grossi Autor : Leandro Salvador ( leandrosalvador.com.br ) * Deque - lista linear - FIFO --> First In First Out - duas pontas aberta - inserções feitas em qualquer ponta - remoções feitas em qualquer ponta * Implementações - array --> deve usar um array circular - vector --> - ligada --> * Operações - insere - remove - consulta - altera - elementos * Implementação com Array - algumas operações do ADT Deque têm que ser alteradas para contemplar as possibilidades de remoção, inserção, consulta, alteração e enumeração em ambas as pontas - para isso, estas operações usam um parâmetro inteiro adicional que indica a ponta a ser considerada - os dois possíveis valores deste parâmetro são definidos como constantes (INICIO e FIM) na classe Deque - como as assinaturas dos novos métodos não são iguais aos da superclasse, estamos fazendo sobrecargas dos métodos e não substituições - em outras palavras, todas as operações da superclasse (sem o parâmetro inteiro adicional) continuam disponíveis - por exemplo, remove() é sinônimo de remove(Deque.INICIO) - interfaces nada mais são do que classes totalmente abstratas; portanto, tal como as classes, também podem fazer parte de uma hierarquia * Implementação Ligada --> PAREI AQUI!!! * Hierarquia de Classes - / - DequeAbstrata.java - Enumerador.java - Compara.java - /vector - Deque.java - VisitaDeque.java - /array - Deque.java - VisitaDeque.java - /ligada - Deque.java - VisitaDeque.java - SNodo.java - DNodo.java * Classes --- /DequeAbstrata.java --------------------------------------------------- package estruturas; public interface DequeAbstrata extends ListaAbstrata { public abstract Object insere(Object b, int ponta); // insere um nó em uma ponta public abstract Object remove(int ponta); // remove o nó de uma ponta public abstract Object consulta(int ponta); // consulta o nó de uma ponta public abstract Object altera(Object b, int ponta); // substitui o nó de uma ponta public abstract Enumerador elementos(int ponta); // devolve uma enumeração a partir de uma ponta } --- /array/Deque.java ----------------------------------------------------- package estruturas.array; import estruturas.*; import java.util.*; public class Deque extends Fila // classe pública para uso de clientes // subclasse de Fila { public final static int INICIO = 0; // começa no inicio public final static int FIM = 1; // começa no fim public Deque() // construtor público { // cria deque vazia super(); } Deque(Object[] v, int i, int f) // construtor protegido { // cria deque com um array já pronto super(v,i,f); // acerta array, inicio e fim } public Object insere(Object b, int ponta) // insere um nó em uma das pontas { if (ponta == FIM) return insere(b); if ((fim + 1) % v.length == inicio) // se esgotou o array realoca(100); // aumenta mais 100 v[inicio] = b; // insere inicio = (inicio - 1 + v.length) % v.length; // decrementa return b; // devolve o objeto inserido } public Object remove(int ponta) // remove o nó de uma das pontas { if (vazia()) throw new NoSuchElementException(); if (ponta == INICIO) return remove(); Object a = v[fim]; fim = (fim - 1 + v.length) % v.length; // decrementa return a; // devolve o objeto removido ou null } public Object consulta(int ponta) // consulta o nó de uma das pontas { if (vazia()) throw new NoSuchElementException(); if (ponta == INICIO) return consulta(); return v[fim]; // devolve o objeto do fim sem remover o nó } public Object altera(Object b, int ponta) // altera o nó de uma das pontas pelo parâmetro { if (vazia()) throw new NoSuchElementException(); if (ponta == INICIO) return altera(b); Object a = v[fim]; // salva o fim antigo v[fim] = b; // altera o fim return a; // devolve o fim antigo ou null } public Object copia() // faz uma cópia (nova instância) rasa de uma deque { return (Object) new Deque(realoca(0), v.length - 1, tamanho() - 1); // devolve deque copiada (com a classe Object) } public Enumerador elementos(int ponta) // devolve uma enumeração a partir de uma ponta { return new VisitaDeque(this, ponta); // devolve objeto Enumerador } } --- /array/VisitaDeque.java ----------------------------------------------- package estruturas.array; import estruturas.*; import java.util.*; class VisitaDeque implements Enumerador { Deque q; // deque em questão int ponta; // ponta desejada int corrente; // nó a ser visitado VisitaDeque(Deque q, int p) // construtor { this.q = q; // deque em questão this.ponta = p; // ponta desejada if (p == Deque.INICIO) // se escolhe a ponta INICIO corrente = q.inicio; // a partir do inicio else // senão escolhe a ponta FIM corrente = q.fim; // a partir do fim } public Object seguinte() // devolve o nó seguinte da iteração { Object a = q.v[corrente]; if (existe()) // se existir um nó seguinte { if (ponta == Deque.INICIO) a = q.v[corrente = ++corrente % q.v.length]; else corrente = (--corrente + q.v.length) % q.v.length; return a; } else // se não existir throw new NoSuchElementException(); // já deu a volta } public boolean existe() // verifica se ainda existem nós não visitados { if (ponta == Deque.INICIO) return corrente != q.fim; else return corrente != q.inicio; } } --- /ligada/Deque.java ---------------------------------------------------- package estruturas.ligada; import estruturas.*; import java.util.*; public class Deque implements DequeAbstrata // classe pública para uso de clientes { public final static int INICIO = 0; // começa no inicio public final static int FIM = 1; // começa no fim int quantidade; // número de nós DNodo cabeça; // cabeça de lista public Deque() // construtor público { // cria deque vazia cabeça = new DNodo(); // cabeça da lista cabeça.eliga = cabeça.dliga = cabeça; // ligações quantidade = 0; // número de nós } public boolean cheia() // verifica se uma deque está cheia { return false; } public boolean vazia() // verifica se uma deque está vazia { return cabeça == cabeça.dliga; } public int tamanho() // devolve o número (quantidade) de nós da deque { return quantidade; } public Object insere(Object b, int p) // insere um nó em uma ponta da deque { if (p == INICIO) // se quer inserir no primeiro nó { DNodo novo = new DNodo(cabeça, b, cabeça.dliga); cabeça.dliga = cabeça.dliga.eliga = novo; } else // se quer inserir no último nó { DNodo novo = new DNodo(cabeça.eliga, b, cabeça); cabeça.eliga = cabeça.eliga.dliga = novo; } quantidade++; return b; } public Object remove(int p) // remove o nó de uma ponta da deque { if (vazia()) throw new NoSuchElementException(); DNodo ref; // temporário if (p == INICIO) ref = cabeça.dliga; // removido inicio else ref = cabeça.eliga; // removido fim cabeça.oinfo = ref.oinfo; // salva na cabeça ref.eliga.dliga = ref.dliga; // acerta direita ref.dliga.eliga = ref.eliga; // acerta esquerda quantidade--; // menos um na deque return cabeça.oinfo; // devolve objeto } public Object consulta(int p) // consulta o nó de uma ponta sem remover { if (vazia()) throw new NoSuchElementException(); if (p == INICIO) return cabeça.dliga.oinfo; else return cabeça.eliga.oinfo; } public Object altera(Object b, int p) // altera o nó de uma ponta pelo parâmetro { if (vazia()) throw new NoSuchElementException(); if (p == INICIO) // se quer alterar o primeiro nó { cabeça.oinfo = cabeça.dliga.oinfo; // salva a ponta antiga na cabeça cabeça.dliga.oinfo = b; // altera a ponta } else // se quer alterar o último nó { cabeça.oinfo = cabeça.eliga.oinfo; // salva a ponta antiga na cabeça cabeça.eliga.oinfo = b; // altera a ponta } return cabeça.oinfo; // devolve a ponta antiga ou null } public Object copia() // faz uma cópia (nova instância) rasa de uma deque { Deque q = new Deque(); Enumerador v = elementos(INICIO); while (v.existe()) q.insere(v.seguinte(),FIM); return q; } public Enumerador elementos(int p) // devolve uma enumeração a partir de uma ponta { return new VisitaDeque(this, p); // devolve Objeto enumerador } } --- /ligada/VisitaDeque.java ---------------------------------------------- package estruturas.ligada; import estruturas.*; import java.util.*; class VisitaDeque implements Enumerador { int sentido; // sentido desejado Deque q; // a deque em questão DNodo corrente; // nó a ser visitado VisitaDeque(Deque q, int sentido) // construtor { // indica o primeiro nó this.sentido = sentido; this.q = q; // deque em questão if (sentido == Deque.INICIO) // se INICIO escolhido corrente = q.cabeça.dliga; // começa a partir da direita da cabeça else // se FIM escolhido corrente = q.cabeça.eliga; // começa a partir da esquerda da cabeça } public Object seguinte() // devolve o nó seguinte da iteração { if (existe()) { q.cabeça.oinfo = corrente.oinfo;// salva na cabeça if (sentido == Deque.INICIO) // se sentido for INICIO corrente = corrente.dliga; // pega o nó seguinte else // se sentido for FIM corrente = corrente.eliga; // pega o nó anterior return q.cabeça.oinfo; // devolve o objeto } else throw new NoSuchElementException(); // deu a volta } public boolean existe() // verifica se ainda existem nós não visitados { return corrente != q.cabeça; } } --- /ligada/DNodo.java ---------------------------------------------------- package estruturas.ligada; class DNodo // nó com duas ligações { protected DNodo eliga; // ligação esquerda protected Object oinfo; // informação do cliente protected DNodo dliga; // ligação direita DNodo() // cria um nó vazio { this(null,null,null); // objeto e ligações null } DNodo(Object oinfo) // cria um nó apenas com a informação { this(null,oinfo,null); // ligações null } DNodo(DNodo eliga, Object oinfo, DNodo dliga) { // cria um nó com informação e ligações this.eliga = eliga; // ligação esquerda this.oinfo = oinfo; // objeto do cliente this.dliga = dliga; // ligação direita } } --------------------------------------------------------------------------- ----------//----------