Ejercicios selectos (excepciones).

1. Con base en lo descrito en la entrada Excepciones, considere el Ejemplo DivisionConManejoExepcion2 y compárese en el ejemplo de dicha entrada (Ejemplo DivisionConManejoExepcion). La equivalencia lógica y funcional es la misma, note que la diferencia radica en la cláusula finally del ejemplo en cuestión (líneas 41-44). Asegúrese de comprender las diferencias así como su equivalencia.
2. Escriba una clase de prueba que permita probar el funcionamiento de la clase ListOfNumbers.
   
3. En las versiones de Java 7 y posteriores, un bloque catch puede manejar más de un tipo de excepción. Dicha característica pretende reducir la duplicidad de código y tener demasiada extensión en las cláusulas de tipo catch. En este sentido, considere el Ejemplo ListOfNumbers2 que es la versión actualizada del Ejemplo ListOfNumbers visto en la entrada Atrapando y manejando excepciones. Asegúrese de entender su equivalencia antes de continuar.
4. Tomando en consideración lo descrito en la entrada Especificación de excepciones lanzadas por un método, modifique el Ejemplo ListOfNumbers2 para que el método writeList( ) no maneje la excepción, sino que indique que la puede lanzar. Así mismo, deberá modificar de manera apropiada lo realizado en el Ejercicio 2 (ahora la clase de prueba tendrá que hacer el manejo correspondiente de la excepción) para que el programa siga funcionando.
   
5. En la entrada Excepciones se trabajó con el Ejemplo DivisionConManejoExepcion, y en el Ejercicio 1 con una versión alternativa (Ejemplo DivisionConManejoExepcion2). Considere ahora el Ejemplo DivisionConManejoExcepcion3 y asegúrese de comprender las diferencias así como las equivalencias con los ejemplos citados. Note que la única diferencia de este último con respecto de la versión anterior es la cláusula throws ArithmeticException (línea 17). En la entrada Especificación de excepciones lanzadas por un método puede consultar los detalles de dicha cláusula.
   
6. Considere una ecuación cuadrática de la forma ax^2 + bx + c. Escriba un programa que permita leer los coeficientes reales de una ecuación de este tipo y obtenga las raíces reales de la misma. Para ello:
• Si el coeficiente a es cero, deberá generar tanto la excepción como el manejo correspondiente de la misma; es decir, su programa deberá reportar el problema (no es una ecuación cuadrática) y continuar.
• Detectar si los coeficientes no son números.
• Si las raíces de la ecuación no son números reales, deberá también reportar dicha situación como una excepción y realizar el manejo correspondiente (preguntar al usuario si desea continuar o no).
  
7. Considere el Ejemplo Excepciones el cual contiene comentarios respecto a secciones de código que serían inalcanzables. Compruebe que así sea, para ello, puede agregar una sentencia simple en donde sea pertinente como por ejemplo System.out.println("¿Qué pasará?"); y analice ¿qué sucede?, ¿compila?, ¿se ejecuta?
   
8. Para el Ejemplo Excepciones3, ¿que piensa que ocurrirá si se elimina alguna de las cláusulas throws Exception (líneas 10, 16, 22 y 28)? Determine primero su respuesta, y posteriormente compruébese con la experimentación.
9. Con base en lo expuesto en el ejercicio anterior, ¿qué piensa que sucederá si en lugar de una excepción verificada (checked exception) se utiliza una excepción no verificada (uncheked/runtime exception)? Determine y realice el experimento correspondiente.
   
10. Con base en lo expuesto en Lanzado y encadenamiento y en los dos ejercicios anteriores, construya un programa que, como en el Ejemplo Excepciones3 se relance una excepción, con la diferencia de que ahora, en cada método, se deberá atrapar la excepción anterior y encadenarla con una nueva creada en ese método, para relanzar esta nueva excepción y que a su vez sea atrapada y encadenada con una nueva en el método siguiente. Revise nuevamente el Ejemplo Excepciones2 para ver cómo crear un excepción encadenada (compuesta).
11. A partir de la versión 7 de Java, se incorporó la sentencia try-con-recursos (try-with-resources), la cual permite declarar uno o más recursos dentro de la cláusula. Dichos recursos son objetos que deben ser cerrados cuando el programa que los utiliza ha terminado con ellos. El Ejemplo ListOfNumbers3 es una muestra de cómo funciona dicha cláusula, pero se invita al lector a documentarse más al respecto.
    

 

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.

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

Implementación del ADT racional.

   El Ejemplo Racional muestra una posible implementación de ADT racional definido en la entrada Tipos de Datos Abstractos (ADT).

   Las líneas 7 y 8 definen los atributos de un número racional (p / q). Los detalles relacionados con los métodos de tipo set y get (líneas 25-41), ya han sido comentados en la sección Métodos y atributos de la entrada POO (mensajes y métodos) y no se repetirán aquí.

   Por otro lado, los constructores definidos (líneas 10-23) requieren de una ampliación en su explicación, ya que difieren un poco de lo hasta ahora comentado para los constructores.

   El constructor principal o base es el definido en las líneas 18-23. Observe que dicho constructor recibe dos argumentos, mismos que representan el numerador (n) y el denominador (d) del número racional que se desea inicializar. En la línea 19, el constructor realiza una verificación del denominador (cláusula de condición), de tal forma que si éste es cero, se crea (new) y lanza (throw) una excepción (consulte la sección de Excepciones de la entrada Ejemplos selectos de transición) para indicar el error a través de la clase ArithmeticException. Note también que el mismo comportamiento es considerado en las líneas 30 y 31 para el método estableceDenominador. Una posible salida del programa al presentarse la situación anteriormente planteada, se muestra en la siguiente figura:

Una salida de la excepción generada en el Ejemplo PruebaRacional al intentar crear un número racional cuyo denominador sea cero.

 

   Los constructores de las líneas 10-12 y 14-16 se apoyan del constructor base de las líneas 18-23 para realizar la inicialización del objeto a través del uso de la cláusula this. La cláusula this es una referencia que tienen todos los objetos hacia sí mismos, por lo que en el contexto de los constructores invoca al constructor sobre cargado que corresponda con el tipo y número de argumentos que envía, que para el caso de las líneas 11 y 15 corresponden con el constructor base de las líneas 18-23.

   La implementación de las operaciones de suma y producto aparecen en las líneas 43-50 y 52-59 respectivamente (la implementación de las operaciones resta y división se dejan como ejercicio para el lector). Observe que en las líneas 46 y 47 (55 y 56) se accede directamente a los atributos p y q a través del operador punto (.), es decir, sin hacer uso de los métodos de acceso set y get; ésto es así debido a que el objeto s (m) es de la misma clase que define al método suma (multiplica), por lo que el acceso es concedido sin ningún tipo de inconveniente (recuerde lo planteado en el Ejercicio 2 de la entrada Ejercicios selectos (POO) y analice la diferencia).

   Por otro lado, note también que para el objeto (this) que recibe el mensaje suma (multiplica), los atributos p y q de las líneas 46 y 47 (55 y 56) son accedidos sin ningún tipo de operador ni mensaje, es decir, son accedidos por contexto, ya que el objeto que recibe el mensaje conoce cuáles son sus propios atributos y métodos por lo que dentro del método la expresión:

p * r.obtenDenominador( )

es equivalente a la expresión:

this.p * r.obtenDenominador( )

   Por último en lo que respecta a los método suma y multiplica, es importante resaltar que ambos métodos utilizan un objeto local al método (s y m respectivamente) para almacenar el resultado que generan y poder regresarlo como valor de retorno del método, por lo que es posible deducir que si un método requiere de variables u objetos para realizar su labor, éstos pueden declarase locales al método. En este sentido, sería un error respecto al paradigma declarar dichas variables u objetos como atributos de la clase, ya que no describen alguna propiedad o característica inherente a los objetos que deriven de la clase, sino que son sólo elementos necesarios para el almacenamiento del resultado y la realización del cálculo correspondiente a la responsabilidad (comportamiento) del método. Lo anterior se aplica aún cuando se utilizara una sola variable para almacenar el resultado de cualquiera de las cuatro operaciones aritméticas.

   Finalmente el método toString (líneas 61-63) requiere una mención aparte, ya que este método sobre escribe (razón por la cual se preservó el nombre del método) y en consecuencia re define el comportamiento previamente establecido en el método la clase Object del API de Java. Dicho método tiene como responsabilidad el regresar una representación en cadena del objeto que recibe el mensaje.

   La clase de prueba del Ejemplo Racional es la del Ejemplo PruebaRacional. Una posible salida corresponde a la mostrada en la siguiente figura:

Una posible salida de la ejecución del Ejemplo PruebaRacional. 

 

   Por último, aunque el Ejemplo PruebaRacional se explica a sí mismo, se resaltarán los siguientes aspectos:

• Las líneas 8 y 9 crean los números racionales r1 y r2, donde r1 = 1 / 3 y r2 = 2 / 5.
• Las líneas 13 y 14 envían los mensajes suma y multiplica respectivamente al objeto r1. Note que el argumento de ambos métodos es r2 y que al valor de retorno de dichos métodos (un número racional), le es enviado de manera implícita el mensaje toString para obtener la representación en cadena de los resultados correspondientes. Esto último sucede también con las líneas 11 y 12 pero para los objetos r1 y r2 respectivamente.

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.

Características fundamentales de la POO.

   Alan Curtis Kay, quien es considerado por muchos (yo entre ellos) como el padre de la POO, definió un conjunto de características fundamentales para el paradigma orientado a objetos.

   Con base en lo propuesto por Kay, en la Programación Orientada a Objetos:

1. Todo es un objeto.
2. El procesamiento es llevado a cabo por objetos:
1. Los objetos se comunican unos con otros solicitando que se lleven a cabo determinadas acciones.
2. Los objetos se comunican enviando y recibiendo mensajes.
3. Un mensaje es la solicitud de una acción, la cual incluye los argumentos que son necesarios para completar la tarea.
3. Cada objeto tiene su propia memoria, misma que está compuesta de otros objetos.
4. Cada objeto es una instancia de una clase. Una clase representa un grupo de objetos similares.
5. La clase es el repositorio del comportamiento asociado con un objeto.
1. Todos los objetos que son instancias de la misma clase llevan a cabo las mismas acciones.
6. Las clases están organizadas en una estructura jerárquica de árbol denominada jerarquía de herencia.
1. La memoria y el comportamiento asociados con las instancias de una clase, están automáticamente disponibles para cualquier clase asociada con la descendencia dentro de la estructura jerárquica de árbol.

   En un intento de complementar la visión de Alan Kay, se presenta a continuación un compendio de conceptos que definen también y refuerzan las características principales de la POO:

• La abstracción denota las características esenciales de un objeto.
• El proceso de abstracción permite seleccionar las características relevantes del objeto dentro de un conjunto e identificar comportamientos comunes para definir nuevos tipos de entidades.
• La abstracción es la consideración aislada de las cualidades esenciales de un objeto en su pura esencia o noción.
• La modularidad es la propiedad que permite subdividir una aplicación en partes más pequeñas (llamadas módulos), cada una de las cuales debe ser tan independiente como sea posible de la aplicación en sí, y de las partes restantes.
• La modularidad es el grado en el que los componentes de un sistema pueden ser separados y reutilizados.
• El encapsulamiento tiene que ver con reunir todos los elementos que pueden considerarse pertenecientes a una misma entidad al mismo nivel de abstracción. Esto permite aumentar la cohesión de los módulos o componentes del sistema. La encapsulación es quizá el concepto más importante del paradigma, ya que permite agrupar las funcionalidades (métodos) y el estado (datos) de los objetos de forma cohesiva. Los métodos proporcionarán los mecanismos adecuados para modificar el estado, y en algunos casos también serán la puerta de acceso a éste.
• El principio de ocultación de información (information hiding) se refiere a que cada objeto está aislado del exterior; es un módulo independiente y cada tipo de objeto presenta una interfaz a otros objetos, la cual especifica cómo es que pueden interactuar con él.
• El aislamiento protege a las propiedades de un objeto contra su modificación por quien no tenga derecho a acceder a ellas; solamente los propios métodos internos del objeto pueden acceder a su estado. Lo anterior asegura que otros objetos no puedan cambiar el estado interno de un objeto de manera accidental o intencionada, eliminando así efectos secundarios e interacciones inesperadas.
• El polimorfismo está relacionado con el aspecto referente al de qué tipo de comportamientos diferentes asociados a objetos distintos, pueden compartir el mismo nombre.
• El polimorfismo es la capacidad que tienen los objetos de naturaleza heterogénea, de responder de manera diferente a un mismo mensaje en función de las características y responsabilidades del objeto que recibe dicho mensaje.
• La herencia organiza y facilita el polimorfismo y el encapsulamiento, permitiendo a los objetos ser definidos y creados como tipos especializados de objetos preexistentes.
• Las clases no están aisladas, sino que se relacionan entre sí formando una jerarquía de clasificación.
• Los objetos heredan las propiedades y el comportamiento de todas las clases a las que pertenecen. Así, los objetos pueden compartir y extender su comportamiento sin tener que volver a implementarlo.
• La herencia múltiple se da cuando un objeto hereda de más de una clase.

   Es sumamente importante en lo subsecuente, tener todos estos conceptos vigentes y presentes, estudiarlos, analizarlos y comprenderlos; la memorización no es recomendable, ya que el memorizar conceptos no implica necesariamente su asimilación y mucho menos su comprensión. Por otro lado, si un concepto es comprendido, es posible entonces el poder explicarlo y deducir en consecuencia su definición.

   Mi deseo es que el lector reflexione sobre este aspecto y que, con un poco de paciencia, sume a su repertorio de conocimientos el conjunto de conceptos descritos hasta aquí, los cuales se pondrán en práctica eventual y progresivamente en entradas subsecuentes del blog.

POO (Consideraciones adicionales).

Respecto al envío de mensajes.

   La sintaxis general en Java para el envío de mensajes a un objeto es la siguiente:

objeto.mensaje(lista_de_argumentos);

donde objeto es un objeto de una clase previamente definida, y mensaje es uno de los métodos públicos definidos para dicha clase. La lista_de_argumentos es una lista de argumentos separada por comas, en donde cada argumento puede ser un objeto, o un tipo de dato primitivo.

Respecto a la sobrecarga de operadores.
   Algunos lenguajes de programación soportan un concepto relacionado con sobrecarga de operadores. La idea general del concepto de sobrecarga se ha planteado en la entrada POO (mensajes y métodos). El lenguaje de programación Java no soporta la sobrecarga de operadores, y por consiguiente, se ha omitido su descripción; sin embargo, es importante que el lector conozca que el concepto de sobrecarga no es exclusivo de los métodos o constructores, ni mucho menos de un lenguaje de programación en particular.

 

    La sobrecarga de operadores en C++ sí existe. En la sección correspondiente a las consideraciones adicionales para las colas de espera, se proporcionan un par de ejemplos al respecto. Para comprenderlos se requiere tener claros los aspectos relacionados con la implementación de la herencia, el funcionamiento de las colas de espera, y su respectiva especialización en la forma de colas de prioridad.

Respecto al paradigma.
   El establecimiento de niveles de acceso como private para los atributos de una clase, así como el uso de métodos de tipo set y get están directamente relacionados con el principio de ocultación de información (information hiding).

   Ahora bien, es probable que el lector haya notado que en la descripción del Ejemplo PruebaHerencia, en distintas ocasiones se hizo referencia a los objetos persona y científico como si fueran en sí mismos personas o entidades existentes. Lo anterior se hizo de manera deliberada, ya que como se comentó en la entrada referente al paradigma orientado a objetos, ésto eleva el nivel de abstracción y permite que se haga referencia a las entidades fundamentales del paradigma (los objetos), como elementos comunes de nuestro lenguaje natural, lo cual permite que los problemas se puedan expresar, al menos en principio, de una manera más natural e intuitiva.

   En este sentido, al dotar a los objetos de una personalidad propia con características y responsabilidades, en lugar de pensar en términos de datos, variables, y funciones o procedimientos que operen sobre dichos datos, se eleva el nivel de abstracción, facilitando con ello el análisis y la comprensión, ya que el problema y su solución pueden ser expresados y analizados en términos de su propio dominio, y no en el del medio (lenguaje de programación) de la solución. Ésta es una de las formas en la que las personas abstraemos, procesamos y utilizamos la información.

   Es sumamente importante que el lector tenga presente que en el paradigma orientado a objetos no se piensa en términos de datos, sino en términos de entidades con características y responsabilidades específicas, por lo que, cuando defina una clase, puede resultar útil el plantearse al menos un par de preguntas que le permitan determinar si los objetos derivados de su clase tienen o no sentido. Adicionalmente, las preguntas pueden ayudar también a establecer o coadyuvar en la meta de mantener una alta cohesión como parte del proceso de diseño e implementación:

1. ¿Los atributos representan características o propiedades, o definen un estado para los objetos que serán instanciados?
2. ¿La clase representa en sus métodos servicios, comportamiento, acciones o responsabilidades inherentes a los objetos que deriven de ella?

   Cabe mencionar que las preguntas propuestas son sólo una guía y una sugerencia al lector, no pretenden ser de ninguna manera una lista completa y absoluta. Con estas dos sencillas preguntas, además de validar y verificar su diseño de clases, estará reforzando también el concepto de encapsulamiento.

Respecto al polimorfismo.
   El polimorfismo es la cualidad de objetos heterogéneos de responder de distinta manera a un mismo mensaje. El tipo de polimorfismo más común se da en la herencia, pero no es el único.

   El Ejemplo Heterogéneo es un conjunto de clases (Automóvil, Motocicleta, Perro, Planta, Plomero, Profesor) heterogéneas que contienen un método de servicios. La idea es que, al menos en principio, cada una de dichas entidades ofrecen servicios distintos en función de su constitución y comportamiento general.

   Por otro lado, el Ejemplo Composición contiene tres clases: Libro, Publicación y Revista, las cuales presentan un comportamiento de polimorfismo en la forma en que se auto describen (imprimen), a través del método toString( ).

   En directa relación con el párrafo anterior, el tipo de polimorfismo más común se presenta en el Ejemplo Herencia, el cual contiene también las tres clases Libro, Publicación y Revista pero con un enfoque de polimorfismo basado en la herencia para la forma en que se auto describen (imprimen) a través del método toString( ).

   Existe un concepto en programación denominado latebinding, dynamic bindig o dynamic linkage, el cual se refiere a un mecanismo de programación en el cual el método que responderá al mensaje (el método que será invocado) es determinado en tiempo de ejecución. Como un ejemplo muy simple de esto, tómese el tiempo de comparar y analizar el Ejemplo PruebaHerencia (descrito en la entrada POO (Herencia)) y el Ejemplo PruebaPolimorfismo, en donde se muestra dicho concepto de programación, así mismo, es importante comprender tanto las diferencias de dichos ejemplos como los comentarios que aparecen en el código del Ejemplo PruebaPolimorfismo.

   Considere ahora el siguiente Ejemplo de late binding y tómese el tiempo que considere necesario para comprenderlo con base en el concepto de polimorfismo y  la comprensión de todos y cada uno de los ejemplos anteriores.

 

    Finalmente, una vez que se tengan madurados y comprendidos los ejemplos enunciados y su relación con el polimorfismo, se recomienda revisar también el tema de clases abstractas e interfaces (Java) para complementar dicho concepto.

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.

Árbol binario de búsqueda (ABB).

   Un árbol binario es una estructura de datos sumamente útil en muchos aspectos, en particular, cuando deben tomarse decisiones en dos sentidos en cada punto de un proceso determinado.

   Con base en lo anterior, suponga que por alguna razón se desea encontrar todos los duplicados de una secuencia de números. Para ello, considere lo siguiente:

1. El primer número de la secuencia se coloca en un nodo que se ha establecido como la raíz de un árbol binario, cuyos subárboles izquierdo y derecho estarán inicialmente vacíos.
2. Cada número sucesivo en la secuencia se compara con el número que se encuentra en la raíz del árbol binario. En este momento, se tienen tres casos a considerar:
1. Si coincide, se tiene un duplicado.
2. Si es menor, se examina el subárbol izquierdo.
3. Si es mayor, se examina el subárbol derecho.
3. Si alguno de los subárboles esta vacío, el número no es un duplicado y se coloca en un nodo nuevo en dicha posición del árbol binario.
4. Si el subárbol correspondiente no está vacío, se compara el número con la raíz del subárbol en cuestión, y se repite todo el proceso nuevamente con dicho subárbol.

   Un árbol binario de búsqueda (ABB) es un árbol binario que no tiene valores duplicados en los nodos, y además, tiene las siguientes características:

1. Los valores en cualquier subárbol izquierdo son menores que el valor en su nodo padre.
2. Los valores en cualquier subárbol derecho son mayores que el valor en su nodo padre.

   Tome en cuenta que un ABB es un árbol binario, pero un árbol binario no es necesariamente un ABB. En este sentido, todo lo que se ha dicho y definido para árboles binarios, es aplicable también a los árboles binarios de búsqueda.

Operaciones primitivas.

   Respecto a las operaciones primitivas, se definen cuatro operaciones primitivas para un ABB:

• inserta: inserta un nuevo nodo al árbol binario de búsqueda. La inserción se realiza de manera ordenada respecto del elemento a insertar, por lo que debe existir una relación de orden definida para el conjunto de datos al que pertenece dicho elemento.

   En resumen, la operación inserta de manera ordenada a elemento en el ABB cuando el objeto abb recibe el mensaje correspondiente, es decir: abb.inserta(elemento).

• recorre en preorden: recorre el ABB no vacío en orden previo, de tal forma que cuando el objeto abb recibe el mensaje: abb.recorrePreorden( ) se imprime en la salida estándar el recorrido en orden previo de abb.

• recorrido en orden: recorre el árbol binario de búsqueda no vacío en orden, de tal forma que cuando el objeto abb recibe el mensaje: abb.recorreEnorden( ) se imprime en la salida estándar el recorrido en orden de abb.

   Note cómo un recorrido en orden, como su nombre lo indica, imprime en la salida estándar los elementos almacenados en el árbol ordenados de manera ascendente.

• recorrido en postorden: recorre el ABB no vacío en orden posterior, de tal forma que cuando el objeto abb recibe el mensaje: abb.recorrePostorden( ) se imprime en la salida estándar el recorrido en orden posterior de abb.

   Para el caso de un árbol binario de búsqueda, también serían deseables otras operaciones, como aquellas que se definieron para los árboles binarios: primitivas, operaciones adicionales que podrían ser útiles y recorridos inversos por ejemplo (vea las entradas Árboles binarios (operaciones primitivas) y Árboles binarios (recorridos)).

   En este sentido, es importante resaltar que siempre que una operación no viole la relación de orden intrínseca a los ABB, es factible de ser implementada y que la decisión final respecto a su implementación estará en directa función de si ésta tiene o no sentido en la aplicación que se esté desarrollando.

Árboles binarios (definición).

   Un árbol binario es un conjunto finito de elementos el cual está vacío, o dividido en tres subconjuntos disjuntos:

1. El primer subconjunto contiene un elemento único llamado raíz del árbol.
2. El segundo subconjunto es en sí mismo un árbol binario y se le conoce como subárbol izquierdo del árbol original.
3. El tercer subconjunto es también un árbol binario y se le conoce como subárbol derecho del árbol original.

   Tome en consideración que en un árbol binario, tanto el subárbol izquierdo como el subárbol derecho podrían estar vacíos.

Representación y conceptos.

   Respecto a su representación, es común denominar a cada elemento de un árbol binario como nodo del árbol. La siguiente figura muestra una posible representación para un árbol binario:

Abstracción de un árbol binario como una estructura de nodos.

 

    Ahora bien, la representación de árbol binario de la figura anterior resultará sumamente útil para desarrollar e ilustrar los siguientes conceptos:

• Si B es la raíz de un árbol binario y D es la raíz del subárbol izquierdo/derecho (todos los conceptos que sigan esta notación tienen una naturaleza simétrica debido a la característica inherente a los árboles y por lo tanto, aplica tanto para el subárbol izquierdo como para el subárbol derecho), se dice que B es el padre de D y que D es el hijo izquierdo/derecho de B.
• A un nodo que no tiene hijos como los nodos A o C, se le conoce como nodo hoja.
• Se dice que un nodo n1 es un ancestro de un nodo n2 (y que n2 es un  descendiente de n1) si n1 es el padre de n2 o el padre de algún ancestro de n2.
• Recorrer un árbol de la raíz hacia las hojas se denomina descender el árbol, y al sentido opuesto, ascender el árbol.
• El nivel de un nodo en un árbol binario se define del modo siguiente:

1. La raíz del árbol tiene el nivel 0.
2. El nivel de cualquier otro nodo en el árbol es uno más que el nivel de su nodo padre.

• La profundidad o altura de un árbol binario, es el máximo nivel de cualquier hoja en el árbol.

   Por otro lado, se dice que un árbol estrictamente binario es aquel en el que cada nodo que no es hoja, tiene sus subárboles izquierdo y derecho no vacíos. En términos coloquiales, un árbol estrictamente binario es un árbol binario en el que cada nodo, tiene dos hijos o simplemente no tiene; es decir, no se vale tener un solo hijo: dos o nada.

   De lo anterior, observe que un árbol estrictamente binario con n hojas, siempre contiene 2n - 1 nodos (¿Por qué?).

   Otro tipo de árboles binarios son los árboles binarios completos. Un árbol binario completo de profundidad p, es un árbol estrictamente binario que tiene todas sus hojas en el nivel p.

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.

Listas circulares.

   Las listas enlazadas, también denominadas listas simplemente enlazadas, son sumamente útiles y convenientes para diferentes usos y aplicaciones; algunas de las cuales ya han sido mencionadas. Aunque las listas simplemente enlazadas son muy dinámicas presentan, como casi todo en la vida, ciertos inconvenientes.

   Algunas de las situaciones indeseables que se tienen con una lista simplemente enlazada son las siguientes:

• Dada una única referencia a un nodo determinado de la lista enlazada y suponiendo que éste no sea el primero, no se puede llegar a ninguno de los nodos que lo preceden, es decir, no pueden alcanzarse los nodos anteriores a él.
• Si por alguna razón se recorre la lista enlazada, siempre debe conservarse una referencia externa (además de la que se utilizó para el recorrido) al inicio de dicha lista enlazada con la finalidad de poder volver a recorrer la lista nuevamente en caso de ser necesario.

   Con base en lo anterior, considere la siguiente modificación respecto a la estructura de una lista simplemente enlazada:

El elemento siguiente en el último nodo hará referencia al primer nodo y no a null; siendo en esto diferente a lo que se define para una lista simplemente enlazada convencional.

   Al tipo de lista enlazada que adopta dicha modificación se le denomina lista simplemente enlazada circular. Su representación se muestra en la siguiente figura:

Abstracción de una lista simplemente enlazada circular representada como una secuencia de nodos.

 

    Es importante hacer notar que en una lista enlazada circular es posible llegar a cualquier otro nodo de la estructura de datos partiendo de un nodo distinto cualquiera, lo cual subsana los dos inconvenientes enunciados al principio de esta sección para una lista simplemente enlazada.

   Observe también que una lista enlazada circular no tiene un “primer” o “último” nodo natural, por lo que se debe establecer un primer y último nodo por convención, lo cual es más una conveniencia que una característica inherente a la estructura de datos.

   Finalmente, tome en cuenta que una referencia a null/nullptr (Java/C++) representa una lista circular vacía, y que una lista circular de un solo nodo es un nodo cuyo atributo de auto referencia contiene una referencia hacia sí mismo como lo muestra la siguiente figura:

Lista circular de un solo elemento.

   El problema de Josephus.

   El siguiente es un problema clásico en el área de las estructuras de datos, y su solución utilizando listas enlazadas circulares es una aplicación clave:

   Un grupo de soldados se encuentra rodeado por una abrumadora fuerza enemiga. No hay esperanza de victoria sin refuerzos. Lamentablemente, sólo hay un caballo disponible para ir en su busca (o escapar).

   Los soldados realizan un pacto de honor para determinar cuál de ellos tomará el caballo y, en el mejor de los casos, pedirá ayuda. Para ello, forman un círculo y van eligiendo un número de un sombrero (n). También se elige uno de los nombres de los soldados de otro sombrero.

   Iniciando con el soldado cuyo nombre se eligió, se empieza a contar en el sentido de las manecillas del reloj alrededor del círculo. Cuando la cuenta llega a n el soldado correspondiente se retira del círculo y la cuenta vuelve a empezar con el soldado que se encontraba a su derecha.

   El proceso continúa análogamente hasta que sólo queda un soldado, mismo que tomará al caballo y pedirá ayuda (o escapará trágica e irremediablemente para los demás soldados).

   En resumen el problema de Josephus es: dado un número entero positivo n, el ordenamiento de los soldados en el círculo, y el soldado a partir del que comienza la cuenta, determinar:

1. El orden en el cual se eliminan los soldados del círculo.
2. Cuál soldado es el que escapa.

   La solución al problema de Josephus se deja como ejercicio para el lector.

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.

Algunas aplicaciones (pilas).

    A continuación se presentan algunas de las aplicaciones más representativas de una pila, cabe mencionar que esta selección es necesariamente incompleta.

Análisis básico de expresiones.
   Considere la siguiente expresión:

   Se insta al lector a que sea tan amable de contestar una por una, las siguientes preguntas:

• ¿Es clara?, es decir, ¿se entiende?
• Para valores concretos de x, y, y j, ¿podría evaluarla?
• ¿Puede escribir la misma expresión en una sola línea de texto, como lo haría para un programa?

   La representación "lineal" de la expresión anterior se muestra a continuación:

7 – ( (x * ( (x + y) / (j - 3) ) + y) / (4 – 5/2) )

   Observe que la expresión anterior contiene paréntesis, los cuales son indispensables para agrupar de manera apropiada las operaciones involucradas, mientras que la primera representación no los tiene, ya que son innecesarios. Ahora bien, en base a lo anterior considere lo siguiente:

• ¿Cómo saber que la expresión lineal está correctamente balanceada en cuanto a paréntesis se refiere, de tal forma que represente exactamente lo mismo que la expresión original?
• ¿Y si la expresión original fuera más grande y/o más compleja?

   Considere ahora esta otra expresión:

   Cuya representación “lineal” está dada por:

{x + (y – [a + b]) * c – [ (d + e) ] } / (h – (j – (k – [l - n] ) ) )

   Al igual que antes:

• ¿Cómo saber si la expresión lineal está correctamente balanceada en cuanto a símbolos de agrupación se refiere? Note que ahora se han introducido otros símbolos de agrupación de expresiones (corchetes y llaves) además de los paréntesis.
• Adicionalmente, ¿cómo saber que un símbolo de agrupación está cerrando a su correspondiente símbolo de apertura?, es decir, ¿cómo saber que los símbolos de agrupación están correctamente asociados?

   Debería resultar claro que es mucho más fácil para las personas comprender expresiones denotadas como en las expresiones originales; sin embargo, las representaciones "lineales" son las que se utilizan en los lenguajes de programación, por lo que se requiere de un mecanismo que verifique de manera automática que una expresión esté bien escrita, al menos en cuanto a símbolos de agrupación se refiere; para ello, considere el siguiente Algoritmo de verificación de balanceo:

   valida = true;
   p = pila vacía;

   while( no sea fin de cadena y la expresion sea válida ){
      procesar el siguiente símbolo de la cadena;

      if ( símbolo == ‘(’ | | símbolo == ‘[’ | | símbolo == ‘{’ )
         p.push(símbolo);
      else if ( símbolo == ‘)’ | | símbolo == ‘]’ | | símbolo == ‘}’ ){
         if ( p.estaVacia( ) )
            valida = false;
         else{
            char s = p.pop( );
            if ( s no es equivalente a símbolo )
               valida = false;
         }
      }
   }  // while

   if ( !p.estaVacia( ) )
      valida = false;
 
   if ( valida )
      println("La expresión es correcta y está balanceada.”);
   else
      println("Existe error en los símbolos de agrupación.”);

Algoritmo de verificación de balanceo.

   Dada una expresión almacenada en una cadena, el Algoritmo de verificación de balanceo utiliza una pila para realizar la verificación de los símbolos de agrupación que se encuentren en dicha expresión.

   Se deja como ejercicio para el lector realizar una implementación de dicho algoritmo, así como la resolución de los aspectos inherentes a la equivalencia de símbolos (vea el Ejercicio 9 de la entrada Ejercicios selectos para pilas Java y C++ respectivamente).

   Notación interfija, postfija y prefija.

   Considere la suma de dos números cualesquiera A y B. Aplicar el operador “+” a los operandos A y B y representar la suma como A + B tiene el nombre de representación o notación interfija.

   La notación interfija, aunque es la más común, no es la única. Existen al menos otras dos notaciones alternativas para expresar la suma de A y B utilizando los mismos símbolos A, B y +:

1. + A B representación o notación prefija.
2. A B + representación o notación postfija.

   Los prefijos “pre”, “pos” e “inter” hacen referencia a la posición relativa del operador en relación a los operandos.

   El llamado o invocación a una función en un lenguaje de programación gobernado por el paradigma estructurado, como el lenguaje C por ejemplo, utiliza notación prefija (considere por ejemplo la suma de dos números enviados a una función invocada mediante suma(a, b)), ya que el operador (suma) precede a los operandos (a, b).

   Conversión de interfija a postfija.
   Considere la siguiente expresión:

A + B x C

la cual implícitamente indica:

A + (B x C)

   Suponga que se desea convertir la expresión anterior a su representación en postfija ¿Cómo proceder?

   Los ejemplos siguientes asumen una representación "lineal" de las expresiones. En base a lo anterior, es importante que el lector tenga presente que el proceso de conversión se basa en las reglas de precedencia de los operadores involucrados en la expresión a convertir.

   Así, para convertir una expresión de su notación interfija a su notación postfija, se tienen lo siguientes pasos:

1. A + (B x C)     forma interfija.
2. A + (BC x)    se convierte la multiplicación y el nuevo elemento se considera como un solo número (de hecho, después de aplicar el operador el resultado (producto) es en efecto, otro número).
3. A (BC x) +    se convierte la suma con las mismas consideraciones expuestas en el punto anterior.
4. A B C x +     se eliminan paréntesis para obtener la representación final en postfija.

   Con base en lo anterior, es posible afirmar que las dos reglas que se siguen durante el proceso de conversión a postfija son las siguientes:

1. Las operaciones con mayor precedencia se convierten primero. Si existe más de una operación con la misma precedencia, se resolverá primero la que esté más a la izquierda.
2. Después de que una parte de la expresión se ha convertido a notación postfija, ésta se considerará como un operando único.

   Ejemplo:
   Dada la siguiente expresión (note que no es la misma que la expresión anterior):

(A + B) x C

convierta dicha expresión a su notación postfija.

   En base a lo expuesto con anterioridad, el proceso de solución está dado por los siguientes pasos:

1. (A + B) x C    forma interfija.
2. (A B +) x C    se convierte la adición.
3. (A B +) C x    se convierte la multiplicación.
4. A B + C x       se eliminan paréntesis: representación postfija.

   Conversión de interfija a prefija.

   Las reglas para convertir una expresión de su notación interfija a su notación prefija son idénticas a las de conversión de interfija a postfija. El único cambio a considerar es que ahora el operador se coloca antes de los operandos en lugar de colocarlo después de ellos.
 
   Aspectos a considerar.
Finalmente, respecto a las notaciones prefija y postfija cabe hacer mención de un par de consideraciones:

1. La representación prefija no siempre es una imagen reflejo de la representación postfija.
2. El orden de los operadores en las expresiones postfijas determina el orden real de las operaciones al evaluar la expresión, haciendo en consecuencia innecesario el uso de paréntesis.

   En la entrada correspondiente a los Ejercicios selectos para pilas Java y C++ respectivamente tendrá la oportunidad de practicar y de ampliar su experiencia al respecto.

   Evaluación de expresiones.

   Aunque para las personas en general es más fácil y natural comprender las expresiones interfijas (quizá porque en su mayoría así fuimos instruidos y así estamos acostumbrados pero, ¿qué pasaría si desde pequeños, en lugar de haber aprendido a realizar operaciones utilizando notación interfija, se nos hubiera enseñado a realizarlas utilizando notación prefija por ejemplo? ¿Qué sería entonces lo fácil y natural de comprender?), el procesamiento de dichas expresiones por medio de una computadora no es nada sencillo.

   Considere lo siguiente: dada una expresión en notación interfija con valores específicos ¿Cómo evaluaría algorítmicamente dicha expresión? Piense y reflexione en ello antes de continuar.

   Ahora bien, con valores específicos para una expresión en notación postfija ¿Cómo evaluaría algorítmicamente dicha expresión? Para esto último, considere el siguiente Algoritmo de evaluación de una expresión en notación postfija:

         pilaOperandos = pila vacía;

         while(no sea fin de cadena){
             símbolo = siguiente carácter de la cadena;
             if(símbolo es un operando)
                   pilaOperandos.push(símbolo);
             else{
                   numero2 = pilaOperandos.pop( );
                   numero1 = pilaOperandos.pop( );
                   resultado = numero1 símbolo numero2;
                   pilaOperandos.push(resultado);
             }
         }
         return pilaOperandos.pop();

Algoritmo de evaluación de una expresión en notación postfija.

   La solución propuesta por el Algoritmo de evaluación de una expresión en notación postfija se basa, como es de esperarse, en una pila. Se deja como ejercicio al lector el análisis y comprensión de dicho algoritmo, así como su correspondiente implementación (consulte la entrada correspondiente a Ejercicios selectos para pilas Java y C++ respectivamente para obtener mayor información).