Pilas (implementación C++).

    La representación de una pila, como una secuencia de nodos, se muestra en la siguiente figura:

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

 

     Los detalles de su implementación se desarrollarán a continuación en dos secciones: Pila primitiva y Pila genérica.

 Pila primitiva.

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

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

   La implementación de la estructura de datos pila se muestra en la clase pila_primitiva (líneas 36-48 del archivo pila_primitiva.h), y su explicación se centrará únicamente en la definición de los métodos push, pop, esta_vacia e imprime del archivo pila_primitiva.cpp.

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

   Por otra parte, el método push (líneas 55-60), recibe como argumento el elemento a insertar en la pila (elemento), y se apoya del método esta_vacia y de los constructores para realizar la inserción de la siguiente manera:

• Si la pila está vacía (línea 56), se crea un nuevo nodo con el elemento correspondiente (línea 57) para el atributo dato, y nullptr en su atributo siguiente (vea la clase Nodo_p).
• Si la pila no está vacía (línea 58), se crea un nuevo nodo con el elemento correspondiente para el atributo dato y con el tope actual de la pila en su atributo siguiente (línea 59). Así mismo, note que el tope es actualizado para hacer referencia al nodo recién creado, dando el efecto de corrimiento a la derecho o hundimiento del tope anterior.

   Ahora bien, observe que el método pop (líneas 63-73) posee una característica particular: el método especifica (línea 63) que podría lanzar (throw( )) una excepción bajo determinadas circunstancias; específicamente, el método lanza la excepción excepcion_ED_vacia (línea 65)  al intentar eliminar un elemento de la pila cuando ésta está vacía (líneas 64-65). Note que la declaración del método en la clase pila_primitiva (línea 45 del archivo pila_primitiva.h) se corresponde con su definición.

   La excepción excepcion_ED_vacia está definida en la línea 41 del archivo pila_primitiva.h. Esta excepción es la que será utilizada en todas las estructuras de datos del blog que se implementan en C++.

   Continuando con el ejemplo en curso, si la estructura de datos no está vacía, el método pop recupera el dato almacenado (línea 67), y desecha el nodo correspondiente al hacer que el tope haga ahora referencia al elemento siguiente del tope actual (línea 69), para finalmente regresar el dato recuperado (línea 72). Note también que la referencia al tope ha sido previamente respaldada en tmp (línea 68), y es mediante dicho apuntador que se liberará la memoria (línea 70) asociada al nodo del que se ha extraído el dato a eliminar. En C++ la liberación de la memoria asignada con new debe realizarse de manera explícita mediante un delete.

   Por último, en el método imprime (líneas 81-94), si la estructura de datos está vacía (línea 82), se reporta (línea 83); en caso contrario, se realiza un recorrido por todos los nodos de la estructura para imprimir su contenido (líneas 84-93).

   El programa principal para la pila primitiva se presenta en el archivo main.cpp del Ejemplo pila_primitiva. Observe cómo en la línea 19 se crea la pila y se utiliza el constructor por omisión (constructor sin argumentos).

   Las líneas 22-25 realizan la inserción en la pila de los números del cero al nueve; por cada inserción se imprime todo el contenido de la pila tal y como se muestra a continuación:

La Pila de enteros primitivos es: 0
La Pila de enteros primitivos es: 1 0
La Pila de enteros primitivos es: 2 1 0
La Pila de enteros primitivos es: 3 2 1 0
La Pila de enteros primitivos es: 4 3 2 1 0
La Pila de enteros primitivos es: 5 4 3 2 1 0
La Pila de enteros primitivos es: 6 5 4 3 2 1 0
La Pila de enteros primitivos es: 7 6 5 4 3 2 1 0
La Pila de enteros primitivos es: 8 7 6 5 4 3 2 1 0
La Pila de enteros primitivos es: 9 8 7 6 5 4 3 2 1 0

    Por otro lado, las líneas 28-36 realizan la eliminación de los elementos de la pila (uno a uno). Dicho fragmento de código intenta eliminar once elementos (líneas 30-35) de la pila (recuerde que sólo fueron insertados diez elementos, por lo que al intentar eliminar el décimo primero, se generará la excepción excepcion_ED_vacia), y dado que el método pop puede lanzar una excepción, el código involucrado en la eliminación debería estar dentro de una cláusula try-catch, la cual permite atrapar (cachar) las excepciones que un método pudiera lanzar y, si así se desea, realizar la gestión que más convenga.

   Si se genera un excepción excepcion_ED_vacia, ésta es atrapada y el flujo de control se envía al ámbito de la cláusula catch en donde se realiza el correspondiente tratamiento de la excepción (líneas 36-38).

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

Elemento eliminado de la pila: 9
La Pila de enteros primitivos es: 8 7 6 5 4 3 2 1 0
Elemento eliminado de la pila: 8
La Pila de enteros primitivos es: 7 6 5 4 3 2 1 0
Elemento eliminado de la pila: 7
La Pila de enteros primitivos es: 6 5 4 3 2 1 0
Elemento eliminado de la pila: 6
La Pila de enteros primitivos es: 5 4 3 2 1 0
Elemento eliminado de la pila: 5
La Pila de enteros primitivos es: 4 3 2 1 0
Elemento eliminado de la pila: 4
La Pila de enteros primitivos es: 3 2 1 0
Elemento eliminado de la pila: 3
La Pila de enteros primitivos es: 2 1 0
Elemento eliminado de la pila: 2
La Pila de enteros primitivos es: 1 0
Elemento eliminado de la pila: 1
La Pila de enteros primitivos es: 0
Elemento eliminado de la pila: 0
Vacia: Pila de enteros primitivos

terminate called after throwing an instance of 'pila::pila_primitiva::excepcion_ED_vacia'

Abortado

    Finalmente, se presenta al lector en Ejemplo pila_primitiva2 una versión alternativa del ejemplo ya descrito. La diferencia es sutil pero importante y se basa en la excepción. En este sentido, es importante que se tome el tiempo para comparar ambas versiones, particularmente las líneas 50-53 del archivo pila_primitiva.h, líneas 99-101 del archivo pila_primitiva.cpp y 36-38 del archivo main.cpp. Los detalles a resaltar son los siguientes:

1. En el ejemplo pila_primitiva se utiliza una clase únicamente como tipo de dato para lanzar una excepción.
2. La cláusula throw acepta un parámetro y en principio puede ser cualquiera de los tipos de C++, incluyendo primitivos como int, por lo que en este sentido, es posible lanzar como excepciones enteros y objetos de cualquier tipo, y las clases definen objetos.
3. La excepción lanzada empatará con el manejador de excepción (expresiones catch) que coincida con el tipo correspondiente de la excepción.
4. Se pueden utilizar puntos suspensivos (...) como parámetro de un catch para atrapar cualquier tipo de excepción sin importar el tipo; es decir, funciona como un comodín de excepciones.
5. En el ejemplo pila_primitiva2 se ha utilizado una excepción estándar (exception) y se ha derivado una clase de ella (excepcion_ED_vacia). exception es una clase base específicamente diseñada para declarar objetos que puedan ser lanzados como excepción. Dicha clase tiene una función miembro virtual llamada what que regresa una secuencia de caracteres. Esta función puede ser sobre escrita (override) en clases derivadas (eso significar ser virtual) para proporcionar algún tipo de descripción o detalle de la excepción.
6. El manejador de esta excepción (línea 36 del archivo main.cpp) atrapa objetos de excepción por referencia (note el ampersand (&) después del tipo), por lo que atrapará también clases derivadas de exception (como excepcion_ED_vacia).
   

    Asegúrese de comprender las diferencias y similitudes de ambos ejemplos.

Pila genérica.

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

 

    Desde el punto de vista del compilador las plantillas (templates) no son funciones ni clases normales ya que se compilan sobre demanda, lo cual significa que el código de una función o clase que utiliza una plantilla no es compilado sino hasta que exista una instanciación específica. En este sentido, no es sino hasta la instanciación el momento en que el compilador genera una función o clase específica para los argumentos definidos en la plantilla. Por esta razón, la implementación con plantillas no puede estar en archivos separados como se ha hecho en el ejemplo anterior en el que la interfaz (archivo .h) estaba separada de la definición (archivo .cpp).

   Como primer paso, es preciso que el lector se tome el tiempo que considere necesario para comparar la clase Nodo_p descrita en la sección anterior, con la clase Nodo (líneas 17-29) del Ejemplo pila_genérica. Es preciso notar que, aunque distintos, ambos ejemplos son esencialmente equivalentes.

 

    La primera diferencia que salta a la vista, además del nombre de la clase, es el prefijo template <class T>. Esta es la notación que utiliza C++ para declarar elementos genéricos con base en una plantilla y hace de T un parámetro de la declaración a la que sirve de prefijo. Una clase que contiene una colección de elementos de algún tipo se denomina habitualmente clase contenedor o simplemente contenedor.

 

   La línea 19 del ejemplo en turno declara que la clase o tipo  del atributo dato es T, es decir un parámetro de plantilla, o por decirlo de manera que se ajuste más a nuestros fines: un genérico. El atributo siguiente por otro lado y en este mismo sentido, es entonces una referencia a un objeto (nodo) que almacena objetos genéricos.

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

   Ahora bien, las consideraciones hechas para la clase Nodo respecto a los genéricos, son las mismas que se deben tomar en cuenta para la clase pila_generica (líneas 33-44), por lo que una vez más se pide encarecidamente al lector que compare esta clase con la clase del Ejemplo pila_primitiva discutido en la sección anterior, tomando en consideración lo explicado hasta este momento para los genéricos.

   Observe que en ninguna parte de la clase pila_generica se hace explícita una clase o tipo específico para el genérico T, por lo que también aquí se hace una gestión de genéricos con base en una plantilla en directa y estrecha relación con las plantillas y los genéricos explicados para la clase Nodo.

 

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

   Finalmente, la función main (líneas 164-190) muestra la prueba para la pila genérica. La línea más importante es la línea 166, ya que es en ella en donde finalmente se define la clase de objetos que contendrá (almacenará) la pila: string. En este ejemplo se ha sustituido "\n" por endl porque en general es más conveniente y el resultado es el mismo (líneas 174, 182 y 186) y se deja como ejercicio para el lector probar el mismo ejemplo con enteros primitivos int.

 

    La inserción de elementos en una pila genérica (líneas 169-173) se vería como se muestra a continuación

La Pila genérica es: 0
La Pila genérica es: 1 0
La Pila genérica es: 2 1 0
La Pila genérica es: 3 2 1 0
La Pila genérica es: 4 3 2 1 0
La Pila genérica es: 5 4 3 2 1 0
La Pila genérica es: 6 5 4 3 2 1 0
La Pila genérica es: 7 6 5 4 3 2 1 0
La Pila genérica es: 8 7 6 5 4 3 2 1 0
La Pila genérica es: 9 8 7 6 5 4 3 2 1 0

 

   Por otro lado, la salida correspondiente a la eliminación de elementos de la pila genérica, se muestra a continuación (líneas 176-187):

 

Elemento eliminado de la pila: 9
La Pila genérica es: 8 7 6 5 4 3 2 1 0
Elemento eliminado de la pila: 8
La Pila genérica es: 7 6 5 4 3 2 1 0
Elemento eliminado de la pila: 7
La Pila genérica es: 6 5 4 3 2 1 0
Elemento eliminado de la pila: 6
La Pila genérica es: 5 4 3 2 1 0
Elemento eliminado de la pila: 5
La Pila genérica es: 4 3 2 1 0
Elemento eliminado de la pila: 4
La Pila genérica es: 3 2 1 0
Elemento eliminado de la pila: 3
La Pila genérica es: 2 1 0
Elemento eliminado de la pila: 2
La Pila genérica es: 1 0
Elemento eliminado de la pila: 1
La Pila genérica es: 0
Elemento eliminado de la pila: 0
Vacia: Pila genérica
terminate called after throwing an instance of 'excepcion_ED_vacia'
  what():  Estructura de datos vacía
Abortado

    Ahora bien, el Ejemplo pila_generica2 muestra una característica adicional importante, que es preciso tomar en cuenta, y que se utilizará también en implementaciones posteriores de estructuras de datos: el uso de los destructores. Un constructor será llamado siempre que se cree un objeto de una clase, y habitualmente considera también la inicialización adecuada del estado del objeto. Por otro lado, si se necesita realizar alguna acción de limpieza cuando un objeto de una clase sale fuera de su ámbito (y en consecuencia se destruirá o eliminará), se puede (y en general se debe) declarar un complemento del constructor denominado destructor (líneas 40 y 109-120) que se encargue de esa labor. Note que para este ejemplo se han insertado un cierto número de elementos en la pila (líneas 183-186) pero no han sido explícitamente eliminados de la estructura de datos, por lo que el destructor se encarga de hacerlo. Asegúrese de entender esto antes de continuar.

 

    Consulte la sección Plantillas (Templates) de la entrada Ejemplos selectos de transición para ampliar un poco más la información y los detalles acerca de las plantillas en C++. Así mismo y como ejemplo adicional, se proporciona también al lector una implementación alternativa de una pila genérica utilizando el contenedor vector. Espero que el lector tenga a bien llevar a cabo su análisis y comprensión correspondiente.

 

    Adicional y finalmente, asegúrese de comprobar que la salida de los Ejemplos de pila_genérica en sus dos versiones se corresponden, en esencia, con lo realizado por el Ejemplo pila_primitiva descrito al inicio de este tema.