Curso de Java: colas de prioridad

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.


public interface Queue<E> extends Collection<E> {

E element();

boolean offer(E e);

E peek();

E poll();

E remove();

}

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
  1. Los ordena de menor a mayor (sale primero el menor elemento)
  2. Para los que son iguales, el orden es arbitrario
  3. Constructores de las colas de prioridad
PriorityQueue()

Crea la cola para ordenar sus elementos con compareTo()

PriorityQueue(Collection<? extends E> c)

Crea la cola para ordenar sus elementos con compareTo(), y conteniendo inicialmente los elementos de la colección c

PriorityQueue(int initialCapacity)

Crea la cola para ordenar sus elementos con compareTo(), y con la capacidad inicial indicada

PriorityQueue(int initialCapacity, Comparator<? super E> comparator)

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)


/**

* Clase enumerada que representa la

* urgencia de un cliente

*/

public enum Urgencia

{

baja, media, alta

}

Clase ColaEsperaConUrgencia

import java.util.*;

public class ColaEsperaConUrgencia

{

/**

* Clase interna para almacenar los datos

* de un cliente con urgencia

*/

private static class DatosCliente implements Comparable <DatosCliente>

{

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<DatosCliente> colaEspera;

/**

* Constructor de ColaEspera

*/

public ColaEsperaConUrgencia()

{

colaEspera=new

PriorityQueue<DatosCliente>();

}

/**

* 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();
 }
}

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.

Compártelo. ¡Gracias!

  • picacho

    Buf !!!

  • Jarod

    Tengo una pregunta.
    Creo que no me ordena por nivel de urgencia.
    Tengo por ejemplo 2 clientes. El primer lo añado con urgencia media y el segundo lo añado con urgencia baja. Y con el metodo que muestra el estado (sin haber atendido antes) me muestra primero el cliente de urgencia baja y luego el de urgencia media. No debería ser al reves ?
    Porque si ahora atiendo a un cliente ya no aparece en la cola el de urgencia baja. No debería ser el de urgencia media de ser atendido ?

    • http://www.adslzone.net Adrián Crespo

      mándame un correo y te mando la clase Java, porque yo lo tengo y funciona bien, es decir extrae atiende los clientes de forma correcta, aunque el muestraEstado(), no muestra todos ordenados, y desconozco el porque, he estado mirando por si habia programado mal el compareTo de la clase DatosCliente y esta todo correcto

      • Jarod

        ¿A que correo te lo mando?

        • http://www.redeszone.net Sergio De Luz

          adrian.crespo[AT]redeszone.net :)

  • Pingback: Curso gratis de introducción de Java | Formación Online

RedesZone © 2010 - 2014