Implementación de Herencia (Java).

   El Ejemplo Persona muestra la implementación en Java de la clase Persona mostrada en el diagrama de clases de la entrada POO (herencia). Todos los detalles de la clase Persona de dicho ejemplo ya han sido expuestos ahí, por lo que se recomienda encarecidamente al lector los revise y analice, y que los compare con lo descrito para diagrama UML correspondiente.

   Por otro lado, el Ejemplo Cientifico contiene la implementación de la clase Científico mostrada también en el diagrama de clases mencionado anteriormente. Observe que la herencia es implementada en Java a través del uso de la cláusula extends (línea 6), seguida de la clase de la que se hereda (Persona) en la definición de la clase Científico.

   Es importante que el lector note el uso de la cláusula super en los constructores (líneas 11 y 18). El uso en Java de dicha cláusula sólo puede hacerse en el contexto de constructores y sirve para delegarle al constructor correspondiente de la clase padre, los detalles de inicialización del objeto en cuestión que, para el caso de la clase Científico, corresponden a los constructores de dos y tres argumentos de la clase Persona respectivamente. Asegúrese de comprender también ésto antes de continuar.

   Al igual que antes, se deja como ejercicio de análisis para el lector tanto los detalles restantes de implementación de la clase Científico, como el asegurarse de comprender la relación del diagrama UML con el código del Ejemplo Científico.

   En este punto, es importante también que el lector ponga especial atención en los métodos mensaje del Ejemplo Persona (líneas 61-63), y del Ejemplo Científico (líneas 33-35), ya que serán fundamentales para comprender la sobre escritura (override) de métodos que se discute más adelante en la clase de prueba (Ejemplo PruebaHerencia).

   La clase de prueba para la herencia se presenta en el Ejemplo PruebaHerencia y se describe brevemente a continuación. La línea 10 define el objeto persona y genera una instancia de la clase Persona con características específicas; note que el constructor que está siendo utilizado es el definido en las líneas 24-28 del Ejemplo Persona.

   Observe cómo en las líneas 13, 15, 19 y 21 del Ejemplo PruebaHerencia se envían mensajes específicos al objeto persona para:

1. Obtener su nombre.
2. Cambiarle el nombre.
3. Volver a obtener su nombre.
4. Solicitarle comer.
5. Solicitarle un mensaje.

   La salida de lo anterior se ve expresada en las primeras cuatro líneas de la siguiente figura:

Salida del Ejemplo PruebaHerencia.

 

    Por otro lado, la línea 26 define y crea el objeto cientifico como una instancia de la clase Cientifico. Al igual que antes, note cómo el constructor utilizado es el definido en las líneas 17-20 del Ejemplo Cientifico.

   A su vez, las líneas 28 y 30 del Ejemplo PruebaHerencia realizan algo análogo a lo que se hizo con el objeto persona, es decir, envían mensajes al objeto cientifico para obtener y cambiar el nombre del científico.

   La línea 32 por su parte, cambia la especialidad del científico a través de un mensaje de tipo set.

   Finalmente, las líneas 34, 36, 38 y 40 envían mensajes específicos al objeto cientifico para:

1. Obtener su nombre.
2. Solicitarle comer.
3. Solicitarle un mensaje.
4. Solicitarle un mensaje especial.

   Note cómo para el mensaje mensaje las respuestas del objeto persona y el objeto cientifico difieren por completo, debido a que aunque el mensaje es el mismo, el objeto que los recibe responde de manera distinta a dicho mensaje; esto último fue lo que en su momento se definió como polimorfismo. En este ejemplo el polimorfismo está expresado en su forma de sobre escritura (override) de métodos.

Composición, Agregación y Asociación.

   Desde mi perspectiva, resulta no trivial el explicar la sutil diferencia que existe entre los conceptos de Composición, Agregación y Asociación. En mi experiencia, existe una tendencia muy común hacia utilizarlos de manera indistinta, sobre todo los dos primeros; por otro lado, el tratar de mostrar uno u otro tipo de relación con ejemplos aislados, en donde sólo me muestre la Composición pero no las otras dos y así con las otras combinaciones representa, al menos para mí, una tarea no muy sencilla.

   El siguiente diagrama de clases UML presenta los cuatro tipos de relaciones más comunes que se dan entre clases:

1. Herencia (entre las clases Persona y Científico, estudiada en la entrada Herencia / Generalización).
2. Composición (entre la clase Persona y las clases Pierna, Cabeza y Tórax entre otras tantas posibles).
3. Agregación (entre las clases Persona y Ropa).
4. Asociación (entre las clases Persona y Tarjeta de Crédito).

Diagrama de Clases UML para mostrar tres tipos de relaciones: Composición, Agregación y Asociación.

    Probablemente he abusado de la simplicidad para el ejemplo, pero he tratado de utilizar elementos conocidos y asequibles en lo general para evitar lo rebuscado o complejo que puede llegar a ser el modelado de un sistema más "real", en el que con toda seguridad aparecerán, de manera natural, este tipo de relaciones. Ahora bien, la generación de esta clase de diagramas se obtiene como resultado del análisis, la experiencia, y la previa comprensión de las diferencias (muchas veces sutiles e incluso subjetivas) que pretendo clarificar.

   La principal diferencia entre las relaciones radica fundamentalmente en dos cosas:

1. En el tiempo de vida de los objetos que se deriven de las clases.
2. El grado de dependencia o cohesión entre los objetos.

Herencia.
   Quizá la relación más simple y más común de las mostradas en el diagrama de clases anterior, sea la de la herencia: un Científico es una Persona, un Científico posee todas las características de una Persona (modeladas por sus atributos) más algunas características particulares a un Científico. Lo mismo sucede con sus responsabilidades y comportamiento. Para ampliar un poco más los detalles, puede el lector revisar la entrada Herencia / Generalización.

Composición.
   La Composición es un tipo de relación de alto grado de dependencia entre la clase contenedora (Persona) y las clases que la componen (Cabeza, Tórax, Pierna, etc.), es decir, cuando se crea una instancia de la clase contenedora, deben crearse, como parte de su conformación, instancias de los objetos que la componen, ya que no tendría sentido, desde el punto de vista de la instancia de Persona, conformar una persona sin cabeza o sin un tórax; por otro lado, durante toda la vida del objeto de la clase Persona debe existir el objeto de la clase Cabeza por la misma razón que antes. En este mismo sentido, tampoco tendría congruencia el tener una instancia de la clase Cabeza que nunca haya estado relacionada con una Persona.

   Algún lector inconforme podría argumentar que sí es posible que un objeto de la clase Persona deje de contener a uno de la clase Pierna por ejemplo, sin afectar la existencia de primero, y en efecto: es posible. Bastaría entonces con analizar si conviene más que la clase Pierna se modele mejor como Agregación, pero finalmente esto es sólo un ejemplo y la idea principal considero que ha sido plasmada, lo último sería más cuestión de análisis y de la conveniencia dada para un sistema determinado tal y como sucede en la vida real.

   Mi perspectiva y determinación personal sería: que se quedara como Composición.

Agregación.
   La Agregación, por otro lado, es un tipo de relación con un bajo grado de dependencia. Así por ejemplo, una instancia de la clase Persona, puede tener o no, durante su tiempo de vida (pero no es preciso que lo tenga desde su creación), un atributo de la clase Ropa sin que ello afecte su propia existencia; al mismo tiempo que un objeto de la clase Ropa podría existir independientemente de si es agregado a una Persona o a un Maniquí (clase que no aparece en el diagrama), por ejemplo.

   En este tipo de relación, la existencia de los objetos involucrados es independiente, lo mismo que su tiempo de vida: un objeto de la clase Ropa podría seguir existiendo más allá del tiempo de vida del de una Persona y viceversa, sin que ninguno de los dos se vea afectado.

Asociación.
   Una Asociación es aún menos dependiente en relación y tiempo. Espero que el lector coincida conmigo en que si bien la ropa no es imprescindible para la existencia de una persona, sí es necesaria; mientras que una tarjeta de crédito podría ser útil, en el mejor de los casos necesaria, pero en definitiva prescindible, es decir, una Persona podría pasar toda su vida sin tener la necesidad de ninguna Tarjeta de Crédito, mientras que otras podría tener muchas de ellas.

   Finalmente la relación de Asociación presentada en el diagrama, muestra que una Tarjeta de Crédito está asociada a una Persona, y que una Persona tiene ninguna (0) o varias (*) Tarjetas de Crédito.

    Finalmente, se recomienda revisar también la información expuesta en la entrada Consideraciones adicionales, en donde se presentan y contrastan ejemplos relacionados con lo aquí expuesto.

ABB (eliminacion).

   La eliminación de un elemento de un árbol binario de búsqueda consiste básicamente en, dado un elemento a eliminar:

• Identificar si dicho elemento se encuentra en el ABB (identificación de duplicados), si no existe, se podría regresar un valor que indique dicha situación y dejar el ABB sin cambios.
• Si el elemento existe en el ABB, entonces existen tres posibilidades:
1. Si el elemento está almacenado en un nodo hoja, la eliminación es directa.
2. Si el elemento está almacenado en un nodo con un solo hijo, el hijo sustituye al padre y se elimina el nodo correspondiente.
3. Si el elemento está almacenado en un nodo con dos hijos, la regla que se adoptará será la de sustituirlo por el hijo más a la derecha del subárbol izquierdo (el mayor de los menores). También existe la regla simétrica del hijo más a la izquierda del subárbol derecho (el menor de los mayores), pero no se utilizará en el blog, por convención, se utilizará la primera.

Observe también que con el proceso de eliminación descrito con anterioridad:

1. Se conserva la relación de orden que debe mantener un ABB.
2. Se podría incurrir en un intento de eliminación de un ABB vacío lo cual, desde el punto de vista de la implementación generaría una excepción, por lo que sería conveniente tener una forma de verificar dicha situación.

Diagrama de clases UML para un ABB con eliminación (Java).

 

 

Diagrama de clases UML para un ABB con eliminación (C++).

 

    En función de lo anterior, los diagramas de clases UML de las figuras anteriores complementan al presentado en la entrada ABB (representación y diseño). Observe que se han realizado las siguientes modificaciones en la clase ABB:

1. La incorporación de un atributo privado numérico (n) con la finalidad de llevar el control del número de elementos insertados en el ABB. Respecto a la implementación de éste, se debe considerar:
1. Inicializar explícitamente dicho atributo a cero en el constructor.
2. Proporcionar únicamente el método de tipo get para dicho atributo: obtenN( ) (obten_n( )).
2. La adición del método elimina, el cual realiza la eliminación de elemento si éste existe en el ABB devolviendo true como caso de éxito; en caso contrario, el método regresa false. Respecto a la implementación de este método, se debe considerar:
1. Seguir las reglas de eliminación descritas con anterioridad.
2. Lanzar la excepción ExcepcionEDVacia (excepcion_ED_vacia) ante un intento de eliminación de un ABB vacío, tal y como lo describe la relación que se muestra en los diagramas de clases.
3. La incorporación del método estaVacio (esta_vacio( )), el cual regresa true si el ABB está vacío y false en caso contrario.

   La implementación de las clases descritas en el diagrama UML correspondiente al lenguaje que utilice como medio, así como su correspondiente prueba, se dejan como ejercicio para el lector.

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.

ABB (representación y diseño).

   La representación de un árbol binario como la que se mostró en la entrada Árboles binarios (definición), es en realidad un árbol binario de búsqueda (ABB). La siguiente figura es también una representación (abstracción) de un ABB en un diagrama del estilo de los que se han utilizado a lo largo del blog. Dicho diagrama muestra elementos auxiliares (referencias) que serán de utilidad para trabajar con los distintos nodos del ABB, tal y como se detallará en la sección de Ejercicios para árboles binarios.

Representación de un ABB.

 

    Para complementar dicha abstracción, el diagrama de clases UML de las siguientes figuras muestran otro tipo de representación (que en sí misma es también una abstracción) para un ABB pero desde el punto de vista del diseño de clases:

Diagrama de clases UML para un ABB (Java).

 

Diagrama de clases UML para un ABB (C++).

 

    Observe cómo ha cambiado por completo la representación del nodo utilizado para un árbol binario de búsqueda (NodoABB) en comparación con el nodo que se había estado utilizando (NodoG) para las anteriores estructuras de datos lineales presentadas en el blog (consulte la sección Contenido temático para mayor información al respecto).

   La clase NodoABB define los atributos correspondientes para los subárboles izquierdo y derecho (representados por los atributos nodoIzquierdo y nodoDerecho respectivamente), y el dato a almacenar (dato). Adicionalmente, la clase define los servicios o comportamiento que deberá implementar la clase, los cuales corresponden a los métodos de tipo set y get; en este sentido, es de resaltar que éstos coinciden con las operaciones primitivas definidas para un árbol binario (consulte la sección Árboles binarios (operaciones primitivas)).

   Por otro lado, la clase ABB describe la abstracción correspondiente para la implementación del árbol binario de búsqueda y establece los servicios o el comportamiento que se espera en función de las operaciones primitivas definidas para un ABB (consulte la sección Operaciones primitivas del tema Árbol binario de búsqueda (ABB)).

   Tanto la definición en un diagrama de clases UML como la implementación correspondiente de los recorridos inversos, se dejan como ejercicios para el lector.

Listas doblemente enlazadas.

   Aunque una lista enlazada circular tiene ventajas sobre una lista simplemente enlazada (vea la entrada Listas circulares), también tiene algunas desventajas:

• No es posible recorrer la lista enlazada circular hacia atrás (o hacia la izquierda); es decir, sólo puede recorrerse en un sentido.
• Dada una referencia a un nodo determinado de la lista enlazada circular, no es posible eliminar dicho nodo utilizando únicamente dicha referencia (¿Por qué?).

   En este sentido, una estructura de datos conveniente para subsanar dichas desventajas es precisamente, la lista doblemente enlazada.

Definición, primitivas y representación.

   Una lista doblemente enlazada es una colección lineal de nodos auto referidos en donde cada nodo tiene dos referencias:

1. Una referencia al sucesor del nodo actual (siguiente).
2. Una referencia al antecesor del nodo actual (anterior).

   La representación de una lista doblemente enlazada se muestra en la figura (a). Observe cómo al igual que en una lista enlazada, una lista doblemente enlazada puede ser también doblemente enlazada circular (figura (b)). Esta última, sigue también las mismas consideraciones que se hicieron en su momento para una lista enlazada circular.

(a) Abstracción de una lista doblemente enlazada.

(b) Abstracción de una lista doblemente enlazada circular.

   Adicionalmente, las operaciones primitivas para una lista doblemente enlazada son exactamente las mismas que para una lista simplemente enlazada, por lo que no se repetirán aquí.

   Por otro lado, los diagramas de clases UML para los lenguajes Java y C++ de una lista doblemente enlazada se presentan a continuación. Los diagramas complementan la definición de la estructura de datos a través de su correspondiente diseño de clases:

Diagrama de clases UML para una lista doblemente enlazada (Java).

 

Diagrama de clases UML para una lista doblemente enlazada (C++).

 

    Por ultimo, note que dichos diagramas de clases son sustancialmente distintos de los que en general se han utilizado hasta ahora para el diseño de las anteriores estructuras de datos y que, exceptuando la clases ExcepcionEDVacia (excepcion_ED_vacia), tanto las clases ListaDoble (lista_doble) como las clases NodoDobleG (Nodo_doble) han sufrido cambios significativos. Consulte la sección de ejercicios correspondiente para obtener más detalles al respecto.

Herencia vs. composición (listas).

   Uno de los aspectos más importantes de la programación orientada a objetos es la conveniencia de la reutilización de código por medio de la abstracción. En este sentido, dos de los esquemas más comunes al respecto son: la herencia y la composición.

   Esta entrada muestra, por medio de un ejemplo ya conocido y presentado previamente al lector, la implementación de una pila utilizando una lista enlazada. Dicha implementación se realiza empleando los dos esquemas mencionados con anterioridad. Así mismo, se analizan las ventajas y desventajas de cada uno de ellos.

   Implementación de una pila utilizando herencia.

   La implementación de una pila por medio de una lista con un enfoque basado en la herencia es en realidad bastante simple. Para muestra, basta con ver el código del código del Ejemplo PilaH.

   Observe que la clase del Ejemplo PilaH no define atributos, y que únicamente define dos constructores y los métodos push y pop; lo cual también ha sido representado en el diagrama de clases UML de la siguiente figura.

Diagrama de clases UML para la implementación de una pila utilizando herencia y una lista enlazada.

 

    Insto nueva y amablemente al lector a que compare, contraste, y analice con detenimiento antes de continuar, a la figura anterior con el Ejemplo PilaH.

   Note que los métodos push (líneas 14-16) y pop (líneas 18-20) del Ejemplo PilaH no hacen otra cosa más que encapsular el comportamiento de los métodos insertaAlInicio y eliminaDelInicio respectivamente, los cuales son servicios o comportamiento definidos en la clase Lista del Ejemplo Lista. Note también que es posible acceder a dichos métodos debido a que la clase PilaH hereda de la clase Lista (línea 5).

   Observe que como parte del mecanismo de la herencia, tampoco es necesario definir el comportamiento de los métodos estaVacia e imprime dentro de la clase PilaH, ya que se encuentran definidos en la clase Lista.

   El primero de dichos comportamientos forma parte de la definición de las primitivas de la estructura de datos pila, mientras que el segundo es utilizado en la clase PruebaPilaH del Ejemplo PruebaPilaH (líneas 11 y 20), la cual es la clase de prueba del Ejemplo en cuestión.

La salida del Ejemplo PruebaPilaH se muestra en la siguiente figura:

Salida del Ejemplo PruebaPilaH.

 

    Consideraciones.

   Al menos en apariencia, el mecanismo de la herencia resulta sumamente conveniente con base en lo expuesto con anterioridad; sin embargo, presenta algunos inconvenientes potenciales que vale la pena considerar.

   Las instancias de la clase PilaH, al heredar las características y el comportamiento inherentes a una lista enlazada, pueden hacer uso de los métodos de inserción y de eliminación correspondientes a ésta, por lo que desde esta perspectiva, un objeto de dicha clase podría permitir inserciones y eliminaciones, no únicamente del tope de la pila (representado por inicio), sino también de la base de la pila ("representada" por fin) a la que se supone, por definición de pila, no se debe tener acceso.

   Tome en consideración que todavía se podría transgredir más la definición de una pila, ya que potencialmente es posible también insertar en, o eliminar de cualquier parte de la estructura de datos con las modificaciones correspondientes (vea el Ejercicio 2.2 de los Ejercicios selectos), lo cual queda completamente fuera tanto de la definición que se hizo de la pila, como de las operaciones primitivas que le son inherentes.

Implementación de una pila utilizando composición.

   La implementación de una pila utilizando el enfoque de composición, se basa en la idea de que una lista enlazada contiene ya definidas las operaciones que necesita una pila, pero que también, como se discutió con anterioridad, contiene otras operaciones que no deberían ser utilizadas por la misma.

   En función de lo anterior y de manera conveniente, lo que puede hacerse es encapsular las operaciones de la lista enlazada dentro de las de la pila con la finalidad de proporcionar una interfaz o un conjunto de servicios ad hoc con la definición de la estructura de datos en cuestión: la pila.

Diagrama de clases UML para la implementación de una pila utilizando composición y una lista enlazada.

 

    La figura anterior muestra el diseño en diagrama de clases UML la definición de una pila que utiliza o contiene (has-a) una lista enlazada para su implementación. Observe y compare con detenimiento dicho diagrama con el respectivo diagrama UML para la implementación con herencia, y note que el cambio principal está en la clase PilaC y en la relación entre ésta y la clase Lista.

   Ahora bien, la definición de la clase PilaC se muestra en el Ejemplo PilaC. Insto una vez más al lector a que ponga atención en dos aspectos:

1. La relación entre el diagrama de clases de la figura anterior y el Ejemplo PilaC.
2. Los métodos push (líneas 16-18), pop (líneas 20-22) e imprime (líneas 24-26) no hacen otra cosa más que encapsular de manera conveniente, los mensajes enviados al objeto tope (línea 6), mismos que son llevados a cabo por los métodos correspondientes definidos en la clase Lista.

   Con base en lo anterior, los objetos instanciados de la clase PilaC sólo podrán acceder a los servicios definidos explícitamente en dicha clase y a ningún otro más independientemente de los métodos que posea la clase Lista, lo cuál hace que, desde el punto de vista de la abstracción y la representación de la estructura de datos, el enfoque de la composición sea mucho más conveniente, aunque un poco más laborioso, que el de la herencia. Por otro lado, para implementar una pila utilizando una lista enlazada la cantidad nueva de código se reduce significativamente; sin embargo, si bien es cierto que uno de los enfoques del paradigma orientado a objetos se basa en la reutilización del código, es importante que el lector se haga consciente de estos dos aspectos, ya que cada uno de ellos tiene sus ventajas y desventajas, y la decisión final de implementación debería tomarse con pleno conocimiento de causa, ya que no siempre es mejor tomar el camino más fácil (herencia).

   La clase de prueba del Ejemplo PilaC se muestra en el Ejemplo PruebaPilaC y sigue el mismo mecanismo de inserción que el los ejemplos de prueba anteriores. Finalmente, compruebe que la salida del Ejemplo PruebaPilaC coincide exactamente con la salida correspondiente del Ejemplo PruebaPilaH, y que desde el punto de vista de la ejecución, no podría saberse cuál fue el enfoque de diseño elegido.

Listas (implementación).

   La implementación de una lista enlazada se muestra en el Ejemplo Lista. Note que con base en lo descrito en el diagrama de clases UML de la siguiente figura y a lo definido en el código fuente de dicho ejemplo, se hace uso de las clases NodoG y ExcepcionEDVacia, mismas que ya han sido explicadas y analizadas en entradas anteriores por lo que ya no se presentan ni se describen aquí (si el lector desea una descripción de dichas clases, refiérase a la entrada Pilas (implementación)).

Diagrama de clases UML para una lista enlazada.

 

    Adicionalmente a lo anterior, el Ejemplo Lista muestra la definición de los métodos estaVacia e imprime, los cuales también han sido presentados y descritos en ejemplos anteriores; de hecho, se han reutilizado aquí con toda la intención, ya que el comportamiento representado por ellos cumple con los requerimientos necesarios para una lista enlazada.

   Con base en lo anterior, únicamente se describirán los siguientes métodos:

• insertaAlInicio (líneas 18-23) como su nombre lo indica, el método inserta elementos en la parte referida por inicio.

   Si la estructura de datos está vacía (línea 19), se crea el nodo (objeto) con el elemento correspondiente, el cual será referido tanto por inicio como por fin (línea 20). En caso contrario, se inserta el elemento siguiendo la misma idea que se utilizó para la pila (línea 22).

• insertaAlFinal (líneas 25-32) como su nombre lo indica, el método inserta elementos en la parte referida por fin.

   Si la estructura de datos está vacía (línea 26), se crea el nodo (objeto) con el elemento correspondiente, el cual será referido tanto por inicio como por fin (línea 27; observe que hasta aquí se hace exactamente lo mismo que para el método anterior: insertaAlInicio). En caso contrario, se inserta el elemento siguiendo la misma idea que se utilizó para la cola de espera (líneas 29-30).

• eliminaDelInicio (líneas 34-47) como su nombre lo indica, este método elimina elementos en la parte referida por inicio.

   Si la estructura de datos está vacía (línea 35), se lanza la excepción ExcepcionEDVacia (línea 36). En caso contrario, se procede a la eliminación del elemento de manera análoga a como se hizo para la cola de espera (líneas 38-46).

• eliminaDelFinal (líneas 49-68) como su nombre lo indica, elimina elementos en la parte referida por fin.

   Si la estructura de datos está vacía (línea 50), se lanza la excepción ExcepcionEDVacia (línea 51). En caso contrario, se procede a la eliminación del elemento correspondiente, para ello:

1. Si sólo existe un elemento (línea 56), se actualizan las referencias (línea 57). En caso contrario (línea 58):
2. Se realiza un recorrido (líneas 59-61) por la estructura de datos desde el inicio (línea 59), para determinar el elemento anterior al referido por fin (¿Por qué?).
3. Se actualizan las referencias correspondientes (líneas 63-64).

   La clase de prueba para el Ejemplo Lista se muestra en el Ejemplo PruebaLista. Note que se insertan diez números enteros, y que para los números pares se utiliza el método insertaAlInicio, mientras que para los números impares se utiliza el método insertaAlFinal. Observe también cómo para la eliminación ocurre lo correspondiente.

   Finalmente, la siguiente figura muestra la salida del Ejemplo PruebaLista.

Salida del Ejemplo PruebaLista.

Listas (definición).

Definición.

   Una lista es, en general, una colección lineal de elementos; mientras que una lista enlazada es, en el contexto que nos compete, una colección lineal de objetos (nodos) auto referidos.

   Se tiene acceso a una lista enlazada por medio de una referencia al primer nodo de la lista. Aunque resulta más conveniente, por las características inherentes a la implementación de la estructura de datos, que existan dos referencias a la misma: una que refiera el inicio de la lista, y otra que refiera el fin de la lista. El acceso a los nodos intermedios subsecuentes, se realiza a través del enlace o referencia que contiene cada uno de ellos.

   Una lista enlazada es más conveniente que un arreglo estático por ejemplo, cuando no es posible determinar con anticipación el número de elementos a almacenar en la estructura de datos.

   Las listas enlazadas son dinámicas, por lo que se puede aumentar o disminuir a discreción el número de elementos de la lista. Un aspecto importante a considerar respecto a las listas enlazadas es que pueden, simplemente por conveniencia, mantenerse en orden (tome en cuenta el lector que, aunque esto puede resultar sumamente conveniente, no es una característica inherente a la estructura de datos) insertando cada nuevo elemento en el punto apropiado dentro de la lista enlazada.

   Normalmente los nodos de las listas enlazadas no están almacenados en forma contigua en la memoria; sin embargo, lógicamente los nodos aparecen como contiguos. Esto obedece a su representación física y lógica respectivamente.

   Operaciones primitivas.

   Se definen cinco operaciones primitivas sobre una lista enlazada (entre paréntesis aparece la definición para C++):

1. La operación insertaAlInicio (inserta_al_inicio) agrega un elemento al inicio de la lista enlazada.
2. La operación insertaAlFinal (inserta_al_final) agrega un elemento al final de la lista enlazada.
3. La operación eliminaDelInicio (elimina_del_inicio) elimina un elemento del inicio de la lista enlazada.
4. La operación eliminaDelFinal (elimina_del_final) elimina un elemento del final de la lista enlazada.
5. La operación estaVacia (esta_vacia) regresa verdadero o falso, dependiendo de si la lista enlazada contiene o no elementos respectivamente.

   Tome en cuenta que los elementos de una lista enlazada podrían ser insertados en cualquier parte, y que en función de ellos, podrían ser definidas más operaciones sobre una lista enlazada, por lo que el mecanismo de inserción estará en función directa de las necesidades específicas para la implementación de la estructura de datos.

  En este sentido, si se desea mantener una lista enlazada ordenada por ejemplo, se deberá ir recorriendo la lista enlazada de manera secuencial, hasta encontrar el lugar apropiado para la inserción de cada uno de los elementos que la conformarán.

   Por otro lado, la eliminación de un elemento particular, podría consistir en primer lugar, en la localización de dicho elemento dentro de la lista enlazada. Si existe, se procede a su correspondiente eliminación; en caso contrario, se debería indicar que el elemento que se está intentando eliminar, no existe dentro de la estructura de datos.

   Representación.

   Como se mencionó en la sección anterior, el acceso a una lista enlazada se realiza por al menos una referencia al primer nodo de dicha lista enlazada. Aunque por otro lado, resulta más conveniente, por las características inherentes a la implementación de la estructura de datos, que existan dos referencias hacia la misma: una que refiera el inicio de la lista enlazada, y otra que refiera el fin de la lista enlazada.

   El acceso a los nodos intermedios subsecuentes se realiza a través del enlace o referencia que contiene cada uno de ellos. Por regla convencional, para marcar el fin de la lista enlazada, el enlace al siguiente nodo en el último nodo de la lista enlazada se establece a null (nullptr).

   La representación mostrada en la siguiente figura es una abstracción de la implementación que se realizará en una entrada posterior. También coincide con la representación lógica de una lista enlazada.

Abstracción de una lista enlazada como una secuencia de nodos.

 

    Observe cómo la figura anterior luce muy similar a la figura correspondiente a las colas de espera, ya que también hace uso de dos referencias: inicio y fin, mismas que denotan respectivamente el primero y el último de los elementos almacenados en la lista enlazada. Note también que, para el caso de un solo elemento, dichas referencias harán referencia, valga la redundancia, al mismo nodo.

   Por otro lado, los diagramas de clases UML que se presentan a continuación, muestran el diseño de clases de la lista enlazada que se desea implementar. Dicho diseño complementa, en conjunción con la definición hecha con anterioridad, el concepto de lista enlazada.

Diagrama de clases UML para la lista enlazada (Java).

  

Diagrama de clases UML para la lista enlazada (C++).

 

    Los diagramas de clases UML de las figuras anteriores muestran también la relación que existe entre las clases más importantes que se involucrarán durante la implementación de la lista enlazada. Tome el lector el tiempo que considere necesario para revisar, analizar y comprender dichos diagramas de clases antes de avanzar a la implementación correspondiente.

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.

Colas (implementación).

   El nodo genérico definido en la clase del Ejemplo NodoG ya ha sido presentado con anterioridad en la sección Pila genérica de la entrada Pilas (implementación) y no se explicará nuevamente. Dicho ejemplo sólo se ha incluido aquí como referencia inmediata al lector para facilitarle la relación y la completa comprensión de la implementación de la cola de espera.

   De manera análoga, el Ejemplo ExcepcionEDVacia muestra la excepción utilizada por la implementación de la cola. Dicha clase también ha sido explicada con anterioridad.

   Se invita al lector a revisar estos dos ejemplos iniciales como preámbulo a la implementación de la cola de espera. En caso de que surgiera alguna duda, consulte las entradas correspondientes a los ejemplos mencionados en los párrafos anteriores.

   La implementación de la cola de espera se muestra en el Ejemplo Cola. Antes de comenzar con la explicación de los métodos que implementan las operaciones primitivas, insto amablemente al lector a que compare el diagrama de clases de la siguiente figura con el código del Ejemplo Cola, esto con la intención de que identifique la relación que existe entre el diseño y la implementación representados por el diagrama de clases y el código respectivamente.

Diagrama de clases UML para la cola de espera del Ejemplo Cola.

    La identificación y comprensión de atributos y constructores deberían resultar totalmente claros para el lector, excepto quizá por el modificador de nivel de acceso protected, el cual hace que el atributo correspondiente sea accesible únicamente por las clases del mismo paquete, o por subclases de la clase que lo define. Dicho lo anterior, la explicación del Ejemplo Cola iniciará con los siguientes métodos (ambos métodos fueron descritos en la implementación de la pila genérica de la entrada Pilas (implementación); de hecho son idénticos, excepto por una pequeña diferencia que sería muy bueno que el lector identificara):

•  estaVacia (líneas 47-49) realiza una verificación bastante simple: si inicio es igual a null, regresa verdadero (la cola está vacía); si no, regresa falso (existe al menos un elemento).
• imprime (líneas 52-55) si la estructura de datos está vacía (línea 53) se reporta (línea 54); en caso contrario, se realiza un recorrido por todos los nodos de la estructura para imprimir su contenido (líneas 57-62).

   Los dos métodos restantes corresponden a las dos operaciones primitivas que fueron definidas para una cola de espera, y se describen a continuación:

1. El método inserta verifica en la línea 21 si la cola está vacía; si lo está, se crea un nuevo nodo que contiene a elemento y se hace que tanto inicio como fin hagan referencia a dicho nodo (objeto).
2. Si la cola no está vacía (línea 23), se crea un nuevo nodo y se agrega al final de la cola (línea 25); adicionalmente, se establece que el último elemento es referido por fin (línea 26).
3. El método elimina verifica (línea 32) si la cola está vacía; si lo está crea y lanza la excepción ExcepcionEDVacia (línea 33); en caso contrario, recupera el dato almacenado (línea 35) y actualiza las referencias correspondientes para inicio y fin (líneas 38-41), para finalmente, regresar el dato recuperado referido por elemento (línea 43).

   La clase de prueba para la cola de espera del Ejemplo Cola se muestra en el Ejemplo PruebaCola. La línea 6 define la clase (Integer) de los elementos a insertar en la cola de espera, mientras que las líneas 9-12 realizan la inserción de los números del cero al nueve. Note que por cada inserción, se imprime todo el contenido de la cola.

   Por otro lado, las líneas 15-24 realizan la eliminación de los elementos de la cola. Dicho fragmento de código intenta eliminar once elementos en las líneas 17-18 (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 elimina 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.

   La salida del Ejemplo PruebaCola se muestra en la siguiente figura. Asegúrese de comprender, antes de continuar, por qué se generan cada uno de los elementos (renglones) que componen dicha salida.

Salida del Ejemplo PruebaCola.

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.