Consideraciones adicionales (colas).

   Las colas de espera, y las colas de prioridad ascendentes y descendentes tienen amplias y muy variadas aplicaciones, que van desde la simulación y modelado de situaciones relacionadas con las líneas de espera que hacemos todos los días (bancos, boletos, casetas de cobro, etc.), hasta aspectos de bajo nivel relacionado con el funcionamiento de los sistemas operativos por ejemplo.

   Las colas de prioridad son un ejemplo sumamente claro en el que la definición de la estructura de datos o ADT es independiente de la implementación, debido a que es posible implementar una cola de prioridad por ejemplo, de al menos dos maneras o enfoques posibles.

   La introducción hacia las relaciones de orden en los objetos por medio de la interfaz Comparable presentada en la entrada de Colas de prioridad (Java) resultará fundamental para las entradas siguientes, por lo que se invita al lector a estudiar detenidamente estos conceptos y complementarlos con información adicional como ejercicio y labor de investigación.

    Por otro lado pero en directa correspondencia con las relaciones de orden se proporcionan adicionalmente, para los lectores interesados en desarrollar sus habilidades en C++, dos ejemplos que podrían ser útiles para el desarrollo de los ejercicios propuestos. El primero de ellos tiene que ver con la implementación de operadores, que en el lenguaje en cuestión se denomina sobrecarga de operadores. Ambos ejemplos se basan en un ejemplo previo estudiado con anterioridad en el tema correspondiente a la implementación de la herencia, por lo que sería recomendable echarle antes un vistazo. El segundo ejemplo muestra el funcionamiento de la sobre carga de operadores en la herencia. Se insta al lector a analizarlos, comprender las diferencias y el resultado de la ejecución, con la finalidad de que le sirvan como base para el desarrollo de los ejercicios.

   Finalmente, resulta sumamente importante que el lector se tome el tiempo para la realización de los ejercicios propuestos, los cuales tienen, como todos los ejercicios del blog, la finalidad de reforzar, ampliar, desarrollar y poner en práctica tanto los conceptos como los conocimientos adquiridos. Le auguro éxito.

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.

Colas de espera (definición).

Definición.

   Una cola de espera o simplemente cola, es un conjunto ordenado de elementos del que se pueden eliminar dichos elementos de un extremo (llamado inicio de la cola), y en el que pueden insertarse elementos en el extremo opuesto (llamado fin de la cola).

   El primer elemento insertado en una cola es el primer elemento en ser eliminado, mientras que el último elemento insertado es el último en ser eliminado. Por esta razón, se dice que una cola es una estructura de datos de tipo FIFO (First In First Out).

   En el mundo real abundan ejemplos de este tipo de estructuras:

• Líneas aéreas.
• Líneas de autobuses.
• Colas de espera en los supermercados.
• Colas de espera en los bancos.
• Etcétera, etcétera, etcétera.

   La siguiente figura muestra en (a) una representación de una cola de espera que permite visualizar los elementos almacenados en la misma:

Inserción y eliminación de elementos en una cola de espera.

   La eliminación de uno de los elementos (A) se muestra en la figura anterior en (b), mientras que la inserción de los elementos D y E se muestra en (c). Observe también cómo las referencias al inicio y fin de la cola son modificadas en cada inserción y eliminación respectivamente.

Operaciones primitivas.

   Se definen tres operaciones primitivas sobre una cola de espera:

1. La operación inserta agrega un elemento en la parte final de la cola. También se dice que esta operación forma o encola un elemento en la estructura de datos.
2. La operación elimina suprime un elemento de la parte inicial de la cola. Esta operación despacha o atiende al elemento que se encuentra al inicio de la cola.
3. La operación estaVacia (esta operación fue definida como opcional o deseable para la pila. Para el caso de la cola dicha operación es ahora una primitiva, por lo que su implementación es requerida) regresa verdadero o falso dependiendo de si la cola de espera contiene o no elementos respectivamente.

   Una operación deseable para una cola de espera, sería la de imprimir todos los elementos de la cola, la cual se denotará como imprime.

Representación.

   La representación mostrada en la siguiente figura es una abstracción de la implementación que se realizará en la entrada correspondiente a la implementación:

Abstracción de una cola de espera como una secuencia de nodos.

 

    Observe cómo la figura anterior luce muy similar a la de la pila. Sin embargo, esta figura muestra el uso de dos referencias: inicio y fin, las cuales denotan, respectivamente, el primero y último de los elementos almacenados en la cola de espera. 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 siguientes muestran el diseño de clases para la cola de espera que se desea implementar. Dicho diseño complementa, en consecuencia, la definición de dicha estructura de datos. A su vez, los diagramas de clases muestran también la relación que existe entre las clases más importantes que se involucrarán durante la implementación de la estructura de datos en cuestión.

Diagrama de clases UML para la cola de espera (Java).

Diagrama de clases UML para la cola de espera (C++).

    En este sentido valdría la pena hacer una aclaración: lo más deseable sería generar un diagrama de clases que representara la idea general del diseño de la estructura de datos con independencia del lenguaje de implementación; sin embargo, con la finalidad de enfatizar las diferencias a considerar en la implementación, se ha optado por manejar dos diagramas de clases que, aunque esencialmente iguales, especifican diferencias sutiles con respecto a los lenguajes de programación utilizados para los ejemplos.

Consideraciones adicionales (pilas).

   La pila es una estructura de datos sumamente importante y ampliamente utilizada en distintas áreas no sólo de la computación. Su definición y funcionalidad es clara y simple, por lo que no es casual que haya sido la primera estructura de datos estudiada y presentada en el blog.

   Por otro lado, los conceptos expuestos en el blog respecto a los genéricos en Java y C++ resultarán fundamentales para los siguientes temas, ya que todas las estructuras de datos siguientes se basan en ellos, por lo que se invita nuevamente al lector a realizar un repaso de los conceptos relacionados con los genéricos así como a tener presente la importancia de los mismos a lo largo de las estructuras de datos subsecuentes.

   Adicionalmente, una vez que se han presentado los conceptos de pila (definición y operaciones) y una propuesta de implementación, resulta fundamental el conocer el esquema de relación que existe entre las clases más importantes involucradas en la implementación de la pila genérica estudiada. Los siguientes diagramas de clases UML presentan dicha relación respecto a las dos implementaciones realizadas:

Diagrama de clases UML para la pila genérica (Java).

 

    Insto amablemente al lector a que se tome el tiempo que considere necesario para comparar el diagrama de clases de la figura anterior con las clases en Java que implementan la pila genérica (Ejemplo Pila), el nodo genérico (Ejemplo NodoG), y la excepción de estructura de datos vacía (Ejemplo ExcepcionEDVacia).

 

Diagrama de clases UML para la pila genérica (C++).

 

    De manera similar a lo dicho en el párrafo anterior para el Ejemplo pila_genérica de C++.

   Los detalles de UML quedan fuera de los alcances del blog; sin embargo, los diagramas de clases UML de las figuras anteriores muestran una relación de composición entre la clase Pila y la clase NodoG (Nodo) de cero a muchos (0 .. *), lo cual quiere decir que una pila puede tener ninguno, uno, o muchos nodos. Por otro lado, también se muestra la relación de asociación uno a uno existente entre la clase Pila y la clases de excepción correspondientes a cada diagrama (observe también que los diagramas de clases muestran así mismo la relación de herencia que existe para las excepciones).

   Asegúrese de comprender el diagrama UML que sea de su interés respecto al lenguaje que esté utilizando así como su relación con los ejemplos citados, ya que en las entradas siguientes se utilizarán este tipo de diagramas de clases UML en complemento con la definición del ADT, para definir la implementación de la estructura de datos correspondiente.

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

Ejercicios selectos (pilas).

1. En el Ejemplo PilaPrimitiva el método imprime tiene las líneas 50 y 52 como comentarios ¿Qué sucede si sustituye la línea 51 por la línea 50 y la línea 53 por la línea 52? ¿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.  Con base en el Ejemplo PilaPrimitiva, haga una implementación completa de una pila que almacene char primitivos y pruébela Cuando termine, considere lo siguiente:
1. ¿Puede visualizar las implicaciones de este ejercicio?
2. ¿Qué pasa por ejemplo si ahora se necesita almacenar datos de tipo double?
3. En el Ejemplo PruebaPila se creó una pila utilizando un constructor sin argumentos. Modifique dicho ejemplo para asignar un nuevo nombre a la pila por medio del constructor correspondiente; asígnele a la pila el nombre de "Mi primera pila", recompile y pruebe su funcionamiento.
4. Modifique el Ejemplo PruebaPila para que permita leer n números enteros desde la entrada estándar y los almacene en la Pila.
5. En el blog, durante la explicación del Ejemplo PruebaPila, se menciona la cláusula try-catch-finally; sin embargo, en dicho ejemplo sólo se muestra el uso de la cláusula try-catch. Investigue y documéntese acerca del uso y funcionamiento de la cláusula completa try-catch-finally. También investigue más acerca del uso y manejo de excepciones, así como la documentación del API respecto al método printStackTrace.
6. Modifique el Ejemplo Pila para que:
1. Agregue el método peek a la implementación. Recuerde que dicha operación hecha un vistazo al elemento que se encuentra en el tope de la pila y 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 pila. 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: size( ).
7. Tomando como referencia el Ejemplo PruebaPilaGenerica, modifíquelo para que la pila genérica del Ejemplo Pila 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).
8. Utilice una pila para verificar si, dada una expresión, ésta es o no un palíndromo. Un palíndromo es una frase o expresión que se lee o interpreta igual procesándola de izquierda a derecha, que de derecha a izquierda. Algunos ejemplos de palíndromos son (Nota: Simplifique el problema y no considere acentos ni la letra ñ en su implementación):
1. 1991.
2. 2002.
3. Hannah.
4. Reconocer.
5. Se van sus naves.
6. Ateo por Arabia iba raro poeta.
7. Dábale arroz a la zorra el abad.
8. Anita lava la tina.
9. La ruta nos aportó otro paso natural.
10. Las Nemocón no comen sal.
11. No di mi decoro, cedí mi don.
12. A la catalana banal, atácala.
9. Realice la implementación del Algoritmo de verificación de balanceo presentado en la entrada Algunas aplicaciones de las pilas. Para lo anterior, construya una clase cuyo nombre sea Expresion, e implemente dicho algoritmo como uno de los servicios o acciones de la clase, identifique al método como verificaBalance de tal forma que su firma sea: public boolean verificaBalance( );.
1. No olvide realizar las pruebas correspondientes para validar y verificar la funcionalidad de su propuesta.
2. Sugerencia: implemente la verificación de equivalencia de símbolos como un método privado; es decir, un método que proporcione servicio a otros métodos de la misma clase (servicio interno), pero no a los objetos instanciados (servicios públicos).
10. Convierta paso a paso utilizando papel y lápiz, las siguientes expresiones en su representación en interfija a su correspondiente notación postfija. Nota: el símbolo @ representa la potencia y es el de mayor precedencia. Note que se han proporcionado las soluciones correspondientes:
1. A + B.
1. A B +.
2. A + B - C.
1. A B + C -.
3. (A + B) * (C - D).
1. A B + C D - *.
4. A @ B * C – D + E / F / (G + H).
1. A B @ C * D - E F / G H + / +.
5. ((A + B) * C – (D - E)) @ ( F + G).
1. A B + C * D E - - F G + @.
6. A – B / (C * D @ E).
1. A B C D E @ * / -.
11. Continuando con la idea planteada en el ejercicio anterior, convierta paso a paso las expresiones pero ahora a su representación en notación prefija. Se proporcionan a continuación las soluciones correspondientes:
1. + A B.
2. - + A B C.
3. * + A B - C D.
4. + - * @ A B C D / / E F + G H.
5. @ - * + A B C - D E + F G.
6. - A / B * C @ D E.
12. Diseñe un algoritmo, así como su correspondiente implementación, para convertir una expresión en notación interfija a su correspondiente notación postfija y prefija respectivamente. Agregue los métodos siguientes a la clase Expresion iniciada en el Ejercicio 9. Asegúrese de probar sus implementaciones con al menos, los dos ejercicios anteriores:
1. Postfija (firma del método public String obtenPostfija( )).
2. Prefija (método public String obtenPrefija( )).
13. Realice la implementación del Algoritmo de evaluación de una expresión en notación postfija presentado en la entrada Algunas aplicaciones de las pilas. Implemente dicho algoritmo como uno de los servicios de la clase Expresion iniciada en el Ejercicio 9. Proponga una firma de método ad hoc a la responsabilidad de éste pero utilice el identificador evaluaPostfija.
1. No olvide realizar las pruebas correspondientes para validar y verificar la funcionalidad de su propuesta.
2. Sugerencia: implemente la realización de la operación representada por símbolo como un método privado; es decir, un método que proporcione servicio a otros métodos de la misma clase (servicio interno), pero no a los objetos instanciados (servicios públicos).
14. Repita el Ejercicio 9 con la clase Stack del API de Java:
1. Desde el punto de vista de la ejecución, ¿nota alguna diferencia?
2. ¿Tendría alguna ventaja o desventaja utilizar el API?
3. Si la clase Pila del Ejemplo Pila fuera parte del API de Java, ¿cuál utilizaría y por qué?