Pilas (implementación).

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

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

 Pila primitiva.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Pila genérica.

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

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

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

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

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

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

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

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

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

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

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