Un lunes más, volvemos con una nueva entrega del curso de Java de RedesZone.net.
Si recordáis, la semana pasada, os dimos la solución al ejercicio de ArrayList que os habíamos propuesto y además, os hablamos de las pilas de datos en Java y como se puede llevar acabo su implementación, ya que, en Java no existe una interfaz que la implemente.
Hoy vamos a hablaros en el curso de Java, de cómo se pueden implementar las colas de datos, en concreto, las colas de prioridad. También os proporcionaremos un ejercicio en el cual, os podréis ir poniendo en contacto con este tipo de datos, y que está parcialmente resuelto. Vamos con las colas de datos a modo de introducción.
Una cola es una lista especial en la que todos los elementos se insertan por un extremo de la lista y se sacan por el otro extremo (FIFO)
- No confundir con la cola de prioridad (las explicaremos más adelante)
Al igual que en las pilas, la implementación
- Implementa estas operaciones eficientemente
- Aprovecha las limitaciones para simplificar
Las operaciones básicas que se realizan sobre una cola suelen ser las siguientes:
- constructor: Crea la pila con cero elementos.
- encola: Añade el parámetro elElemento al extremo de inserción de la cola. Si elElemento es incompatible con los elementos que se almacenan en esta colección lanza una excepción.
- desencola: Elimina de la cola el elemento que está en el extremo de extracción y lo retorna. Si no hay ningún elemento, lanza una excepción.
- hazNula: Elimina todos los elementos de la cola, dejándola vacía.
- estaVacia: Si la cola está vacía retorna true. En otro caso, retorna false.
- tamaño: Retorna un entero que dice cuántos elementos hay en la cola.
Posibles implementaciones
La interfaz Queue, junto a la operación add() heredada de la colección, dispone de operaciones para encolar, desencolar, o consultar el primer elemento de la cola (el próximo que se va a desencolar). De cada una de ellas dispone de dos versiones, una que lanza una excepción si hay un fallo, y otra que retorna un valor especial si la acción solicitada no puede realizarse.
- offer(): retorna true si ha conseguido encolar el elemento y false si no (por ejemplo, si la cola es limitada, y el elemento no cabe).
- poll(): desencola y retorna un elemento si existe; si no existe, retorna null.
- peek(): retorna sin desencolarlo el primer elemento si existe (el que se desencolaría con peek); si no existe, retorna null.
- add(): intenta encolar el elemento e, y en caso de que no pueda (por ejemplo, si la cola es limitada, y el elemento no cabe) lanza IllegalStateException.
- remove(): desencola y retorna un elemento si existe; si no existe, lanza NoSuchElementException.
- element(): retorna sin desencolarlo el primer elemento si existe (el que se desencolaría con peek); si no existe, lanza NoSuchElementException.
Las colas Java no deben usarse para almacenar elementos que sean null, ya que entonces los métodos poll() y peek() no funcionarían bien.
[java]
public interface Queue
E element();
boolean offer(E e);
E peek();
E poll();
E remove();
}
[/java]
Si queréis el ejemplo de una cola, lo tenéis en esta entrega.
Nosotros ahora vamos a dar un mas más allá, y vamos a hablaros de las colas de prioridad.
- En Java existe la clase PriorityQueue que
- Implementa la interfaz Queue
- Se comporta como una cola de prioridad
- Usa compareTo, o un comparador, para ordenar los elementos por su prioridad
- Los ordena de menor a mayor (sale primero el menor elemento)
- Para los que son iguales, el orden es arbitrario
- Constructores de las colas de prioridad
[java]PriorityQueue()[/java]
Crea la cola para ordenar sus elementos con compareTo()
[java]PriorityQueue(Collection extends E> c)[/java]
Crea la cola para ordenar sus elementos con compareTo(), y conteniendo inicialmente los elementos de la colección c
[java]PriorityQueue(int initialCapacity)[/java]
Crea la cola para ordenar sus elementos con compareTo(), y con la capacidad inicial indicada
[java]PriorityQueue(int initialCapacity, Comparator super E> comparator)[/java]
Crea la cola con la capacidad inicial indicada, y para ordenar sus elementos de acuerdo con el comparador indicado
Vamos ahora con un ejemplo práctico de una cola de prioridad:
- Escribir una clase para controlar el acceso de clientes a un servicio con varios grados de urgencia
- Se guardará una cola de espera de clientes, ordenados por prioridad.
- Cada cliente tiene un nombre, un número de móvil.
- Junto al cliente se guarda su urgencia.
Operaciones
- añadir un cliente
- atender a un cliente
- mostrar el estado de las colas
Escribir también un programa de prueba
Clase Urgencia (Enumerada)
[java]
/**
* Clase enumerada que representa la
* urgencia de un cliente
*/
public enum Urgencia
{
baja, media, alta
}
[/java]
Clase ColaEsperaConUrgencia
[java]
import java.util.*;
public class ColaEsperaConUrgencia
{
/**
* Clase interna para almacenar los datos
* de un cliente con urgencia
*/
private static class DatosCliente implements Comparable
{
Cliente c;
Urgencia urg;
/**
* Constructor de DatosCliente
*/
DatosCliente (Cliente c, Urgencia urg) {
this.c=c;
this.urg=urg;
}
/**
* Comparación de clientes por su urgencia
*/
public int compareTo(DatosCliente otro) {
return this.urg.compareTo(otro.urg);
}
}
// final de la clase DatosCliente
// cola del servicio
private Queue
/**
* Constructor de ColaEspera
*/
public ColaEsperaConUrgencia()
{
colaEspera=new
PriorityQueue
}
/**
* Nuevo cliente; se mete en la cola de espera
*/
public void nuevoCliente
(Cliente c, Urgencia urg)
{
DatosCliente datos=new DatosCliente(c,urg);
colaEspera.add(datos);
}
/**
* Atender cliente: se saca de la cola de
* espera; retorna el cliente atendido
*/
public Cliente atenderCliente()
throws NoSuchElementException
{
DatosCliente datos=colaEspera.remove();
return datos.c;
}
/**
* Mostrar el estado de la cola de espera
*/
public void muestraEstado() {
System.out.println();
System.out.println("–Estado de la cola–");
System.out.println("No atendidos "+
colaEspera.size());
for (DatosCliente datos:colaEspera) {
System.out.println(datos.c+" urgencia:
"+datos.urg);
}
}
/**
* Num clientes en espera
*/
public int numClientesEnEspera() {
return colaEspera.size();
}
}
[/java]
Es necesaria una clase Cliente y una Principal para probarlo, que os lo dejo a vuestra elección. En la próxima entrega os vamos a proponer unas, pero hay muchas posibilidades y no tienen porque coincidir con las nuestras. También os daremos un ejercicio para que practiquéis con las colas y las pilas, y veáis la diferencia conceptual entre ambas implementaciones, y comenzaremos hablando un poco de los mapas de datos.
