Beceoca

César Juárez Megías

ENUNCIADO EJERCICIO 2

 

Se pretende construir una estructura de datos compleja, en este caso una cola mediante el uso de una lista enlazada.

Esta cola deberá contener los siguientes métodos:

            · Encolar elementos (enqueue).

            · Desencolar elementos (dequeue).

            · Indicar si la cola está vacía.

            · Imprimir por pantalla todos los contenidos de la cola.

 

En nuestro caso, la cola que vamos a crear almacenará objetos de tipo pila, cuya clase también deberemos programar, la cual llevará estos métodos:

            · Introducir un elemento en la pila (push).

            · Extraer un elemento de la pila (pop).

            · Indicar si la pila está vacía.

            · Indicar si la pila está llena.

            · Imprimir por pantalla todos los contenidos de la pila.

 

Como en el caso de las colas también deberemos programarla mediante una lista enlazada, la pila se implementará mediante un array.

 

Cada una de estas pilas contendrá vectores (uno en cada posición de la pila)

 

Suponemos que la cola y la pila tienen tamaño para 15 objetos.

Suponemos también que los vectores que se almacenan en la pila nos los dan ya tal y como se quieren almacenar

 

 

NOTAS

 El método imprimir de la cola imprimirá por pantalla cada una de las pilas almacenadas en ella.

A su vez, imprimir cada una de estas pilas significa imprimir todos y cada uno de los vectores que almacena.

Por último, imprimir uno de estos vectores quiere decir imprimir, uno debajo de otro, todos los objetos que estén guardados en él, considerando que dichos objetos serán números enteros.

Tras la impresión, la estructura de datos al completo deberá quedar tal y como estaba al principio.

CLASES EJERCICIO 2

(para hacer la lectura más fácil he puesto los comentarios en color verde)

 

Clase Cola

public class Cola{

//Declaramos los atributos necesarios, en este caso el constructor será el que viene por defecto

private int tamaño = 15;

public int objetosEnCola = 0;

public int objetosImpresos = 0;

public Nodo primero = null;

public Nodo ultimo = null;

 

//Metodo enqueue

public void enqueue(Pila pila){

//Comprobamos que la cola no está llena

if (estaLlena == false){

if (estaVacia == true){

//Al ser el primer objeto añadido tendrá a la vez la primera y la última posición

primero = new Nodo(pila);

ultimo = new Nodo(pila);

}else{

//Como no es el primer objeto añadido creo un nuevo nodo con la pila que voy a encolar

nuevoUltimo = new Nodo(pila);

//Pongo el ultimo nodo apuntando al nuevo

ultimo.setNodoSiguiente(nuevoUltimo);

//Cambio el ultimo nodo por el que acabo de añadir al final de la cola

ultimo = nuevoUltimo;}

//Sumo un objeto en la cuenta de objetos que tiene la cola

objetosEnCola++;

}else{

//Si la cola está llena saco por pantalla un mensaje de error

System.error.println(“La cola está llena, no puede añadir más objetos”);}}

 

//Metodo dequeue

public Pila dequeue(){

if (estaVacia == false){

//Guardo la pila a devolver en una variable

Pila pilaADevolver = primero.getPila();

//Pongo la posición siguiente como la primera de la cola

Nodo NuevoPrimero = primero.getSiguiente();

primero = nuevoPrimero;

//Resto el objeto que acabo de sacar de la cola

objetosEnCola–;

//Devuelvo el nodo que había en la primera posición

return (PilaADevolver);}

//Si no hay objetos en la cola

else{

System.error.println(“No hay más objetos en esta cola”);}}

 

//Metodo estaVacia

public boolean estaVacia(){

//Si la cola está vacía (no hay ningún objeto) devuelvo true, sino, devuelvo false

if (objetosEnCola==0){

return true;

}else{

return false;}}

 

//Metodo imprimir

public void imprimir(){

//Si la cola está vacia lo comunicamos en un mensaje por pantalla

if (estaVacia()==true){

System.out.println(“La cola está vacia”);

}else{

primero.imprimir();

imprimeRestantes(primero.getSiguiente());}

 

public void imprimeRestantes(Nodo nod)

//Si el nodo no es nulo, lo imprimimos y llamamos a este método para que imprima el siguiente

if (nod != null){

nod.imprimir();

imprimeRestantes(nod.gesSiguiente());

//Si el nodo es nulo, no hay más que hacer y por lo tanto se sale automáticamente del algoritmo recursivo

}}}//Fin de la clase Cola

 

Clase Nodo

public class Nodo{

//Declaramos los atributos necesarios

Pila pila;

Nodo siguiente == null;

 

//Constructor

public Nodo(Pila pila){

this.pila = pila;}

 

//Método setNodoSiguiente

public void setNodoSiguiente(Nodo siguiente){

this.siguiente = siguiente;}

 

//Método getNodoSiguiente

public Nodo getNodoSiguiente(){

return (siguiente);}

 

//Método getPila

public Pila getPila(){

return pila;}

//Método imprimir (llama directamente al método imprimir de la pila)

public void imprimir(){

pila.imprimir();}

}//Fin de la clase Nodo

 

Clase Pila

import import java.util.*;

public class Pila{

//Declaramos las variables necesarias

public Vector array [];

public int tamaño = 15;

public int posicion = 0;

 

//Constructor

public Pila(){

array = new Vector [tamaño];}

 

//Método push

public void push(Vector i){

//Miramos si la cola no está llena, si lo está sacamos un mensaje por pantalla,

y si no lo está añadimos el objeto en su posición

if (estaLlena()){

System.out.println(“La pila está llena”);}

else{

array [posicion] = i;

posicion++;}}

 

//Método pop

public Vector pop(){

//Devolvemos el objeto de la lista que está en la primera posición para salir de ella

return array [posicion];

posicion–;}

 

//Método estaLlena

public boolean estaLlena(){

if (posicion == (tamaño-1)){

return true;

}else{

return false;}}

 

//Método estaVacia

public boolean estaVacia(){

if (posicion == -1){

return true;

}else{

return false;}}

 

//Método imprimir

public void imprimir(){

//Comprobamos que no está vacia y si no lo está imprimimos por pantalla todos los elementos de la lista

if (estaVacia()){

System.out.println(“La pila está llena”);

}else{

//Recorremos la pila

for(int i = 0; i<=posicion; i++){

//Recorremos el vector

for(int j=0; j<array[i].size(); j++){

System.out.print(array[i].elementAt(j)+”  “);}}}}

 

}//Fin de la clase Pila

CONCEPTOS USADOS EN EL EJERCICIO 2

 

En este caso los conceptos usados para resolver este ejercicio son los siguientes:

            - Concepto de pilas y colas

            - Uso de una cola dinámica

            - Uso de la clase Vector

            - Conceptos de algoritmia nivel básico/medio (recorrer arrays, llamadas a otros métodos dentro de un método)

            - Recursividad