Cola

Una Cola es una estructura formada por una secuencia de 0 a N elementos, en la que la inserción de nuevos elementos en la estructura se realiza por un extremo llamado Final, y las extracciones de elementos de la estructura se realizan por el otro extremo, que llamaremos Principio.

La misma definición de la estructura Cola, implica que el primer elemento que se inserte en la estructura, será el primer elemento que pueda extraerse de la misma. Por esa razón la estructura Cola también recibe el nombre de estructura FIFO (First Input First Output). Asi pues el proceso de un elemento de la Cola, exige que dicho elemento ocupe la posición del Principio de la Cola.

Ejemplos de colas en la vida real:

Cola de la taquilla para sacar entradas a un espectáculo.Cola en la gasolinera para cargar el deposito del coche.Cola para pagar en el supermercadoCola en la peluqueria ...

Operaciones para la manipulación de la estructura Cola

Sobre una estructura tipo Cola, además de surgir de forma natural las operaciones que permiten añadir y quitar elementos de la cola necesitaremos otras operaciones para la manipulación dicha estructura como son:

- Crear una Cola- Vaciar la Cola- Comprobar si la cola Esta Vacia- Obtener una copia del primer elemento de la cola- Insertar un elemento por el final de la Cola- Borrar el elemento que esta el primero de la Cola

A la operación Insertar se la conoce tambien como Encolar u operación Put.

A la unión de las operaciones Primero + Borrar se la conoce tambien como Desencolar u operación Get.

La declaracion completa de la clase Nodo usada en la cola es la siguiente:

Nodo.java

public class Nodo protected Object elemento; //Información, de tipo Object, almacenada en cada nodo

protected Nodo siguiente; //Referencia al siguiente nodo

public Nodo()/* Crea un nuevo objeto nodo */{

elemento = null;siguiente = null;

}public Nodo(Object x)/* Crea un nuevo objeto nodo moviendo el elemento X */

{elemento = x;

}public Nodo(Object x, Nodo sig)/* Crea un nuevo objeto nodo moviendo el elemento X sin copiar

y poniendo en su atributo Siguiente el valor Sig */ {

elemento = x;siguiente = sig;

} public void insertarSig(Object x)/* Inserta un nodo justo después del nodo en curso El elemento es movido SIN COPIAR. */

{Nodo NuevoNodo = new Nodo();NuevoNodo.elemento = x;NuevoNodo.siguiente = this.siguiente;// Nodo NuevoNodo = new Nodo(x, siguiente);this.siguiente = NuevoNodo;

}

CLASE COLA

La Cola es una estructura lineal de tipo FIFO (First Input First Output), en la que los elementos se insertan por un extremo de la estructura y se obtienen por el extremo contrario (pe. Cola de la taquilla del cine, cola de un comedor…).

Se va ha implementar la clase Cola según la siguiente definición:

/*Clase Nodo. Cada elemento de la cola es un nodo que contiene información de tipo Object y una referencia al siguiente nodo de la lista */public class Nodo {

//Información, de tipo Object, almacenada en cada nodoprotected Object elemento;//Referencia al siguiente nodoprotected Nodo siguiente;

}

public class Cola {//Cola que almacena objetos de tipo Object/* primero y ultimo hacen referencia al primer y último nodo de la cola */private Nodo primero, ultimo;// tam indica el número de elementos de la pila en cada momento private int tam;

/*Constructor sin argumentos. Crea una cola vacía (las dos referencias (primero y ultimo) a null */public Cola()

/* Devuelve si la cola está vacía o no */public boolean esVacia()

/* Devuelve el número de elementos de la cola */public int tamanyo()

/* Inserta el objeto o, que llega como parámetro, al final de la cola*/public void put(Object o)

/* Si la cola no está vacía elimina, sin devolverlo, el primer elemento de la cola, en caso contrario muestra un mensaje de error */public void borrar()

/* Si la cola no está vacía devuelve y elimina el primer elemento de la cola, en caso contrario muestra un mensaje de error */public Object get()

/* Si la cola no está vacía devuelve, pero no elimina, el primer elemento de la cola, en caso contrario muestra un mensaje de error */public Object frente()

}

public class Cola{

private Nodo primero, ultimo; //hace referencia al primero y al ultimo nodo de la cola

private int tam; //indica el nº de elementos de la cola

public Cola()/* Crea una nueva cola, vacía */{

primero = null;ultimo = null;tam = 0;

}

public void vaciar()/* Elimina todos los elementos de la cola y la deja vacia */{

primero = null;ultimo = null;tam = 0;

}

public boolean esVacia()/* Devuelve true si la cola esta vacia, false en caso contrario */{

return (primero == null);}

public int tamanyo()/* Devuelve el numero de elementos que contiene la cola */{

return tam;}

public void put( Object x );/* Inserta X en la ultima posición de la cola */{

if (primero == null){

primero = new Nodo( x );ultimo = primero;

}else{

ultimo.InsertarSiguiente(x);ultimo = ultimo.siguiente;

} tam ++;

}

public Object frente( )/* Devuelve, sin eliminar, el elemento situado en el frente de la cola.

Devuelve null si la cola esta vacia*/ {

return primero.elemento;}

public void borrar( )/* Elimina sin devolverlo, el elemento situado en el frente de la cola */

{if (primero != null) {

primero = primero.siguiente; tam --;

}}

public Object get( )/* Devuelve y elimina el elemento situado en en el frente de la cola.

Devuelve null si la cola esta vacia*/ {

if (primero == null) return null;

else {

Nodo temp = primero;primero = primero.siguiente;

tam --;return temp.elemento;

}}

}