miércoles, 23 de enero de 2008

Implementación de una Cola en lenguaje JAVA (Extraer, Primero, Siguiente, Concatenar, Insertar)

El objetivo será implementar un tipo abstracto de datos que implemente una cola de espera genérica, dentro de las posibilidades del lenguaje Java, el cual, por ejemplo, en comparación con los lenguajes C++ o Ada, no dispone de estructuras sintácticas análogas al template o generic.

El diseño aquí propuesto contempla una clase principal Cola, que gestiona una cola compuesta de elementos de la clase Nodo. Los objetos de esta última clase contendrán objetos "genéricos", cuya clase el programador concretará, al usar el TAD, en función de sus necesidades. Se propone pues la siguiente implementación:

* Clase Nodo. Como se ha indicado, dispondrá de un campo (private), que será de la clase Object, lo que permitirá contener cualquier tipo de objeto (pues en Java toda clase se considera derivada de la clase Object). Contendrá asimismo un enlace protected que apunte al siguiente nodo de la cola. Desde fuera de la clase (o derivada) sólo será accesible el método dato(), que devuelve el objeto de dato que contiene. En definitiva, la clase Nodo nos servirá como tipo iterador, esto es, nos permitirá declarar objetos de esta clase en los que apoyarnos para recorrer una cola sin destruirla.
* Clase Cola. En el momento de la creación, se especificará el número máximo de elementos que puede contener la cola. Inicialmente, la cola estará vacía. Esta clase suministra los siguientes métodos:
o insertar(Object). Construye un Nodo con el objeto de dato pasado como parámetro (no se admite null), y lo inserta como nuevo último elemento de la cola.
o extraer(). Devuelve el dato asociado al primer elemento de la cola. Dicho primer elemento se extrae de la cola.
o primero(). Devuelve el primer Nodo de la cola, pero no lo extrae. La cola no se ve pues alterada.
o siguiente(Nodo). Método static que devuelve el elemento de la cola situado a continuación del elemento pasado como parámetro. Con este método podemos recorrer la cola desde primero().
o concatenar(Cola). Añade la cola pasada como parámetro a la cola sobre la que se aplica, a partir del último elemento de ésta. Si se realiza con éxito la operación, la cola pasada como parámetro quedará vacía, si no, ninguna de las dos colas se ve alterada.

Constrúyase asimismo una rutina main de prueba. Para ello puede utilizarse, por ejemplo, la clase String como clase de objetos que se almacenarán en el campo de datos dentro de Nodo. La rutina main creará, añadirá y extraerá distintos nodos a dos colas, cuyas ristras se visualizarán por pantalla, así como el resultado de su concatenación.



class Nodo extends Object{
protected Nodo Sig;
private Object Info;
public Nodo(Object E) { Sig = null ;Info = E;}
public Object dato() { return Info; }
}

class Cola extends Object {

private int Maximo; // Almacenarà el numero maximo de elementos a almacenar
private int NElementos; // Almacenarà el numero de elementos almacenados por el momento
private Nodo Primero; // Almacenarà el enlace al primer nodo a salir de la cola.

public Cola(int max) {
Maximo = max;
NElementos = 0;
Primero = null;
}
void insertar(Object E){
Nodo n;
if (Maximo > NElementos)
{
if (Primero == null) Primero = new Nodo(E);
else
{
n = Primero;
while (n.Sig != null) n = n.Sig;
n.Sig = new Nodo(E);
}
NElementos++;
}
}
Object extraer(){
Nodo n;
Object E;
if (Primero == null) E = null;
else
{
n = Primero ;
Primero = Primero.Sig;
E = n.dato() ;
n = null ;
NElementos-- ;
}
return E;
}

Nodo primero ( ){ return Primero; }
static Nodo Siguiente(Nodo n){ return n.Sig; }

void concatenar(Cola c){
if (Maximo > NElementos + c.NElementos)
{
while (c.NElementos>0){ insertar(c.extraer()); }
}
}

public static void main (String args[]) {
Cola C = new Cola(20);
Cola C2 = new Cola(8);
Nodo act = null;
Nodo act2= null;
Object Aux = null;
int fin;
String s[] = {"1ero ","2do ","3ero ","4to ","5to ","6xto ","7timo","8avo "};
System.out.println(" Prueba de inserción de 8 ristras en 2 colas (insertar )");
for (int i=0;i<8;i++){
System.out.println(" Este es el elemento numero "+i+" = '"+s[i]+"' , el cual meteré dentro de la cola") ;
C .insertar(s[i ]);
C2.insertar(s[7-i]);
}
System.out.println(" Probamos que se encuentran las 8 ristras en la colas(primero,dato,siguiente)");
fin = C.NElementos;
for (int i=0;i if (i==0){
act = C.primero();
System.out.println(" Primer elemento "+act.dato() );
act2 = C2.primero();
System.out.println(" Primer elemento(2) "+act2.dato());
}
else{
act = C.Siguiente(act);
System.out.println(" Elemento : "+act.dato());
act2 = C2.Siguiente(act2);
System.out.println(" Elemento(2) : "+act2.dato());
}
}
C.concatenar(C2);
fin = C.NElementos;
for (int i=0;i if (i==0){
act = C.primero();
System.out.println(" Primer elemento "+act.dato() );
}
else{
act = C.Siguiente(act);
System.out.println(" Elemento : "+act.dato());
}
}
fin = C.NElementos;
for (int i=0;i System.out.println(" Extrayendo Cola ["+i+"] = "+C.primero().dato());
Aux = C.extraer();
}
Aux = null;
return ;
}
}