Ejercicio 2!

Este ejercicio trata de crear una estructura de datos compleja. En lo referente al enunciado, me parece que está bien explicado. No hay ningún punto en el que haya dudado de lo que me preguntaban. Igualmente haré un resumen de lo que me piden a modo de introducción.

Tenemos que crear una cola (con su política de inserción/obtención FIFO), implementada mediante una lista enlazada (lista con memoria dinámica). Esta cola debe almacenar pilas (LIFO), en este caso implementadas mediante un array. En cada posición de este array debe haber un vector(memoria dinámica) que almacene enteros.

Nos piden implementar los siguientes métodos en la clase pila: introducir un vector, extraer un vector, indicar si está vacía, indicar si está llena e imprimir; y los siguientes métodos en la clase cola: encolar una pila, desencolar una pila, indicar si está vacía e imprimir.

Lo que hay que conseguir es que llamando al método imprimir de la clase cola, éste imprima todas las pilas que contiene, los vectores que contiene cada pila y los enteros que contiene cada vector.

La implementación es la siguiente:

CLASE VECTOR DE ENTEROS

import java.util.Vector;
import java.util.Enumeration;

public class VectorEnteros {
//vector que va a guardar los enteros
private Vector vectorenteros;
/*Por simplicidad creamos un array que contenga inicialmente los enteros que queremos guardar.
Si queremos modificar el vector, solo hay que modificar el array correspondiente en la clase Prueba*/
private int numeros[];

public VectorEnteros(){
//Creo el vector
vectorenteros=new Vector();
}

public void añadir(int n[]){
numeros=n;
for (int i=0;i< numeros.length; i++){
Integer num=new Integer(numeros[i]);
vectorenteros.addElement(num);
}
}

public void imprimir(){
Enumeration e=vectorenteros.elements();
while(e.hasMoreElements()){
//Hay que hacer cambio de tipo
Integer entero=(Integer)e.nextElement();
System.out.print(entero+” “);
}
System.out.println(“”);

}
}//Fin clase

CLASE PILA

//Clase Pila implementada como array en la que se almacenan vectores de enteros. Observar que se cumple LIFO

public class Pila{
private int numElementos;
private VectorEnteros elementos[];
private int indice;

public Pila(int numElementos){
this.numElementos=numElementos;
indice=-1;
elementos= new VectorEnteros[numElementos];
for(int i=0; i<numElementos;i++){
elementos[i]=new VectorEnteros();
}
}

public int vacia(){
return(indice =-1);
}
public int llena(){
return (indice=numElementos-1);
}

public void push(VectorEnteros v){
indice++;
elementos[indice]=v;
}

public VectorEnteros pop(){
VectorEnteros v= elementos[indice];
indice–;
return v;
}

public void imprimir(){
int j=0;
for (int i=elementos.length-1;i>=0;i–){
System.out.print(“Vector “+(j+1)+”\t”);
elementos[i].imprimir();
j++;
}
System.out.println(“”);

}
}//Fin clase

CLASE NODO

//Clase nodo para implementar posteriormente la cola dinámica

public class Nodo{
public Nodo siguiente;
public Pila pila;

public Nodo(){
pila=null;
siguiente=null;
}

public Nodo(Pila p, Nodo sig){
pila=p;
siguiente=sig;
}

public Nodo siguiente(){
return siguiente;
}
public Pila elemento(){
return pila;
}
public void actualizarPila(Pila p){
pila=p;
}
public void actualizarSiguiente(Nodo sig){
siguiente=sig;
}
}//Fin clase

CLASE COLA

//Clase Cola implementada como lista dinámica en la que se almacenan pilas. Observar que se cumple FIFO

public class Cola{
private Nodo primero;
private Nodo ultimo;

public Cola(){
primero = null;
ultimo = null;
}

public boolean vacia(){
return (primero == null);
}

public void encolar(Pila p){
Nodo nuevo = new Nodo(p,null);

if(vacia())
primero = nuevo;
else
ultimo.siguiente = nuevo;
ultimo = nuevo;
}

public Pila desencolar(){
if(vacia()){
System.err.println(“No hay elementos en la cola\n”);
return null;
}
else{
Pila p = primero.pila;
primero = primero.siguiente;
if(vacia()){
ultimo = null;
}
return p;
}
}

public void imprimir(){
int j=1;

if(!vacia()){
System.out.println(“CONTENIDO DE LA COLA\n”);

while(!vacia()){
System.out.println(“Pila “+j+”: \n”);

Pila p = primero.pila;
primero = primero.siguiente;

ultimo = null;
p.imprimir();
j++;
}
System.out.println(“\n”);
}
else{
System.out.println(“ESTA COLA ESTÁ VACÍA”);
System.out.println(“\n\n”);
}
}
}//Fin clase

CLASE DE PRUEBA

public class Prueba{
public static void main(String[]args){

//creamos nuestros arrays de enteros
int array1[]= {1,2,3,4,5,6,7};
int array2[]= {1,2,3,4};
int array3[]= {1,2};
int array4[]= {1,2,3,4,5,6,7,8,9,10};
int array5[]= {1};
int array6[]= {1,2,3,4,5};
int array7[]= {1,2,3,4,5,6};

//rellenamos los vectores
VectorEnteros v1=new VectorEnteros();v1.añadir(array1);
VectorEnteros v2=new VectorEnteros();v2.añadir(array2);
VectorEnteros v3=new VectorEnteros();v3.añadir(array3);
VectorEnteros v4=new VectorEnteros();v4.añadir(array4);
VectorEnteros v5=new VectorEnteros();v5.añadir(array5);
VectorEnteros v6=new VectorEnteros();v6.añadir(array6);
VectorEnteros v7=new VectorEnteros();v7.añadir(array7);

//creamos una pila con los 7 vectores de enteros
Pila p1=new Pila(7);
p1.push(v1);
p1.push(v2);
p1.push(v3);
p1.push(v4);
p1.push(v5);
p1.push(v6);
p1.push(v7);

//creamos varias pilas para almacenar en la cola y hacer pruebas con ellas
Pila p2=new Pila(7); p2=p1;
Pila p3=new Pila(7); p3=p1;
Pila p4=new Pila(7); p4=p1;
Pila p5=new Pila(7); p5=p1;
Pila p6=new Pila(7); p6=p1;
Pila p7=new Pila(4); //cambiamos el orden y el tamaño
p7.push(v4);
p7.push(v2);
p7.push(v3);
p7.push(v1);

Cola c1=new Cola();
c1.encolar(p1);c1.encolar(p7);c1.encolar(p3);c1.encolar(p7);

Cola c2=new Cola();
c2.encolar(p7);c2.encolar(p6);c2.encolar(p5);

Cola c3=new Cola();
Cola c4=new Cola();

c4.encolar(p7);
c1.desencolar();

c1.imprimir();
c2.imprimir();
c3.imprimir();
c4.imprimir();
}
}//Fin clase

CONCEPTOS FUNDAMENTALES

En este ejercicio repasamos estructuras de datos tocando un poco todo lo que hemos dado durante el curso.

En el orden en que yo he ido haciendo el ejercicio, lo primero que he repasado es como crear una clase vector de enteros(con memoria dinámica); no es muy difícil si importamos la clase Vector que ya tenemos implementada (import java.util.Vector). El mayor problema que veo es a la hora de hacer los cambios de tipo, creo que es donde más metemos la pata… Hay que tener en cuenta que la clase Vector almacena una lista de elementos de tipo Object, o derivadas de ésta; en cualquier caso, estos elementos tienen que ser objetos. En nuestro caso, no podemos almacenar enteros como int(ya que es un tipo primitivo), tenemos que hacer un cambio de tipo a su clase envoltorio Integer para que funcione correctamente.

En la clase Pila repasamos el comportamiento de inserción y obtención de objetos LIFO. Básicamente trabajamos con arrays, con las NullPointerException y esas cosas que nos hacen la vida un poco más difícil…Esta parte desde mi punto de vista es la más sencilla ya que trabajamos con memoria estática, que es a lo que más acostumbrados estamos.

La clase Cola es la que más problemas me ha creado; no por no entender el comportamiento de una cola, sino por tener que implementarla como lista enlazada. He tenido que buscar más información sobre las listas enlazadas a parte de los apuntes para por fin lograr entenderlas. La clase Nodo es siempre igual, yo creo que he incluido métodos que no eran necesarios para nada, pero bueno…por si acaso! y en la clase cola, el método desencolar todavía no me queda claro del todo…

Para terminar he creado una clase Prueba donde como su nombre indica compruebo los métodos en los que más dudas tengo, y que todo funcione correctamente. Imagino que en algo habré metido la pata pero este ejercicio creo que lo he entendido bastante bien