Trabajando con hilos.

Hilos y pausas.

    Una vez que un hilo se crea y la máquina virtual de Java lo integra al entorno de ejecución, el hilo empieza a trabajar. En ocasiones, resulta conveniente que un hilo realice pequeñas pausas, o que se sincronice con otros en el sentido de esperar o verificar si algún otro hilo ha hecho ya su trabajo.

    El Ejemplo MensajesPausados muestra el uso del método sleep para pausar temporalmente la ejecución de un hilo. sleep es un método estático, es decir, no se requiere de un objeto concreto que reciba el mensaje, pero sí el nombre de la clase a la cual pertenece (línea 28). En esencia, el ejemplo imprime línea por línea un hermoso poema con pausas de 4 segundos (4000 milisegundos) entre cada línea. Note que esto es sólo un tiempo aproximado, y no debería considerarse con exactitud bajo ninguna circunstancia. En este sentido, resulta fatal el considerar aspectos de cualquier tipo de sincronización con base en el tiempo: no es buena idea y el azar puede (y seguramente lo hará) jugar en su contra.

    Por otro lado, el Ejemplo MensajesPausados2 muestra como única diferencia respecto del anterior la línea 12, particularmente en lo que se refiere a la excepción InterruptedException. El uso de un método como sleep podría generar un excepción del tipo verificada (Checked Exception), por lo que es preciso que se maneje o al menos se atrape. En el primer ejemplo main sólo reporta que de ocurrir la relanzará, es decir, no hace ningún manejo ni la atrapa pero al menos la reporta; el ejemplo en turno omite dicha declaración, por lo que ni siquiera compilará y se reportará un mensaje similar al siguiente:

MensajesPausados2.java:28: error: unreported exception InterruptedException; must be caught or declared to be thrown
            Thread.sleep(4000);
                        ^
1 error

se invita al lector a corroborar lo anterior.

    El Ejemplo MensajesPausados3 muestra una alternativa para la ejecución realizando un manejo muy elemental de la excepción correspondiente a través del bloque try-catch (líneas 22-31). Note que desde el punto de vista de la compilación y la ejecución, el Ejemplo MensajesPausados y el Ejemplo MensajesPausados3 son lógicamente equivalentes.

Hilos interactuando.

   El Ejemplo HilosInteractuando consiste en dos hilos:

1. El de main.
2. El derivado de CicloMensaje: Hilo (línea 57).
   

    El primero es el hilo principal main que cada aplicación de Java tiene. El hilo principal crea y pone en ejecución (líneas 56-59) un nuevo hilo a partir de un objeto ejecutable (CicloMensaje) y espera por él para terminar (líneas 63, 67, 68-69 y 74).

    Si el hilo derivado de la clase CicloMensaje se tarda mucho en terminar, el hilo principal lo interrumpe (línea 71).
   
   Como en los ejemplos de la sección anterior, el hilo de CicloMensaje imprime un bello poema línea por línea pero ahora con una pausa de 1 segundo entre ellas. Note el lector que no se está haciendo uso del método sleep, sino del método join de la clase Thread (línea 67); la diferencia es sutil pero importante: join es un método que debe recibir un objeto concreto a través de su respectivo mensaje (invocación) y, por la naturaleza misma de su funcionamiento, también puede generar la excepción InterruptedException. En este sentido, el diálogo entre los objetos podría interpretarse de la siguiente manera:

"El hilo de main envía un mensaje a Hilo (de CicloMensaje) para decirle que lo esperará 1 segundo más para que termine."

    Si el hilo de CicloMensaje sigue vivo (líneas 63 y 68) y el tiempo transcurrido excede la paciencia preestablecida (líneas 42 ó 48), entonces Hilo es interrumpido (línea 71) antes de que haya impreso todos sus mensajes e imprime un mensaje de reproche antes de salir (línea 34).

Consideraciones.

    El Ejemplo Ejemplo MensajesPausados ilustra dos conceptos importantes:

1. Interrupciones que pueden presentarse al trabajar con hilos (InterruptedException).
2. Las pausas de los hilos basadas en tiempo (método sleep( ) de la clase Thread).

    El método sleep hace que el hilo actual interrumpa su ejecución (se duerma) por un tiempo aproximado de cuatro segundos. Es importante que el lector tome en cuenta esto último y nunca estará de más el repetirlo, ya que es un error suponer una exactitud en el tiempo de interrupción debido a que existen gastos de gestión en la administración de los hilos (overhead). Aún peor que lo anterior, es el tratar de sincronizar hilos con base en este criterio de tiempo.

    La sincronización de hilos es una labor no trivial y no debe ser minimizada. Más adelante en el blog se muestran las bases de la sincronización en la entrada Sincronización, misma que proporciona al lector una aproximación un poco más detallada pero finalmente introductoria al respecto.

    El uso del método sleep conlleva la potencial generación de la excepción InterruptedException, la cual es una excepción verificada, es decir, debe ser atrapada o relanzada para que el programa compile y funcione, razón por la cual la línea 12 del Ejemplo Ejemplo MensajesPausados adopta este último mecanismo. Para obtener más información con respecto a los aspectos mencionados en este párrafo, consulte en el Contenido temático del blog más ampliamente los conceptos relacionados con las excepciones.

    Finalmente se conmina encarecidamente al lector a que consulte el API para ampliar y complementar la información respecto a los métodos utilizados en los ejemplos.

Ejercicios selectos (Hilos).

 

1. Considere el Ejemplo HolaEjecutable2. Modifíquelo para que la línea 18 substituya a la 17, recompile y pruebe su funcionamiento. Se recomienda ampliamente al lector consultar el API de Java para documentarse acerca del uso del constructor correspondiente y asegurase de comprender su funcionamiento.
2. Considere el Ejemplo HolaHilo2. Integre la línea 17 (que aparece comentada) para que forme parte del código, recompile y pruebe su funcionamiento. Se recomienda ampliamente al lector consultar el API de Java para documentarse acerca del uso del método setName( ) de la clase Thread y asegurase de comprender su funcionamiento; así como de comprender también la similitud y diferencias con respecto al ejercicio anterior.
3. Con base en los Ejemplos HolaHilo2 y HolaEjecutable2 realice, para cada uno, lo siguiente:
1. Genere más de un hilo (al menos tres) y póngalos en ejecución.
2. Genere un arreglo con capacidad para almacenar diez hilos, creé el número de hilos correspondiente y ponga a todos en ejecución.
   
4. Asegúrese de comprender por completo el Ejemplo HilosInteractuando. Posteriormente, modifique el ejemplo para:
• Cambiar los tiempos de método join (línea 67) una vez que haya consultado el API y comprenda más a fondo su funcionamiento.
• Cambiar el nombre del hilo de main, para que en la ejecución, en lugar de ver, por ejemplo "main: Todavía esperando...", sea vea: "Padre: Todavía esperando...".
• Pruebe con argumentos en la invocación del programa para modificar el tiempo de espera (paciencia) del hilo principal (main).
  
5. Considere el Ejemplo PruebaContador. Asegúrese de probar la equivalencia de las líneas 42-43 con la línea 44.
6. Para el Ejemplo PruebaContadorSincronizado, asegúrese de probar la equivalencia de las líneas 43-44 con la línea 45.
7. En la entrada Sincronización, se hace referencia a que un constructor no puede ser sincronizado. Pruebe dicha situación generando el error de sintaxis que debería generarse.
8. Considere y analice el Ejemplo MsLunch. Asegúrese de comprender la diferencia entre éste y las distintas versiones del ejemplo comentado en la entrada Sincronización.
9. Con base en las entradas Creación de hilos, Sincronización y los ejemplos correspondientes, escriba un programa que realice lo siguiente:
• Genere 6 hilos: 3 utilizando Thread y 3 utilizando Runnable.
• Cada hilo deberá incrementar 100 000 veces el valor de un contador compartido e imprimir su valor al finalizar.
• El hilo principal (main) deberá decrementar 600 000 veces el valor del contador compartido e imprimir su valor al finalizar.
• El hilo principal deberá, antes de iniciar sus decrementos, esperar (join) a cada hilo 50 milisegundos.
• El hilo principal deberá llamarse padre y los hilos creados: hijo1, hijo2, ... hijo 6.
  
• ¿Cuál debería ser el valor final del contador en un enfoque sincronizado y por qué?
  
10. Para el Ejemplo Interbloqueo, elimine la palabra reservada synchronized de ambos métodos ¿Que piensa que sucederá y por qué? Determine su respuesta antes de volver a compilar y ejecutar.
    
11. Considere, analice y comprenda el Ejemplo Interbloqueo2 sin ejecutarlo.
• ¿Puede determinar lo que hace? 
• ¿Se comprende la diferencia con el Ejemplo Interbloqueo?
• ¿Por qué hace lo que hace?
  

Creación de hilos.

   En Java hay básicamente dos formas de generar un nuevo hilo de ejecución:

1. Crear una instancia de la clase Thread.
2. Crear una instancia de una clase que sea ejecutable, es decir, una clase que implemente la interfaz Runnable.

   En esta entrada se presentarán dos ejemplos de cada una de estas formas.

Clase Thread.
   El Ejemplo HolaHilo muestra la creación de un hilo cuando una clase (HolaHilo) hereda de la clase Thread (línea 8).

   Todas las subclases de Thread deberían sobreescribir el método run( ), ya que la definición de dicho método establece el comportamiento que tendrá el hilo creado, es decir, el conjunto de acciones a realizar por el hilo, son definidas dentro de este método (líneas 10-12) que, para este caso, consiste únicamente en imprimir un mensaje en la salida estándar.

   Observe cómo en el método main (líneas 14-17) se crea, en la línea 15 un nuevo hilo de ejecución (hilo), mismo que se hecha a andar en la línea 16 a través del método start( ).

   El método start( ) hace que el hilo receptor del mensaje inicie su ejecución, dentro de esta inicialización del hilo ocurren distintos aspectos de gestión que la máquina virtual de Java tiene que realizar para que las cosas funcionen, como la invocación al método run( ) del hilo correspondiente.

   Es importante hacer notar al lector que nunca hay un llamado explícito al método run( ), sino que ocurre un llamado implícito como parte de las gestiones y acciones que realiza el método start( ).

   Por último, el Ejemplo HolaHilo2 muestra una variación del ejemplo anterior.

   En las líneas 11 y 19 se ha hecho uso del método currentThread( ) de la clase Thread, el cuál regresa la instancia del hilo que se está ejecutando (hilo actual), esto con la finalidad de que el método getName( ) obtenga el nombre asignado a dicha instancia. Esta propiedad del hilo en cuestión es utilizada para imprimirla en la salida estándar en las líneas 12 y 20 respectivamente.

   Finalmente, la línea 17 (comentada) utiliza el método setName( ) para asignarle un nombre al hilo ("Hilo Jr."). Se deja como ejercicio para el lector descomentar dicha línea, recompilar, ejecutar y comparar las salidas de los ejemplos correspondientes y comprender la diferencia.

Interfaz Runnable.
   El Ejemplo HolaEjecutable muestra la creación de un hilo utilizando la interfaz Runnable (línea 8).

   Una interfaz en Java es básicamente un contrato que la clase que la implementa debe cumplir, es decir, la clase que implementa una interfaz se compromete a definir todos los métodos que establezca dicha interfaz.

   Para el caso de la interfaz Runnable, el único método que hay que definir es el método run( ) (líneas 10-12), cuya única misión es imprimir un mensaje en la salida estándar.

   En la línea 15 se crea una instancia de la clase HolaEjecutable (ejecutable), misma que es utilizada como argumento para el constructor del hilo creado en la línea 16.

   Si todo sale bien, en la línea 17 existen dos hilos de ejecución:

1. El de main.
2. El que se creo en la línea 16 (hilo).

   Note aquí también que nunca hay un llamado explícito al método run( ), sino que más bien hay un llamado implícito en alguna parte del método start( ) (línea 17), el cuál es el encargado de realizar la gestión necesaria para que el hilo recién creado se introduzca en el entorno de ejecución de la máquina virtual de Java. Se recomienda ampliamente al lector el consultar el API para obtener más detalles acerca de la clase Thread y de la interfaz Runnable.

   Finalmente el Ejemplo HolaEjecutable2 muestra una variación del ejemplo descrito con anterioridad. Note particularmente las líneas 11 y 20 en donde se ha hecho uso del método currentThread( ) de la clase Thread, el cuál regresa la instancia del hilo que se está ejecutando (hilo actual); por otro lado, el método getName( ) obtiene el nombre asignado a dicha instancia. Esta propiedad del hilo en cuestión es utilizada para imprimirla en la salida estándar en las líneas 12 y 21 respectivamente.

El intercambio de la líneas 17 y 18 para que mutuamente se excluyan se deja como ejercicio para el lector.

Hilos.

   En un enfoque tradicional de programación, las sentencias y expresiones se ejecutan de manera secuencial, en la programación concurrente, este mismo grupo de sentencias y expresiones se ejecutan de manera concurrente, entendiéndose por concurrencia a la capacidad de las diferentes partes o unidades de un programa para ejecutarse fuera de orden o en orden parcial sin afectar el resultado final.

   Abusando de la simplificación, puede entenderse a la concurrencia como la capacidad de un software o equipo de cómputo para realizar más de una tarea al mismo tiempo.

   En la programación concurrente existen dos unidades básicas de ejecución: procesos e hilos. En el lenguaje de programación Java la programación concurrente se basa principalmente en hilos (threads) aunque estos están estrechamente relacionados con los procesos.

    Los detalles y aspectos relacionados con los procesos gestionados por un sistema operativo quedan fuera de los alcances de este blog; sin embargo, es preciso que el lector tenga al menos una idea general de los aspectos inherentes relacionados con los procesos, razón por la cual se esbozarán algunos conceptos.

   Un proceso es una instancia en ejecución de un programa. En este sentido, un proceso es un entorno de ejecución autocontenido y habitualmente tiene un conjunto de recursos completos, privados, básicos y fundamentales relacionados con su ejecución; así, cada proceso tiene además su propio espacio de memoria.

   Los hilos son también llamados procesos ligeros. Tanto los hilos como los procesos proveen un entorno de ejecución sin embargo, la creación de un nuevo hilo requiere en lo general de menos recursos que la creación de un nuevo proceso.

   Los hilos habitualmente existen dentro de un proceso. Cada proceso tiene al menos un hilo denominado hilo principal. Los hilos comparten los recursos asignados al proceso, tales como la memoria y los archivos asociados por ejemplo, lo cual los hace muy eficientes pero potencialmente problemáticos.

   Desde el punto de vista de los programadores de aplicaciones Java, todo inicia con un solo hilo: main, y este hilo tiene la capacidad de crear nuevos hilos y a partir de ahí generar una programación concurrente a través de dichos hilos.

   Cada hilo en Java está asociado con una instancia de la clase Thread por lo que se recomienda ampliamente al lector revisar la especificación de dicha clase en el API y todo el apartado relacionado con la concurrencia de los tutoriales de Java.

By Hooman Mallahzadeh - Own work, CC BY-SA 4.0, https://commons.wikimedia.org/w/index.php?curid=100534098

Atrapando y manejando excepciones.

   Esta entrada se basa en la descripción del siguiente ejemplo:

      // Note: This class will not compile yet.
      import java.io.*;
      import java.util.List;
      import java.util.ArrayList;

      public class ListOfNumbers {
          private List<Integer> list;
          private static final int SIZE = 10;

          public ListOfNumbers ( ) {
              list = new ArrayList<Integer>(SIZE);
              for (int i = 0; i < SIZE; i++) {
                   list.add(Integer.valueOf(i));
              }
          }

          public void writeList( ) {
// The FileWriter constructor throws IOException, which must be caught.
              PrintWriter out = new PrintWriter(new FileWriter("OutFile.txt"));

              for (int i = 0; i < SIZE; i++) {
               // The get(int) method throws IndexOutOfBoundsException, which must be caught.
                  out.println("Value at: " + i + " = " + list.get(i));
              }
              out.close();
          }
      }

   El ejemplo ha sido tomado y adaptado para cumplir con las nuevas especificaciones del API de The Java Tutorials (Catching and Handling Exceptions). Puede descargar la versión ListOfNumbers1, misma que no compila debido a que no realiza el adecuado manejo de las excepciones que podrían generarse, y la versión corregida ListOfNumbers, la cual contiene ya los elementos necesarios para el adecuado manejo de dichas excepciones.

    Recomiendo al lector remitirse en este momento al Ejercicio 3 de la entrada de Ejercicios selectos para comparar este ejemplo con una versión alternativa que compacta las cláusulas catch en una sola.

Excepciones.

   El lenguaje de programación Java utiliza excepciones para manejar errores y otros eventos excepcionales. Un programa en Java puede utilizar excepciones para indicar que ha ocurrido un evento excepcional, de hecho, el término excepción es la forma corta de decir evento excepcional.

   En este sentido, una excepción es un evento que ocurre durante la ejecución de un programa en Java, que interrumpe el flujo normal de ejecución del programa (vea What is an Exception).

   Cuando un error ocurre dentro de un método, el método crea un objeto (objeto de excepción) y lo coloca en el entorno de ejecución, el cual contiene información acerca del error, incluyendo su tipo y el estado del programa cuando ocurrió el error. A éste proceso se le denomina lanzar una excepción.

   Después de que un método lanza una excepción el entorno de ejecución intenta encontrar a alguien (manejador de excepción) que la atrape y la maneje:

La pila de invocación de métodos y la búsqueda del manejador de excepción (adaptada de What is an Exception).

   Para lanzar un excepción se debe hacer uso de la cláusula throw adjunta a un objeto de excepción (descendiente de la clase Throwable) para proporcionar información específica acerca del evento excepcional que ocurrió.

   Un código válido en el lenguaje de programación Java debe respetar la cláusula catch (también llamado requisito de especificación), lo cual significa que el código que podría lanzar ciertas excepciones debe estar encerrado por alguna de las siguientes:

• Una sentencia try que atrapa la excepción.
• Un método que especifica que puede lanzar la excepción.

  Cabe mencionar que no todas las excepciones están sujetas a esta situación, y la razón es que existen tres categorías básicas de excepciones y sólo una de ellas está sujeta a dicho requisito (excepción comprobada):

1. Excepción comprobada (checked exception): condiciones excepcionales que un programa o aplicación bien escrita debe considerar.
2. Error: condiciones excepcionales que son externas al programa o la aplicación; usualmente no es posible anticiparlas o recuperarse de ellas (mal funcionamiento del hardware o del sistema).
3. Excepción en tiempo de ejecución (runtime exception): condiciones excepcionales que son internas al programa o la aplicación sin que la aplicación pueda anticiparlas o recuperarse de ellas (errores lógicos a bugs).

   Las excepciones de error y de tiempo de ejecución se conocen comúnmente como excepciones no comprobadas o verificadas (unchecked exceptions).

   Un programa puede atrapar excepciones por medio de la combinación de los bloques try, catch y finally:

1. El bloque try identifica un bloque de código en el que una excepción puede ocurrir.
2. El bloque catch identifica un bloque de código, conocido como manejador de excepción (exception handler), que puede atrapar y manejar un tipo específico de excepción.
3. El bloque finally identifica un bloque de código que en general se garantiza que se ejecutará independientemente de si se generó (catch) o no (try) la excepción, por lo que es el lugar preciso para cerrar archivos, liberar recursos y cualquier tarea de limpieza que se requiera como parte de la ejecución del código que se ejecutó en el try.

   Una cláusula try podría contener al menos un bloque catch o finally, y múltiples bloques catch.

    Como un primer acercamiento, considere inicialmente el Ejemplo DivisionSinManejoExcepcion el cual muestra la posible generación de una excepción no verificada (unchecked) si se intenta hacer una división por cero (línea 16). La excepción que podría generarse es de la clase ArithmeticException; pero todavía más: ¿Qué sucede si en lugar de un número se introduce una letra o una cadena? Se conmina al lector a probar lo hasta aquí expuesto.

    El Ejemplo DivisionConManejoExepcion toma ya en consideración lo expuesto en el párrafo anterior e ilustra el uso de la cláusula try-catch líneas (27-43). El manejo de excepciones consiste en hacer que un programa, ante una situación anormal o fuera del flujo esperado de ejecución, pueda recuperarse y continuar y no simplemente terminar. Note que con excepción de las cláusula en cuestión, el programa es esencialmente el mismo que el anterior, con la consideración del ajuste de una bandera para determinar o no la continuación del programa (líneas 24, 35 y 44). Este ejemplo, además del manejo de la excepción aritmética, también considera la excepción InputMismatchException para el caso de que no se proporcionen los números enteros como entrada sino alguna otra cosa.

    ¿En qué orden debería colocarse las excepciones?, ¿cuál debemos poner primero? Las recomendaciones, una vez que se asume que se han localizado las excepciones más pertinentes, serían dos:

1. Atrape primero la excepción que a su consideración tenga más probabilidad de ocurrir, después la segunda y así sucesivamente.
2. Coloque primero las excepciones más específicas y al final las más generales; para ello, deberá consultar la jerarquía de clases correspondiente.
   

   Finalmente, además de invitar al lector a revisar el API de Java para la revisión y familiarización de las excepciones comentadas en esta entrada, es importante resaltar que la decisión de utilizar excepciones propias comprobadas (checked) o no (unchecked) debería seguir esta guía: si un cliente o usuario de nuestras clases tiene una expectativa de recuperarse razonablemente de una excepción, entonces la excepción debería ser del tipo comprobada (checked); por otro lado, si no puede hacerse nada para recuperarse de la excepción ésta debería ser no comprobada (unchecked). Para más información vea Unchecked Exceptions - The controversy.

Pilas (implementación).

   La representación de una pila, como una secuencia de nodos, se muestra en la siguiente figura. Los detalles de su implementación se desarrollarán a continuación.

Abstracción de una pila como una secuencia de nodos.

 Pila primitiva.

   Esta sección describe la implementación de una pila primitiva. Se ha denominado de esta forma debido a que implementa una estructura de datos que almacena un tipo de dato primitivo: int.

   La definición de la clase fundamental para la implementación de la estructura de datos se muestra en el Ejemplo NodoPrimitivo. Los detalles de este tipo de implementación de clases autorreferidas se han discutido con anterioridad en la entrada Abstracción de estructuras de datos y no se repetirán aquí, por lo que se sugiere al lector que la revise nuevamente y se tome el tiempo necesario para comparar el Ejemplo NodoPrimitivo con el Ejemplo Nodo antes de continuar.

   La implementación de la estructura de datos pila se muestra en el Ejemplo PilaPrimitiva, y su explicación se centrará únicamente en los métodos push, pop, estaVacia e imprime.

   El método estaVacia (líneas 37-39) realiza una verificación bastante simple: si el tope de la pila es igual a null, regresa verdadero (está vacía), si no, regresa falso (existe al menos un elemento).

   El método push por su parte (líneas 18-23), recibe como argumento el elemento a insertar en la pila (elemento), y se apoya del método estaVacia y de los constructores para realizar la inserción:

• Si la pila está vacía (línea 19), se crea un nuevo nodo con el elemento correspondiente (línea 20) para el atributo dato, y null en su atributo siguiente.
• Si la pila no está vacía (línea 21), se crea un nuevo nodo con el elemento correspondiente para el atributo dato y con el tope actual en su atributo siguiente (línea 22). Así mismo, note que el tope es actualizado para hacer referencia al nodo recién creado.

   Ahora bien, observe que el método pop (líneas 26-34) posee una característica particular: el método lanza (throws) una excepción ExcepcionEDVacia (línea 26) lo cual quiere decir que, en determinadas condiciones, el método puede lanzar una excepción; para el caso del método pop, la condición consiste en intentar eliminar un elemento de la pila cuando ésta está vacía.

   La excepción ExcepcionEDVacia definida en el Ejemplo ExcepcionEDVacia es en realidad bastante simple, ya que delega toda la responsabilidad a RuntimeException que es la clase de la que deriva, y lo único que hace es establecer un identificador para la excepción a través de sus constructores, los cuales en realidad utilizan el constructor de la super clase (clase padre) a través de la cláusula super. Es importante que el lector recuerde esta excepción, ya que será la excepción que utilizarán todas las estructuras de datos que se implementan en el blog.

   Ahora bien, cuando el programador se enfrenta a la necesidad de lanzar una excepción cabe la pregunta ¿y de qué tipo? Se puede utilizar una excepción escrita por alguien más o se puede hacer una propia. Se debería hacer clases de excepción propias cuando se responda de manera afirmativa a alguna de las siguientes preguntas, de otra forma, debería usarla una excepción escrita por alguien más (vea Creating Exception Classes):

• ¿Necesita un tipo de excepción que no está representada en el API de Java?
• ¿Sus usuarios se verán beneficiados si pueden diferenciar sus excepciones de aquellas lanzadas por clases escritas por alguien más?
• ¿Su código lanza más de una excepción relacionada?
• Si utiliza una excepción escrita por alguien más, ¿sus usuarios tendrán acceso a esas excepciones?
• ¿Su paquete de clases debería ser independiente y auto contenido?

   Continuando con el Ejemplo PilaPrimitiva, el método pop verifica (línea 27) si la pila está vacía, si lo está, crea y lanza la excepción correspondiente (línea 28); en caso contrario, recupera el dato almacenado (línea 30), y desecha el nodo correspondiente al hacer que el tope haga ahora referencia al elemento siguiente del tope actual (línea 31), para finalmente regresar el dato recuperado (línea 33). En Java no hay una eliminación o liberación explícita de memoria, dicha labor es delegada al recolector de basura el cual se encarga, grosso modo, de identificar aquellos objetos que no estén siendo referidos para entonces liberar la memoria que utilizan.

   Por último, en el método imprime (líneas 42-57), si la estructura de datos está vacía (línea 43), se reporta (línea 44); en caso contrario, se realiza un recorrido por todos los nodos de la estructura para imprimir su contenido (líneas 47-54).

   La clase de prueba para la pila primitiva del Ejemplo PilaPrimitiva, se presenta en el Ejemplo PruebaPila. Observe cómo en la línea 6 se crea la pila y se utiliza un constructor sin argumentos.

   Las líneas 9-12 realizan la inserción en la pila de los números del cero al nueve; por cada inserción se imprime todo el contenido de la pila, como se muestra en la siguiente figura:

Ejemplo de inserción de elementos en la pila primitiva. Se muestra la salida del Ejemplo PruebaPila.

    Por otro lado, las líneas 15-24 realizan la eliminación de los elementos de la pila. Dicho fragmento de código intenta eliminar once elementos (líneas 17-18) de la pila (recuerde que sólo fueron insertados diez elementos, por lo que al intentar eliminar el décimo primero, se generará la excepción ExcepcionEDVacia), y dado que el método pop puede lanzar una excepción, el código involucrado en la eliminación debe estar dentro de una cláusula try-catch-finally, la cual permite atrapar (cachar) las excepciones que un método pudiera lanzar.

   Si se genera un excepción ExcepcionEDVacia, ésta es atrapada y el flujo de control se envía al ámbito de la cláusula catch en donde se realiza el correspondiente tratamiento de la excepción. Para el caso del Ejemplo PruebaPila el manejo de la excepción consiste únicamente en imprimir la secuencia de eventos (en forma de pila) que dieron lugar a la excepción; sin embargo, es importante aclarar que el manejo de una excepción puede ser tan elaborado como en un momento dado se requiera.

   La salida correspondiente a la eliminación de elementos de la pila primitiva, se muestra en la siguiente figura:

Ejemplo de eliminación de elementos en la pila primitiva. Se muestra la salida del Ejemplo PruebaPila.

Pila genérica.

   Esta sección generaliza la implementación de una pila de tal forma que la estructura de datos tenga la capacidad de almacenar objetos genéricos; es decir, objetos de cualquier clase.

   Como primer paso, es preciso que el lector se tome el tiempo que considere necesario para comparar el Ejemplo NodoPrimitivo discutido en la sección anterior, con el Ejemplo NodoG. Es importante resaltar que, aunque distintos, ambos ejemplos son esencialmente equivalentes.

La primera diferencia que salta a la vista, además del nombre de la clase, es la notación <T>. Dicha notación se utiliza en Java para especificar que la clase gestiona objetos genéricos, es decir, que el tipo o la clase de los objetos que almacena no está especificada en la definición de la misma, sino que se especifica en el momento de la instanciación del objeto (observe la línea 6 del Ejemplo PruebaPilaGenerica).

   La línea 7 del Ejemplo NodoG define que la clase del atributo dato es T, es decir, un genérico, y por lo tanto el atributo siguiente es una referencia a un objeto que almacena objetos genéricos.

   Observe cómo ahora los constructores y los métodos de tipo set reciben como argumentos objetos genéricos T (líneas 10, 14 y 19), y referencias a objetos que a su vez almacenan objetos genéricos (líneas 14 y 27); mientras que los métodos de tipo get regresan genéricos (línea 23), o referencias a objetos que almacenan objetos genéricos (línea 31).

   Ahora bien, las consideraciones hechas para el Ejemplo NodoG respecto a los genéricos, son las mismas que debe tomar en cuenta para el Ejemplo Pila, por lo que una vez más se pide encarecidamente al lector que compare este último con el Ejemplo PilaPrimitiva discutido en la sección anterior tomando en consideración lo explicado hasta este momento para los genéricos.

   Observe que en ninguna parte del Ejemplo Pila se hace explícita una clase específica para el genérico T, por lo que también aquí se hace una gestión de genéricos en directa relación con los genéricos utilizados en el Ejemplo NodoG.

   En resumen, la clase NodoG del Ejemplo NodoG define nodos que almacenan objetos genéricos (nodos genéricos), los cuales son utilizados de manera conveniente por la clase Pila del Ejemplo Pila para conformar una estructura de datos dinámica que almacena objetos o nodos genéricos en forma de pila.

   El Ejemplo PruebaPilaGenerica muestra la clase de prueba para la pila genérica del Ejemplo Pila. La línea más importante del Ejemplo PruebaPilaGenerica es la línea 6, ya que es en ella en donde finalmente se define la clase de objetos que contendrá (almacenará) la pila: Integer.

   Consulte la sección Genéricos de la entrada Ejemplos selectos de transición para ampliar un poco más la información y los detalles acerca de los genéricos en Java. En el Ejemplo PilaC se muestra la implementación alternativa de una pila utilizando un ArrayList del API de Java; mientras que en el EjemploPruebaPilaC se presenta su correspondiente clase de prueba. Adicionalmente, se proporcionan al lector dos ejemplos adicionales que utilizan colecciones (estructuras de datos) del API: Stack y ArrayDeque (Deque); tómese el tiempo de estudiarlos y revisar la información correspondiente en el API.

   Finalmente, asegúrese de comprobar que la salida del Ejemplo PruebaPilaGenerica corresponde, en esencia, con la salida del Ejemplo PruebaPila para la inserción de datos (push), y que lo correspondiente ocurre también para la eliminación de elementos (pop).

ABB (implementación).

   Esta entrada presenta la implementación de un ABB en base a dos enfoques respecto a la inserción de elementos:

1. Enfoque recursivo.
2. Enfoque iterativo.

   Para ambas implementaciones se utiliza la clase NodoABB definida en el Ejemplo NodoABB, por lo que será la primera clase que se describirá.

   La clase NodoABB define un nodo capaz de almacenar objetos genéricos. Cada nodo definido por la clase tiene la forma de cada uno de los nodos de la siguiente figura:

Árbol binario de búsqueda (ABB) conformado por objetos de la clase NodoABB.

 

    Observe además que cada objeto instanciado tendrá dos referencias a objetos como él, las cuales representarán referencias hacia el subárbol izquierdo (nodoIzquierdo) y hacia el subárbol derecho (nodoDerecho).

   Los detalles restantes deberían resultarle familiares al lector, ya que en esencia se refieren a un constructor y a los métodos de tipo set y get para cada uno de los atributos. Asegúrese de comprender el Ejemplo NodoABB en su totalidad antes de continuar.

Enfoque recursivo.

   Probablemente el enfoque más común para la implementación de un ABB debido a la naturaleza inherente a la definición de dicha estructura de datos, sea el enfoque basado en la recursividad.

   El Ejemplo ABBr muestra la definición de la clase ABBr, la cual es en esencia la implementación de la representación definida en el diagrama de clases UML presentado en la entrada ABB (representación y diseño).

   El estudio y la comprensión de la implementación de los métodos de recorrido para un árbol binario de búsqueda (líneas 34-68), se dejan como ejercicio para el lector.

   El método inserta (líneas 13-18), crea la raíz del árbol (línea 15) si el ABB está vacío (línea 14), i.e. no existe. En caso contrario, delega la responsabilidad de la inserción de elemento dentro de arbol al método privado recursivo insertaR (línea 17).

   Por su parte, la idea del método insertaR (líneas 21-32) es verificar la relación de orden de elemento respecto del dato almacenado en el nodo actual, y entonces:

• Si elemento es menor (línea 22), debe ser insertado en el subárbol izquierdo.
• Si el subárbol izquierdo está vacío o disponible (línea 23), se crea un nuevo nodo con elemento como dato y se asigna como hijo izquierdo (línea 24). Si no está vacío (línea 25), se recorre el subárbol izquierdo de manera recursiva (línea 26) para encontrar la posición apropiada para elemento dentro del subárbol.
• Si elemento es mayor (línea 27), debe ser insertado en el subárbol derecho.
• Si el subárbol derecho está vacío o disponible (línea 28), se crea un nuevo nodo con elemento como dato y se asigna como hijo derecho (línea 29). Si no está vacío (línea 30), se recorre el subárbol derecho de manera recursiva (línea 31) para encontrar la posición apropiada para elemento dentro del correspondiente subárbol.

   La clase de prueba para la clase ABBr del Ejemplo ABBr se muestra en el Ejemplo PruebaArbol.

   La clase PruebaArbol del Ejemplo PruebaArbol utiliza la clase Random del API para generar un número aleatorio (línea 14) dentro de un rango específico; el cual, además de presentarse en la salida estándar (línea 15), representa el valor a ser insertado dentro del árbol binario de búsqueda (línea 16).

   Finalmente, el Ejemplo PruebaArbol realiza los tres recorridos más convencionales definidos para un ABB (líneas 19-27). Es ampliamente recomendable que el lector realice varias ejecuciones de la clase PruebaArbol y corrobore la salida con inserciones y recorridos realizados a papel y lápiz.

Una posible salida de los Ejemplos PruebaArbol y Prueba ABB.

 

    Una posible salida para el Ejemplo PruebaArbol se muestra en la figura anterior.

Enfoque iterativo.

   Un enfoque alternativo para la implementación de la operación de inserción en un árbol binario de búsqueda, es utilizar un ciclo en lugar de recursividad.

   El enfoque propuesto es casi tan compacto como el recursivo pero mucho más eficiente. La implementación sin recursividad del ABB representado en el diagrama de clase de la entrada ABB (representación y diseño) se presenta en el Ejemplo ABB.

   Al igual que antes, el estudio y la comprensión de la implementación de los métodos de recorrido (líneas 34-68), se dejan como ejercicio para el lector.

   El método inserta (líneas 13-32), crea la raíz del árbol (línea 15) si el ABB está vacío (línea 14), i.e. no existe. En caso contrario, se genera una referencia alterna (línea 17) para recorrer el árbol (línea 18).

   Al igual que antes, la idea es verificar la relación de orden de elemento respecto del dato almacenado en el nodo actual, y entonces:

• Si elemento es menor (línea 19), debe ser insertado en el subárbol izquierdo.
• Si el subárbol izquierdo está vacío o disponible (línea 20), se crea un nuevo nodo con elemento como dato y se asigna como hijo izquierdo (línea 21). Si no está vacío (línea 22), se cambia la referencia del subárbol en cuestión (abb), y se recorre el subárbol izquierdo (línea 23) para encontrar la posición apropiada para elemento dentro del árbol.
• Si elemento es mayor (línea 24), debe ser insertado en el subárbol derecho.
• Si el subárbol derecho está vacío o disponible (línea 25), se crea un nuevo nodo con elemento como dato y se asigna como hijo derecho (línea 26). Si no está vacío (línea 27), se cambia la referencia del subárbol en cuestión (abb), y se recorre el subárbol derecho (línea 28) para encontrar la posición apropiada para elemento dentro del ABB.
• Finalmente, si el elemento no fue menor ni mayor, entonces por tricotomía de los números no le queda otra más que ser igual, en cuyo caso no hay nada por hacer mas que terminar (líneas 29 y 30).

   La clase de prueba para la clase ABB del Ejemplo ABB se muestra en el Ejemplo PruebaABB.

   Al igual que antes, la clase PruebaABB del Ejemplo PruebaABB utiliza la clase Random del API para generar un número aleatorio (línea 14) dentro de un rango específico, el cual además de presentarse en la salida estándar (línea 15), representa el valor que será insertado dentro del árbol binario de búsqueda (línea 16).

   Finalmente, el Ejemplo PruebaABB también realiza los tres recorridos más convencionales definidos para un ABB (líneas 19-27). Una vez más, se recomienda ampliamente que el lector realice varias ejecuciones de la clase PruebaABB y corrobore la salida con inserciones y recorridos realizados a papel y lápiz.

Consideraciones adicionales.

   Una de las aplicaciones más útiles de las colas, las colas de prioridad y de las listas vinculadas es la simulación.

   Un programa de simulación modela una situación del mundo real para aprender u obtener algo de ella. En una simulación, cada objeto y acción del mundo tiene su representación en el programa.

   Si la simulación es precisa, el resultado del programa reflejará el resultado de las acciones que se simulan, por lo que será posible comprender lo que ocurre en una situación del mundo real sin la necesidad de observar su ocurrencia en el mundo real.

   Algunos de los contextos en los que es posible aplicar técnicas de simulación utilizando las estructuras de datos anteriormente mencionadas son:

• Bancos.
• Líneas aéreas.
• Casetas de cobro de autopistas.
• Terminal de autobuses.
• Líneas de espera en general.
• Un largo etcétera.

   Las listas enlazadas completan el espectro de las estructuras de datos lineales que se estudiarán en este blog, mismo que dio inició con las pilas. Debe notar que en éste sentido se ha ido avanzando de lo particular hacia lo general, ya que como pudo apreciarse, las listas enlazadas son las estructuras de datos que menos restricciones tienen en su definición y operaciones.

   Tanto los usos como las aplicaciones de las pilas, las colas de espera y las listas enlazadas son prácticamente infinitas, ya que están limitadas únicamente por la imaginación o la capacidad del programador.

 

Iteradores.

    Un iterador es un objeto que permite al programador recorrer un contenedor de una manera determinada. Puede verse también como la entidad que le permite a un programa "caminar" o recorrer una estructura de datos desde el exterior.

 

Diagrama de clases de la estructura del patrón de diseño de un iterador [Wikipedia].

 

    En el contexto en que se ha venido manejado en el blog, un iterador regresará el valor almacenado (dato) en los nodos internos de la estructura de datos.

    Iteradores en Java.

    El API de Java proporciona distintas colecciones que pueden ser recorridas con iteradores. Cualquier clase que implemente la interfaz Iterator debe ser capaz de regresar un iterador que permita recorrer los elementos que almacena.

    A modo de ejemplo se hará una modificación al Ejemplo Lista estudiado en la entrada correspondiente a la implementación. Por simplicidad y para tener un ejemplo completamente funcional, se proporcionará como una carpeta comprimida que contiene todos los archivos necesarios para su ejecución. Sólo se resaltarán los cambios en dos clases, y se deja como ejercicio al lector hacer la comparación correspondiente con el ejemplo original:

1. Lista:
1. Linea 10: implementación de la interfaz Iterator.
2. Línea 13: objeto que se regresará como iterador (referencia externa).
3. Línea 22: inicialización del iterador en el constructor.
4. Líneas 104-109: implementación del método next de la interfaz Iterator. Este método se encarga de obtener el siguiente dato de la lista, regresarlo y avanzar hacia el siguiente nodo.
5. Líneas 111-113: implementación del método hasNext de la interfaz Iterator. Este método se encarga de determinar si hay más elementos (true) o no (false) en la estructura de datos.
6. Líneas 115-118: implementación del método iterator de la interfaz Iterator. Este método se encarga de iniciar un iterador al principio de la estrictura de datos para poderla recorrer desde el exterior. Note que el método regresa una referencia al mismo objeto (this) ya que su clase (Lista) implementa la interfaz Iterator y en ella están definidos los métodos requeridos para gestionar el iterador.
   
2. PruebaLista:
1. Línea 5: inclusión de la interfaz Iterator del paquete java.util.
2. Líneas 19-22: uso del iterador implementado en la clase Lista.

    Adicional a la interfaz Iterator, existe también en el API la interfaz Iterable (más reciente), que permite hacer uso de ciclos del tipo for-each. El Ejemplo ListaIterable muestra su implementación y uso y, dado que los cambios son menores y relativamente simples respecto del ejemplo anterior, se deja su análisis y estudio como ejercicio para el lector.

    Iteradores en C++. 

    La idea de un iterador debería ser el poder recorrer la colección o estructura de datos en cuestión desde el exterior sin tener que conocer los detalles de su implementación. En este sentido, un iterador será un objeto que haga referencia a un elemento dentro del contenedor (la lista) y, dado que finalmente es un apuntador, puede ser utilizado para acceder al elemento al que se refiere y para moverse a través de todos los elementos del contenedor.

    El Ejemplo lista_iterador se basa en general en el Ejemplo lista estudiado con anterioridad. Ahora bien, el primero ha sido rediseñado en su totalidad, por lo que podría resultar conveniente al lector comprender y analizar antes el Ejemplo lista2.

    Para el ejemplo en turno se han incorporado también algunas de las características más recientes del lenguaje C++, por lo que los cambios más sobresalientes se enuncian a continuación, manteniendo el énfasis en la implementación respecto al iterador:

• Implementación básica del iterador (líneas 67-94):
• Apuntadores que representan las referencias la nodo actual y anterior de la lista (líneas 69-70).
• Constructores y mecanismos de inicialización del iterador (líneas 73-74).
• Implementación de los tres operadores fundamentales (se puede y deben implementar otros):
• Operador de preincremento: ¿qué debe hacer el iterador cuando se incremente? (líneas 77-83).
• Operador de diferencia: ¿cómo sabe un iterador que es distinto de otro? (líneas 86-88).
• Operador de desreferencia: ¿qué regresa el iterador cuando se acceda a lo que apunta? (líneas 91-93).
• Incorporación de mecanismos que permitan obtener un iterador al inicio de la colección y poder determinar su fin (líneas 184-186).
• Uso del iterador:
• Uso del esquema para cada (for-each) en las líneas 206-207.
• Uso del esquema tradicional del iterador en las líneas 211-216.

    El ejemplo en turno incorpora algunas características nuevas en las que vale la pena documentarse, como el uso de noexcept, inline, auto, etc., se deja como ejercicio para el lector su documentación.

 

    Finalmente, cabe mencionar que una implementación más robusta de iteradores requiere de un conocimiento más amplio, sobre todo si se espera que nuestra estructura de datos pudiese ser utilizada por otros programadores o por los algoritmos de la biblioteca estándar. Lo expuesto aquí es sólo una implementación básica, ya que existen distintos tipos de iteradores, operadores de acceso, consideraciones de recorrido, etcétera. Un punto inicial y de buena referencia puede ser la sección de iteradores de cplusplus, en dónde podrá encontrar además la información referente a los otros aspectos utilizados en el ejemplo.

Colas de prioridad.

   La cola de prioridad es una estructura de datos en la que el ordenamiento intrínseco de los elementos, determina el resultado de la aplicación de sus operaciones básicas o primitivas.

   En este sentido, existen dos tipos de colas de prioridad:

1. Cola de prioridad ascendente.
2. Cola de prioridad descendente.

   Ambas estructuras de datos redefinen la forma de operación convencional respecto de una cola de espera, por lo que serán estudiadas de manera separada.

Cola de prioridad ascendente.

   La cola de prioridad ascendente es un tipo de estructura de datos en el que la inserción de los elementos se realiza de manera convencional, pero la eliminación se realiza en base al menor de los elementos almacenados en ella. Para que ésto sea posible, los elementos que almacena la estructura de datos deben tener una relación de orden; es decir, deben poseer algún mecanismo que permita compararlos entre sí.

   La siguiente figura muestra la relación de clases en UML para una cola de prioridad ascendente con la redefinición o sobre escritura (override) del método elimina. Observe cómo se ha instrumentado la redefinición de dicho método por medio del mecanismo de la herencia, y que las relaciones previamente existentes se conservan (compare con el diagrama de clases presentado para las colas de espera en la entrada Colas de espera (definición)).

 

Diagrama de clases UML para una cola de prioridad ascendente con la redefinición (override) del método elimina.

    Otro tipo de representación para la cola de prioridad ascendente, consiste en mantener ordenados los elementos de manera ascendente durante la inserción y conservar la operación de eliminación de la forma convencional. Dicha representación se expresa en UML como se muestra en la siguiente figura:

 

Diagrama de clases UML para una cola de prioridad ascendente con la redefinición (override) del método inserta.

    En resumen, en una cola de prioridad ascendente los elementos se recuperan (eliminan) en orden ascendente respecto de la relación de orden que guarden entre sí. Ahora bien, para objetos con una relación de orden inherente a ellos, como un objeto de la clase Integer o de la clase Float por ejemplo, la comparación es posible pero, ¿qué ocurre con objetos de la clase String del API de Java, o con las clases Persona y Cientifico definidas en la entrada POO (herencia) por ejemplo?

   Implementación.

   En la orientación a objetos existe un concepto relacionado con la herencia: la herencia múltiple. La herencia múltiple básicamente es la capacidad de una clase de heredar los atributos y métodos de más de una clase; sin embargo, el lenguaje de programación Java no incluye en su gramática dicha capacidad, aunque por otro lado, incorpora un mecanismo que permite que una clase se comprometa, a través de una especie de contrato, a implementar en métodos las operaciones declaradas o establecidas en una interfaz (interface). La interfaz Comparable del API de Java compromete u obliga a las clases que la implementan, a establecer una relación de orden entre los objetos que la implementen. Dicha relación de orden es arbitraria y está en función únicamente del interés o de las necesidades específicas de la clase en cuestión.

   Para ilustrar lo anterior, considere el Ejemplo ColaAscendente el cual implementa una cola de prioridad ascendente sobre escribiendo o redefiniendo (override) el método inserta tal y como se propone en el diagrama de clases UML de la figura anterior. Note el uso de la interfaz Comparable. Observe con detenimiento la línea 6 la cual, en el contexto de lo anterior, podría interpretarse de la siguiente manera:

La clase ColaAscendente es una subclase, clase hija o clase derivada de la clase Cola, gestiona objetos genéricos T que definan o establezcan una relación de orden a través de la implementación del método compareTo declarado en la interfaz Comparable.

   Observe que el mensaje o la invocación del método compareTo ocurre en la línea 21 del Ejemplo ColaAscendente, y que la idea general del método inserta (líneas 15-35) consiste en recorrer la secuencia de nodos (líneas 21-24) mientras haya nodos por procesar y no se haya encontrado el lugar correspondiente para el elemento a insertar (línea 21). En este sentido, el método compareTo compara el objeto receptor del mensaje con el objeto proporcionado como argumento; dicho método regresa uno de tres posibles valores (consulte en el API de Java la interfaz Comparable para ampliar y complementar la información al respecto):

1. Un entero negativo (< 0) si el objeto receptor del mensaje es menor que el objeto proporcionado como argumento.
2. Cero (0) si el objeto que recibe el mensaje es igual al objeto proporcionado como argumento.
3. Un entero positivo (> 0) si el objeto receptor del mensaje es mayor que el objeto proporcionado como argumento.

   Es importante que el lector comprenda que el método compareTo es definido en la clase que quiera establecer una relación de orden para sus objetos, es decir, los objetos de la clase genérica T deberán tener la definición (código) de dicho método.

   Continuando con la explicación del método inserta del Ejemplo ColaAscendente, note que el método hace uso de objetos auxiliares (líneas 16, 18 y 19), para poder realizar el ajuste de las referencias correspondientes en las líneas 26-34. Aquí cabe mencionar que, aunque dichos objetos pudieron haber sido definidos como atributos de la clase ColaAscendente, en realidad no representan una característica o cualidad inherente a los objetos que se deriven de dicha clase, sino que más bien son entidades útiles para la manipulación de la estructura de datos dentro del método, por lo que de ser atributos, aunque la implementación trabajaría de la misma manera, el enfoque sería inapropiado, esto es: sería un diseño inadecuado. El análisis y los detalles del ajuste de las referencias de las líneas 22-23 y 26-34 se dejan como ejercicio para el lector, a quien se insta amablemente a comprender completamente su funcionamiento antes de continuar.

   Por último, la clase de prueba para la cola de prioridad ascendente del Ejemplo ColaAscendente se muestra en el Ejemplo PruebaColaAscendente.

   Tómese el lector el tiempo que considere necesario para comparar el Ejemplo PruebaColaAscendente con el Ejemplo PruebaCola y advierta que son, esencialmente iguales.

   Note también que los objetos a almacenar en la cola de prioridad ascendente son objetos de la clase Integer (línea 6) por lo que, para que no haya ningún problema en la compilación, dicha clase deberá tener la implementación (implements) de la interfaz Comparable, y en consecuencia, la definición del método compareTo. En este sentido, se invita al lector para que realice dicha comprobación en el API de Java antes de compilar y ejecutar el Ejemplo PruebaColaAscendente.

   Con base en lo anterior, todos los objetos que se deseen almacenar en la cola de prioridad ascendente definida en el Ejemplo ColaAscendente, deberán implementar dicha interfaz, así como definir el comportamiento requerido (código) por el método compareTo.

   Por último, observe que a diferencia del Ejemplo PruebaCola, el Ejemplo PruebaColaAscendente inserta intencionalmente nueve números de manera desordenada, ya que la implementación de cola de prioridad propuesta (Ejemplo ColaAscendente) los mantiene ordenados dentro de la estructura de datos, mientras que la eliminación (líneas 18-26) se realiza de manera convencional. La salida del Ejemplo PruebaColaAscendente se muestra en la siguiente figura:

Salida del Ejemplo PruebaColaAscendente. 

 

Cola de prioridad descendente.

   La cola de prioridad descendente es análoga en lo general a la cola de prioridad ascendente.

   La cola de prioridad descendente es un tipo de estructura de datos en el que la inserción de los elementos se realiza también de la manera convencional, pero la eliminación se realiza en base al mayor de los elementos almacenados en ella. Al igual que para la cola de prioridad ascendente, para que ésto último sea posible, es necesario que los elementos que almacena la estructura de datos tengan una relación de orden, es decir, es preciso que incorporen algún mecanismo que les permita compararlos entre sí.

   La siguiente figura muestra la relación de clases en UML para una cola de prioridad descendente con la redefinición o sobre escritura (override) del método elimina. Una vez más, note cómo se ha instrumentado la redefinición de dicho método por medio del mecanismo de la herencia, y que las relaciones (compare con el diagrama de clases presentado para las colas de espera en la entrada Colas de espera (definición)) previamente existentes se conservan.

 

Diagrama de clases UML para una cola de prioridad descendente con la redefinición (override) del método elimina.

    Al igual que para la cola de prioridad ascendente, otro tipo de representación para la cola de prioridad descendente consiste en mantener ordenados los elementos de manera descendente durante la inserción y conservar la operación de eliminación de la forma convencional, tal y como lo sugiere la representación del diagrama de clases UML de la siguiente figura:

 

Diagrama de clases UML para una cola de prioridad descendente con la redefinición (override) del método inserta.

    Por último, recuerde que en una cola de prioridad descendente los elementos se recuperan (eliminan) en orden descendente respecto de la relación de orden que guardan entre sí. Los detalles de la implementación, se dejan como ejercicio para el lector.

Ejercicios selectos (colas).

(a) Estado inicial para la representación de Round robin.

(b) Estado siguiente para la representación de Round robin.

1. En el Ejemplo Cola el método inserta tiene la línea 24 como comentario ¿Qué sucede si sustituye la línea 25 por la línea 24? ¿Compilará? Si sí, ¿por qué?, y si no, ¿por qué? Si compila ¿Cuál será el resultado de la ejecución? Determine sus respuestas y después corrobore las mismas con la experimentación.
2. En el Ejemplo PruebaCola se creó una cola de espera utilizando un constructor sin argumentos. Modifique dicho ejemplo para asignar un nuevo nombre a la cola por medio del constructor correspondiente, asígnele el nombre de "Mi primera cola de espera", recompile, y pruebe su funcionamiento.
3. Modifique el Ejemplo PruebaCola para que permita leer n números enteros desde la entrada estándar y los almacene en la cola de espera.
4. Modifique el Ejemplo Cola para que:
1. Agregue el método peek a la implementación. Dicha operación funciona de la siguiente manera: echa un vistazo al elemento que se encuentra en el inicio de la cola de espera, lo regresa pero no lo elimina.
2. Incorpore un atributo privado numérico (n) que lleve el control del número de elementos insertados en la cola de espera. Al respecto no olvide:
1. Inicializar explícitamente dicho atributo a cero en el constructor.
2. Proporcionar únicamente el método de tipo get para el atributo n: public int obtenN( ).
5. Tomando como referencia el Ejemplo PruebaCola, modifíquelo para que la cola de espera del Ejemplo Cola almacene otro tipo de objetos además de los de la clase Integer. Pruebe con al menos las siguientes clases:
1. Double.
2. String.
3. Persona (del Ejemplo Persona).
4. Cientifico (del Ejemplo Cientifico).
6. Utilizando una cola de espera como la del Ejemplo Cola, implemente el algoritmo de Round robin. Round robin es un método para seleccionar a todos los elementos en un grupo de manera equitativa y en orden, se comienza con el primer elemento de la cola de espera y se procesa, se continua con el segundo y así de manera progresiva hasta llegar al último elemento de la cola, para empezar nuevamente desde el primer elemento. El principio general subyacente detrás del método, consiste en que cada elemento de la cola de espera consume una parte de un elemento compartido en cantidades iguales.
1. Considere la figura anterior en su inciso (a), la cual representa el estado inicial de una cola de espera de números enteros que representan las cantidades a considerar (quantum).
2. El estado siguiente (inciso (b)) consiste en atender (restarle uno al quantum) al nodo que se encuentra al inicio de la cola y volverlo a formar al final de la misma para atender de manera análoga a los siguientes nodos.
3. Tome en consideración que, una vez que el número llega a cero, el nodo correspondientes es eliminado. 
4. El proceso anteriormente descrito continúa hasta atender o despachar a todos los nodos formados en la cola. Para ello:
1. Genere un número aleatorio entre 10 y 50, el cual representará el número de nodos que contendrá la cola de espera.
2. Por cada nodo, genere nuevamente un número aleatorio entre 1 y 500, mismo que representará el quantum asignado a cada nodo.
5. No olvide construir también una clase de prueba para su implementación. La salida de su programa puede ser en la salida estándar o en un archivo de texto (consulte el API). Es importante que compruebe el adecuado funcionamiento de su implementación, ya que se reutilizará en otros ejercicios del blog.
7. Modifique el Ejemplo PruebaColaAscendente para que la cola de prioridad ascendente del Ejemplo ColaAscendente almacene otro tipo de objetos además de los de la clase Integer. Pruebe con al menos las siguientes clases:
1. Double.
2. String.
3. Persona (del Ejemplo Persona).
4. Cientifico (del Ejemplo Cientifico).
5. Tome en cuenta que las clases Double y String del API de Java implementan la interfaz Comparable, pero que las clases Persona y Cientifico no, por lo que como primer paso, deberá hacer que dichas clases implementen la interfaz Comparable y definan el método compareTo. Para ello:
1. Realice el ordenamiento en base al atributo que representa la edad de la persona para las instancias de la clase Persona (vea 7.6).
2. Realice el ordenamiento en función del atributo que representa la especialidad del científico para las instancias de la clase Cientifico (vea 7.7).
6. Como guía adicional para el lector, la clase PersonaComparable del Ejemplo PersonaComparable realiza la implementación de la interfaz Comparable. Observe cómo dicho ejemplo es esencialmente igual al Ejemplo Persona. Compare ambos ejemplos, estúdielos, y ponga especial atención en las líneas 5 y 57-63 del Ejemplo PersonaComparable, para que pueda resolver lo planteado en este ejercicio.
7. Respecto a la clase Cientifico, la solución es un poco más elaborada:
1. Si partimos de la siguiente base: public class Persona implements Comparable<Persona>{...}. Entonces la herencia debería ser: public class Cientifico extends Persona implements Comparable<Persona>{...} y no public class Cientifico extends Persona implements Comparable<Cientifico>{...} ya que de otra forma el compilador indicará que Comparable no puede ser heredada con diferentes argumentos (Cientifico y Persona).
   
2. El método compareTo de Cientifico debe hacer un cast (conversión de tipos): public int compareTo(Persona p){   Cientifico c = (Cientifico) p; // aquí va el código que compara con los criterios para Científico.}.
3. La cola ascedente deberá indicar que almacena objetos de la clase base Persona: ColaAscendente<Persona> cola = new ColaAscendente<Persona>( ); pero insertar instancias de Cientifico (por eso es necesario el cast).
4. En este tipo de problemas recuerde siempre usar la clase base como tipo base para los datos, aunque inserte objetos de clases derivadas. El proceso de eliminación es equivalente.
   
8. Con base en las consideraciones hechas en el blog respecto de la cola de prioridad ascendente y al diseño propuesto por el diagrama de clases UML alternativo (entrada Colas de prioridad), realice la implementación de la cola de prioridad ascendente sobrescribiendo ahora el método elimina. Pruebe su propuesta con las clases y las consideraciones hechas en el Ejercicio anterior para la interfaz Comparable.
9. Realice la implementación de una cola de prioridad descendente de manera análoga a la del Ejemplo ColaAscendente. Para lo anterior, tome en cuenta las consideraciones hechas en el blog y lo expuesto en el diseño representado por el diagrama de clases UML (entrada Colas de prioridad). No olvide definir también la clase de prueba para verificar y validar su propuesta; puede basarse en la del Ejemplo PruebaColaAscendente. Para sus pruebas, tome en cuenta al menos, las clases y consideraciones propuestas en el Ejercicio 7.
10. Con base en las consideraciones hechas en el blog respecto de la cola de prioridad descendente y al diseño propuesto por el diagrama de clases UML alternativo (entrada Colas de prioridad), realice la implementación de la cola de prioridad descendente. Pruebe su propuesta con las clases y las consideraciones hechas en el Ejercicio 7 para la interfaz Comparable.
11. Considere la abstracción de la estructura de datos compuesta mostrada en la figura que aparece al final de esta entrada. La estructura de datos mostrada está compuesta por una cola de espera y varias pilas, una por cada nodo formado en la cola. Note que cada nodo de la cola de espera conserva una referencia a objetos como él, y una referencia a objetos de tipo pila. Este ejercicio consiste en hacer una representación de una fila de supermercado, en donde cada nodo formado en la cola de espera, simula un carrito de supermercado con diferentes productos almacenados en él en forma de pila (en la vida real no necesariamente es así, pero para el caso del ejercicio propuesto basta con esa suposición). Cada nodo de la pila representa un producto, por lo que se requiere que la información que almacena la pila sean cadenas que representan la descripción del producto: leche, jamón, huevos, cacahuates, etc.
1. Escriba un programa que modele e implemente la estructura de datos planteada por el diagrama de la estructura de datos.
2. Sería sumamente conveniente y recomendable para el lector que, como parte de su diseño, realizara también el diagrama de clases UML de su propuesta de solución.

Abstracción de una estructura de datos compuesta.