TAD Sequência com Arranjo Circular

Implemente o TAD sequência baseado em um arranjo variável usado de forma circular de maneira que as inserções no início e no fim da sequência executem em tempo constante.

Classes:

Posição:

public class Posicao
{
// indice no vetor
private int indice;

// referencia para o elemento
private Object elemento;

// construtor
public Posicao(int indice, Object elemento)
{
this.indice = indice;
this.elemento = elemento;
}

// retorna indice
public int index()
{
return indice;
}

// retorna elemento
public Object element()
{
return elemento;
}
}

Interador:

public class Iterador
{
// armazena elementos
private Posicao[] elementos;

// controla posicao no array
private int pos;

// construtor
public Iterador(Posicao[] elementos)
{
this.elementos = elementos;
pos = 0;
}

// retorna objeto corrente do array
public Posicao object()
{
return elementos[pos];
}

// verifica se tem proximo elemento
public boolean hasNext()
{
if(pos == elementos.length)
return false;

return true;
}

// move para o proximo elemento
public Posicao nextObject()
{
if(hasNext())
return elementos[pos++];

return null;
}

// volta ao começo
public void reset()
{
pos = 0;
}
}

Sequência:

public class Sequencia
{
// no. max. de elementos
private final int MAX_ELEMENTOS = 100;

// array de posicoes
private Posicao[] sequencia;

// variaveis de controle
private int first;
private int last;
private int N;

// construtor
public Sequencia()
{
sequencia = new Posicao[MAX_ELEMENTOS];
first = 0;
last = 0;
N = MAX_ELEMENTOS;
}

// insere elemento na primeira posicao
public void insertFirst(Object o)
{
// calcula possivel indice
int pos = first - 1;

// verifica se menor que limite
if(pos < 0)
pos = N - 1; // circular

// verifica se sequencia esta cheia
if(pos == last)
{
aumentar();
// chama funcao novamente apos aumentar
insertFirst(o);
}
else
{
// cria nova posicao
Posicao posicao = new Posicao(pos, o);

// insere na posicao candidata
sequencia[pos] = posicao;
// atualiza indice da primeira posicao
first = pos;
}
}

// insere elemento na ultima posicao
public void insertLast(Object o)
{
// cria nova posicao
Posicao posicao = new Posicao(last, o);

// insere na ultima posicao
sequencia[last] = posicao;

int pos;

// atualiza indice da ultima posicao
pos = (last + 1) % N;

// verifica se sequencia esta cheia
if(pos == first)
aumentar();
else
last = pos; // atualiza indice da ultima posicao
}

// duplica tamanho da sequencia
public void aumentar()
{
// cria nova sequencia com dobro do tamanho
Posicao[] temp = new Posicao[2*sequencia.length];

// contadores auxiliares
int pos = first;
int i = 0;

// copia todos os elementos para nova sequencia
while(pos != last)
{
temp[i] = new Posicao(i, sequencia[pos].element());
i++;
pos = (pos + 1) % N;
}

// atualiza indices
first = 0;
last = i;
sequencia = temp;
N = sequencia.length;
}

public int size()
{
return (N - first + last) % N;
}

public Iterador elements()
{
// cria array de elementos a serem retornados
Posicao[] elementos = new Posicao[size()];

// contadores auxiliares
int pos = first;
int i = 0;

// copia todos os elementos para array de saida
while(pos != last)
{
elementos[i] = sequencia[pos];
i++;
pos = (pos + 1) % N;
}

// cria iterador auxiliar e passa elementos
Iterador iterador = new Iterador(elementos);

// retorna iterador
return iterador;
}

// insere elemento antes de posicao p
public void insertBefore(Posicao p, Object o)
{
// indice para ultima posicao (valor corrente)
int pos = last;

// desloca todos os elementos depois de p
do
{
sequencia[pos] = new Posicao(pos, sequencia[pos-1].element());
pos--;

// verifica limite inferior
if(pos < 0)
pos = N-1;
}
while(pos > p.index());

// insere novo elemento
sequencia[pos] = new Posicao(pos, o);

// atualiza indice para ultimo elemento
last = (last + 1) % N;

// verifica necessidade de crescimento
if(size() == N)
aumentar();
}

}

Testa Sequência:

public class SequenciaApp
{
public static void main(String args[])
{
Posicao p = null;
Iterador it;
Sequencia seq = new Sequencia();

seq.insertLast("Bola");
seq.insertLast("Caixa");
seq.insertLast("Chave");
seq.insertFirst("Lapis");

it = seq.elements();
while(it.hasNext())
{
p = it.nextObject();
System.out.println((String)p.element());
}

seq.insertBefore(p, "Controle Remoto");
System.out.println();

it = seq.elements();
while(it.hasNext())
{
p = it.nextObject();
System.out.println((String)p.element());
}
}
}