Curso de Java: colas de prioridad

Curso de Java: colas de prioridad

Adrián Crespo

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> extends Collection<E> {

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
  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

[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 <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();
}
}
[/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.

9 Comentarios
Logo redeszone.net
Navega gratis con publicidad…

Navegar por testdevelocidad.es con publicidad personalizada, seguimiento y cookies de forma gratuita. i

Para ello, nosotros y nuestros socios i necesitamos tu consentimiento i para el tratamiento de datos personales i para los siguientes fines:

Las cookies, los identificadores de dispositivos o los identificadores online de similares características (p. ej., los identificadores basados en inicio de sesión, los identificadores asignados aleatoriamente, los identificadores basados en la red), junto con otra información (p. ej., la información y el tipo del navegador, el idioma, el tamaño de la pantalla, las tecnologías compatibles, etc.), pueden almacenarse o leerse en tu dispositivo a fin de reconocerlo siempre que se conecte a una aplicación o a una página web para una o varias de los finalidades que se recogen en el presente texto.

La mayoría de las finalidades que se explican en este texto dependen del almacenamiento o del acceso a la información de tu dispositivo cuando utilizas una aplicación o visitas una página web. Por ejemplo, es posible que un proveedor o un editor/medio de comunicación necesiten almacenar una cookie en tu dispositivo la primera vez que visite una página web a fin de poder reconocer tu dispositivo las próximas veces que vuelva a visitarla (accediendo a esta cookie cada vez que lo haga).

La publicidad y el contenido pueden personalizarse basándose en tu perfil. Tu actividad en este servicio puede utilizarse para crear o mejorar un perfil sobre tu persona para recibir publicidad o contenido personalizados. El rendimiento de la publicidad y del contenido puede medirse. Los informes pueden generarse en función de tu actividad y la de otros usuarios. Tu actividad en este servicio puede ayudar a desarrollar y mejorar productos y servicios.

La publicidad que se presenta en este servicio puede basarse en datos limitados, tales como la página web o la aplicación que esté utilizando, tu ubicación no precisa, el tipo de dispositivo o el contenido con el que está interactuando (o con el que ha interactuado) (por ejemplo, para limitar el número de veces que se presenta un anuncio concreto).

  • Un fabricante de automóviles quiere promocionar sus vehículos eléctricos a los usuarios respetuosos con el medioambiente que viven en la ciudad fuera del horario laboral. La publicidad se presenta en una página con contenido relacionado (como un artículo sobre medidas contra el cambio climático) después de las 18:30 h a los usuarios cuya ubicación no precisa sugiera que se encuentran en una zona urbana.
  • Un importante fabricante de acuarelas quiere realizar una campaña publicitaria en Internet para dar a conocer su última gama de acuarelas con la finalidad de llegar tanto a artistas aficionados como a profesionales y, a su vez, se evite mostrar el anuncio junto a otro contenido no relacionado (por ejemplo, artículos sobre cómo pintar una casa). Se detectará y limitará el número de veces que se ha presentado el anuncio a fin de no mostrarlo demasiadas veces.

La información sobre tu actividad en este servicio (por ejemplo, los formularios que rellenes, el contenido que estás consumiendo) puede almacenarse y combinarse con otra información que se tenga sobre tu persona o sobre usuarios similares(por ejemplo, información sobre tu actividad previa en este servicio y en otras páginas web o aplicaciones). Posteriormente, esto se utilizará para crear o mejorar un perfil sobre tu persona (que podría incluir posibles intereses y aspectos personales). Tu perfil puede utilizarse (también en un momento posterior) para mostrarte publicidad que pueda parecerte más relevante en función de tus posibles intereses, ya sea por parte nuestra o de terceros.

  • En una plataforma de redes sociales has leído varios artículos sobre cómo construir una casa en un árbol Esta información podría añadirse a un perfil determinado para indicar tuinterés en el contenido relacionado con la naturaleza, así como en los tutoriales de bricolaje (con el objetivo de permitir la personalización del contenido, de modo que en el futuro, por ejemplo, se te muestren más publicaciones de blogs y artículos sobre casas en árboles y cabañas de madera).
  • Has visualizado tres vídeos sobre la exploración espacial en diferentes aplicaciones de televisión. Una plataforma de noticias sin relación con las anteriores y con la que no has tenido contacto en el pasado crea un perfil basado en esa conducta de visualización marcando la exploración del espacio como un tema de tu posible interés para para otros vídeos.

El contenido que se te presenta en este servicio puede basarse en un perfilde personalización de contenido que se haya realizado previamente sobre tu persona, lo que puede reflejar tu actividad en este u otros servicios (por ejemplo, los formularios con los que interactúas o el contenido que visualizas), tus posibles intereses y aspectos personales. Un ejemplo de lo anterior sería la adaptación del orden en el que se te presenta el contenido, para que así te resulte más sencillo encontrar el contenido (no publicitario) que coincida con tus intereses.

  • Has leído unos artículos sobre comida vegetariana en una plataforma de redes sociales. Posteriormente has usado una aplicación de cocina de una empresa sin relación con la anterior plataforma. El perfil que se ha creado sobre tu persona en la plataforma de redes sociales se utilizará para mostrarte recetas vegetarianas en la pantalla de bienvenida de la aplicación de cocina.
  • Has visualizado tres vídeos sobre remo en páginas web diferentes. Una plataforma de video, no relacionada con la página web en la que has visualizado los vídeos sobre remo, pero basandose en el perfil creado cuando visistaste dicha web, podrá recomendarte otros 5 vídeos sobre remo cuando utilices la plataforma de video a través de tu televisor .

La información sobre qué publicidad se te presenta y sobre la forma en que interactúas con ella puede utilizarse para determinar lo bien que ha funcionado un anuncio en tu caso o en el de otros usuarios y si se han alcanzado los objetivos publicitarios. Por ejemplo, si has visualizado un anuncio, si has hecho clic sobre el mismo, si eso te ha llevado posteriormente a comprar un producto o a visitar una página web, etc. Esto resulta muy útil para comprender la relevancia de las campañas publicitarias./p>

  • Has hecho clic en un anuncio en una página web/medio de comunicación sobre descuentos realizados por una tienda online con motivo del “Black Friday” online y posteriormente has comprado un producto. Ese clic que has hecho estará vinculado a esa compra. Tu interacción y la de otros usuarios se medirán para saber el número de clics en el anuncio que han terminado en compra.
  • Usted es una de las pocas personas que ha hecho clic en un anuncio que promociona un descuento por el “Día de la madre”de una tienda de regalos en Internet dentro de la aplicación de una web/medio de comunicación. El medio de comunicación quiere contar con informes para comprender con qué frecuencia usted y otros usuarios han visualizado o han hecho clic en un anuncio determinado dentro de la aplicación y, en particular, en el anuncio del “Día de la madre” para así ayudar al medio de comunicación y a sus socios (por ejemplo, las agencias de publicidad) a optimizar la ubicación de los anuncios.

La información sobre qué contenido se te presenta y sobre la forma en que interactúas con él puede utilizarse para determinar, por ejemplo, si el contenido (no publicitario) ha llegado a su público previsto y ha coincidido con sus intereses. Por ejemplo, si hasleído un artículo, si has visualizado un vídeo, si has escuchado un “pódcast” o si has consultado la descripción de un producto, cuánto tiempo has pasado en esos servicios y en las páginas web que has visitado, etc. Esto resulta muy útil para comprender la relevancia del contenido (no publicitario) que se te muestra.

  • Has leído una publicación en un blog sobre senderismo desde la aplicación móvil de un editor/medio de comunicación y has seguido un enlace a una publicación recomendada y relacionada con esa publicación. Tus interacciones se registrarán para indicar que la publicación inicial sobre senderismo te ha resultado útil y que la misma ha tenido éxito a la hora de ganarse tu interés en la publicación relacionada. Esto se medirá para saber si deben publicarse más contenidos sobre senderismo en el futuro y para saber dónde emplazarlos en la pantalla de inicio de la aplicación móvil.
  • Se te ha presentado un vídeo sobre tendencias de moda, pero tu y otros usuarios habéis dejado de visualizarlo transcurridos unos 30 segundos. Esta información se utilizará para valorar la duración óptima de los futuros vídeos sobre tendencias de moda.

Se pueden generar informes basados en la combinación de conjuntos de datos (como perfiles de usuario, estadísticas, estudios de mercado, datos analíticos) respecto a tus interacciones y las de otros usuarios con el contenido publicitario (o no publicitario) para identificar las características comunes (por ejemplo, para determinar qué público objetivo es más receptivo a una campaña publicitaria o a ciertos contenidos).

  • El propietario de una librería que opera en Internet quiere contar con informes comerciales que muestren la proporción de visitantes que han visitado su página y se han ido sin comprar nada o que han consultado y comprado la última autobiografía publicada, así como la edad media y la distribución de género para cada uno de los dos grupos de visitantes. Posteriormente, los datos relacionados con la navegación que realizas en su página y sobre tus características personales se utilizan y combinan con otros datos para crear estas estadísticas.
  • Un anunciante quiere tener una mayor comprensión del tipo de público que interactúa con sus anuncios. Por ello, acude a un instituto de investigación con el fin de comparar las características de los usuarios que han interactuado con el anuncio con los atributos típicos de usuarios de plataformas similares en diferentes dispositivos. Esta comparación revela al anunciante que su público publicitario está accediendo principalmente a los anuncios a través de dispositivos móviles y que es probable que su rango de edad se encuentre entre los 45 y los 60 años.

La información sobre tu actividad en este servicio, como tu interacción con los anuncios o con el contenido, puede resultar muy útil para mejorar productos y servicios, así como para crear otros nuevos en base a las interacciones de los usuarios, el tipo de audiencia, etc. Esta finalidad específica no incluye el desarrollo ni la mejora de los perfiles de usuario y de identificadores.

  • Una plataforma tecnológica que opera con un proveedor de redes sociales observa un crecimiento en los usuarios de aplicaciones móviles y se da cuenta de que, en funciónde sus perfiles, muchos de ellos se conectan a través de conexiones móviles. La plataforma utiliza una tecnología nueva para mostrar anuncios con un formato óptimo para los dispositivos móviles y con un ancho de banda bajo a fin de mejorar su rendimiento.
  • Un anunciante está buscando una forma de mostrar anuncios en un nuevo tipo de dispositivo. El anunciante recopila información sobre la forma en que los usuarios interactúan con este nuevo tipo de dispositivo con el fin de determinar si puede crear un nuevo mecanismo para mostrar la publicidad en ese tipo de dispositivo.

El contenido que se presenta en este servicio puede basarse en datos limitados, como por ejemplo la página web o la aplicación que esté utilizando, tu ubicación no precisa, el tipo de dispositivo o el contenido con el que estás interactuando (o con el que has interactuado) (por ejemplo, para limitar el número de veces que se te presenta un vídeo o un artículo en concreto).

  • Una revista de viajes, para mejorar las experiencias de viaje en el extranjero, ha publicado en su página web un artículo sobre nuevos cursos que ofrece una escuela de idiomas por Internet. Las publicaciones del blog de la escuela se insertan directamente en la parte inferior de la página y se seleccionan en función de la ubicación no precisa del usuario (por ejemplo, publicaciones del blog que explican el plan de estudios del curso para idiomas diferentes al del país en el que este te encuentras).
  • Una aplicación móvil de noticias deportivas ha iniciado una nueva sección de artículos sobre los últimos partidos de fútbol. Cada artículo incluye vídeos alojados por una plataforma de streaming independiente que muestra los aspectos destacados de cada partido. Si adelantas un vídeo, esta información puede utilizarse para determinar que el siguiente vídeo a reproducir sea de menor duración.

Se puede utilizar la localización geográfica precisa y la información sobre las características del dispositivo

Al contar con tu aprobación, tu ubicación exacta (dentro de un radio inferior a 500 metros) podrá utilizarse para apoyar las finalidades que se explican en este documento.

Con tu aceptación, se pueden solicitar y utilizar ciertas características específicas de tu dispositivo para distinguirlo de otros (por ejemplo, las fuentes o complementos instalados y la resolución de su pantalla) en apoyo de las finalidades que se explican en este documento.

O sin publicidad desde 1,67€ al mes

Por solo 1,67€ al mes, disfruta de una navegación sin interrupciones por toda la red del Grupo ADSLZone: adslzone.net, movilzona.es, testdevelocidad.es, lamanzanamordida.net, hardzone.es, softzone.es, redeszone.net, topesdegama.com y más. Al unirte a nuestra comunidad, no solo estarás apoyando nuestro trabajo, sino que también te beneficiarás de una experiencia online sin publicidad ni cookies de seguimiento.