Pilas

Estructuras de Datos – Pilas

Josué V. Herrera Algoritmos, Tutoriales 0 Comments

En este tutorial estudiaremos el algoritmo de una pila, aprenderemos a implementar esta estructura de datos lineal que es sin dudas fundamental en nuestro aprendizaje y que luego de incorporarla se convertirá en una herramienta más a la hora de resolver esos problemas que se nos presentan cuando necesitamos modelar nuestros datos.

Las Pilas describen una estructura LIFO (Last-in First-out), el último elemento en añadir es el primero en salir, son como arreglos pero con funcionalidades limitadas. Solamente podemos hacer push para añadir un elemento en la cima de la pila, pop para remover un elemento de la cima y peek para visualizar un elemento de la cima sin extraerlo o eliminarlo de la misma. Aunque una pila pueda lucir poco probable de usar lo cierto es que en muchas ocasiones necesitamos añadir objetos a una lista para luego volver a trabajar con ellos. En estos casos también es frecuente que el orden en el cual interactuamos con los elementos sea un aspecto importante a tener en cuenta por lo que una Pila sería una de las tantas formas en que pudiéramos gestionar nuestra lista de objetos.

Operaciones de una Pila

Como ya he comentado las Pilas cuentan con un pequeño ámbito de funcionalidades. Teniendo en cuenta una Pila compuesta por libros las acciones que esta tendría que ser capaz de ejecutar serían:

Push

Cuando añadimos un nuevo elemento en nuestra pila de libros lo hacemos sobre su parte superior:

Estructuras de Datos Pila - Push

…acción que podemos observar en el diagrama anterior.

Peek

En una pila el único elemento que podemos verificar es aquel que se encuentra en la cima de la misma, es decir el último que fue añadido:

Estructuras de Datos Pila - Peek

…tal y como se observa en la imagen anterior.

Pop

Cuando necesitamos eliminar un elemento de la pila nos vemos limitado por diseño a que este sea el último introducido, aquel que se encuentre en ese momento en la cima de la Pila:

Estructuras de Datos Pila - Pop

…sería lo mismo que remover el último ejemplar de nuestra pila de libros.

Implementando una Pila en Swift

Luego de la teoría pasemos a la práctica. Pero antes me gustaría aclarar lo siguiente: para los ejemplos a continuación nos apoyaremos en la colección Array propia del lenguaje Swift, ya que el objetivo de este artículo es aprender el algoritmo detrás de una pila, su implementación y no como crear una colección de datos desde cero, algo que sí veremos en futuros artículos.

Veamos como implementar una estructura de datos de tipo Pila en el lenguaje Swift  y para esto comenzaremos por crear un nuevo proyecto de Playground y escribir lo siguiente:

Aquí acabamos de declarar una estructura de nombre Stack con una propiedad que hemos declarado como un arreglo de tipo String y de nombre array.  Sobre este arreglo es donde ejecutaremos las acciones anteriormente vistas: push, peek y pop.

La función Push

Añadir un objeto a nuestra Pila es una operación relativamente sencilla, agreguemos el siguiente método al código anterior:

La función push toma un solo parámetro, evidentemente el elemento que añadiremos a la cima de la pila. Creo pertinente aclarar que estamos haciendo uso del método append de nuestra propiedad array el cual nos añade el nuevo elemento al final del arreglo. Si lo hubiéramos hecho al inicio aparte de violar el diseño de una Pila también estaríamos ejecutando una operación O(0) muy costosa debido al desplazamiento de elementos, mientras que al añadirlo al final sería una operación O(1) cuya duración es la misma sin importar el tamaño del arreglo.

La función Peek

Cuando necesitamos hacer un peek o echar una ojeada sobre nuestra Pila lo hacemos mediante la función peek que implementaremos a continuación:

En este código hemos eliminado el modificador mutating ya que esta función no modifica el arreglo, solamente toma el último elemento y devuelve una copia del mismo para que podamos verificarlo.

La función Pop

Eliminar el último elemento de la Pila también es una operación sencilla, veamos el código del método asociado a esta acción:

Si alguno ha tenido la duda de por qué la función pop y peek devuelven un valor String opcional pues les comento que esto es debido al caso donde la Pila esté vacía, no hay elementos en esta y por ende el valor de retorno será nil.

En este punto ya podemos integrar todo cuanto hemos implementado y pasar a probar nuestro código que es el siguiente:

…debajo de este fragmento añadiremos las líneas:

Comenzamos por crear un objeto de tipo Stack, acto seguido añadimos el primer libro mediante push, seguimos ejecutando la función peek con la intención de verificar que el primer elemento ha sido añadido en la Pila. Continuamos añadiendo otro libro y repetimos la misma acción de verificar su inclusión, en la siguiente línea removemos el último libro mediante la función pop, verificamos que ha sido eliminado, nuevamente eliminamos el primer libro introducido y verificamos por última vez recibiendo nil como resultado.

La salida en pantalla del código anterior es la siguiente:

El protocolo CustomStringConvertible

Actualmente es bastante incómodo visualizar todos los elementos que componen nuestra Pila. Así que tal y como hemos hecho en otros artículos y ejemplos, usaremos el protocolo CustomStringConvertible el cual nos permite definir como deseamos que los datos se muestren en pantalla.

Para lograr esto haremos uso de las extensiones añadiendo el código a continuación:

…ahora modificaremos las líneas de prueba de nuestra Pila por las siguientes:

…y la salida en pantalla es:

Genéricos

Actualmente tenemos un inconveniente, nuestra Pila solamente puede almacenar valores de tipo String. Si necesitamos una Pila para valores de tipo entero tendríamos que duplicar el código. Por suerte para nosotros Swift siempre nos ofrece una alternativa óptima:

En este ejemplo hemos optado por hacer uso de código genérico y puesto que ya hemos hablado sobre este tema los invito, si es que tienen dudas, a que visiten el tutorial sobre Tipos Genéricos en Swift. Luego de estos cambios pertinentes ya podemos manejar distintos tipos de datos:

En este fragmento de código hemos creado dos pilas, la antigua bookStack y una nueva de nombre integerStack. Destacamos aquí la definición del tipo de dato con el cual trabajaremos al momento de crear el objeto, mediante la sintaxis:

ObjetoGenérico<Tipo de Dato>()

Cabe también mencionar que la modificación que hemos hecho en la línea 36 que se extiende ahora hasta la 40 se debe a que en este punto el compilador desconoce el tipo de dato con el cual trabajaremos, por lo que la línea anterior le resultaría ambigua. Debido a esta razón hemos optado (mediante la función de orden superior map) por convertir los valores del arreglo en String antes de organizarlos con reversed y juntarlos mediante joined.

La salida en pantalla del código anterior es:

Toques finales

Aún hay dos propiedades que usualmente acompañan a una Pila estas vienen a solventar la frecuente necesidad de verificar si nuestra Pila se encuentra vacía y de no estarla cuantos elementos almacena:

Estas propiedades las hemos definido al inicio de la estructura y tras el arreglo, tal y como se puede observar en el fragmento de código anterior.

Espero que todo cuanto se ha dicho aquí, de una forma u otra le haya servido de aprendizaje, de referencia, que haya valido su preciado tiempo.

Este artículo, al igual que el resto, será revisado con cierta frecuencia en pos de mantener un contenido de calidad y actualizado.

Cualquier sugerencia, ya sea errores a corregir, información o ejemplos a añadir será, más que bienvenida, necesaria!