Estructuras de datos Lineales/ Pilas

Hermes Mosquera  ( Noviembre de 2013)

PILAS

A nivel lógico las pilas son definidas como un tipo de estructuras de datos lineal condicionadas, compuestas de elementos del mismo tipo donde las inserciones y eliminaciones se realizan por un mismo extremo, el extremo superior de la pila, que también se le conoce como Cima o Tope.  Se considera como un grupo ordenado de elementos clasificados de acuerdo al tiempo en que han sido insertados o almacenados en la pila, el elemento que se elimina de la cabeza es siempre el que lleve menos tiempo en ella. En resumen una pila es una lista en la cual los elementos solo pueden ser insertados y eliminados por un único extremo. De tal manera que el último elemento en entrar es el primero en salir,  las pilas son conocidas como listas LIFO por el acrónimo en inglés (Last Input, First Out).

Mientras que a nivel físico, las pilas pueden ser representadas gráficamente con numerosas analogías en la vida real, por ejemplo: pila de platos, una pila de monedas, una pila de discos, etc. Como se muestra en la imagen siguiente.

 

Imagen 1. Pilas de discos

Operaciones a realizar con pilas

 

Se listan las operaciones básicas que se pueden realizar con la implementación de las pilas:

• Insertar un elemento a la pila.
• Visualizar los elementos de la pila
• Eliminar elementos de la pila
• Buscar elementos de la pila.

La representación en memoria  de las estructuras de datos tipo pilas para efectos de su implementación se puede  lleva a cabo haciendo uso de apuntadores con listas enlazadas  y también por medio de arreglos unidimensionales.

En la siguiente imagen se visualiza gráficamente la entrada y salida de elementos de una pila.

 

Imagen 2. Entrada y salida de elementos de una pila

Implementación de una estructura de datos tipo Pila

Para facilitar la manipulación de los datos  de  una estructura de datos tipo pila, es conveniente implementar un menú de opciones que se encargará de invocar a cada una de las funciones que realizan las operaciones que se realizan con pilas, es decir una función para insertar elementos, otra función para visualizar los elementos insertados en la pila, otra para extraer o eliminar elementos, y la función para buscar elementos existentes en la pila. Es importante comprobar antes de realizar cualquier operación si la pila está vacía; esto es, si el puntero es igual a NULL, if (puntero==NULL).

Lo primeo que hacemos es definir la estructura, teniendo en cuenta la información que se va almacenar en ella, Veamos un modelo o prototipo de estructura para gestionar una pila de elementos de tipo entero.

 La estructura se llama pila, que alberga dos miembros, uno de tipo entero llamado dato y otro que es un apuntador del mismo tipo de la estructura que hemos nombrado como  *sig,  o siguiente, utilizado como enlace o liga a cada nodo de la pila.

En el prototipo  de la estructura también se incluyen dos apuntadores del mismo tipo de estructura los cuales hacen las veces de instancias de la estructura, ellos son: *inicio y *final.

 

 

 

Imagen 3. Prototipo de funciones y la estructura pila

Implementación paso a paso de una Pila.

Después de haber realizado la lectura detallada y analizado la aplicabilidad que se le puede dar a las pilas, se realiza el análisis del planteamiento del problema,  este análisis nos permite identificar la información que se gestionará en la pila para lo cual se hace uso de la estructura,  para este caso se hará la implementación de una pila para el manejo de números enteros ingresados en tiempo  de ejecución, para lo cual se hará uso de un menú de opciones y tres funciones básicas para insertar visualizar y extraer datos de la pila.

Manos a la obra.

Se inicia abriendo un documento nuevo en el editor de C++ de su preferencia,  para este caso utilizo el IDE Falcon C++,  ya teniendo claro el planteamiento y los datos a gestionar solo resta iniciar con la edición del código fuente,  lo primero es incluir las librerías o los archivos de cabecera, estas son básicas por ser las más usadas, así como también la definición de estructura que le llamaremos pila; y los prototipos de las tres funciones (insertar, visualizar y extraer), seguimos con la función principal que contiene el menú de opciones y la definición de las tres funciones (insertar, visualizar y extraer) que por ahora y para efectos de probar el código solo muestran un mensaje de la función que cumplen.

  Imagen 4. Definición de la estructura pila

 

 

 Imagen 5. definición de la función principal main()

Para efectos de probar el menú de opciones, se definen de las tres funciones (insertar, visualizar y extraer) que por ahora  cada una, solo muestran un mensaje de la función que cumplen.

 

 

 

 

 

 

 

 

 

Imagen 6. Definición provisional de las tres funciones

Si ha seguido las instrucciones ya puede guardar el archivo con el nombre que quiera y la extención .cpp, para el ejemplo lo renombramos cono  pila.cpp.   procedemos a compilarlo, si todo está bien  no hay errores de sintaxis podemos ver la salida en pantalla así:

 

 

 

 

 

 

Imagen 7. Salida en pantalla prueba del menú de opciones

Continuamos entonces con la definición de cada una de las funciones (Insertar, visualizar y extraer).

Definición de la función Insertar.

Esta función permite ingresar los elementos a la pila, uno a uno como respuesta a elegir la opción insertar del menú de opciones, recuerde quitar la instrucción  cout <<«inserta»;   que se definió en esta función para efectos de probar el menú de opciones.

 Imagen 8. Definición de la función Insertar

Explicamos cada una de las lineas del código de esta función.

La función insertar carece de parámetros y no retorna ningún valor, en la linea 52 está la instrucción para la reserva de memoria dinámica  al apuntador inicio través del operador new  el cual retorna un dato de tipo pila.

La instrucción 53  hace una limpieza de pantalla; la linea 54 pide al usuario ingresar un dato  a la pila de tipo entero;  en la linea 55 se lee en memoria el dato ingresado por el usuario, en la linea 56 con el condicional if  se verifica si no hay elementos en la pila,  es decir si el apuntador final es igual a Null se inicializa con el contenido del apuntador final, es decir que inicio y  final tienen la misma información y como tal apuntan al mismo sitio.    En la linea 59 se hace que inicio apunte al siguiente nodo y este se inicializa a NULL o vacío, es decir que se crea el siguiente nodo pero en ese momento está vacío.  En caso que final sea diferente de NULL, es decir, que el apuntador final tenga información,  lo que hay en el apuntador final se le pasa a  inicio->siguiente, es decir al nuevo nodo que se creó. esto lo indica la linea 63 y finalmente en la linea 64 se hace una re asignación de punteros donde el apuntador final apunta a donde apunta inicio.

Ahora necesitamos probar el código y saber si efectivamente se insertan los números en la pila, para ello se requiere implementar la función visualizar.

Definición de la función Visualizar.

Al igual que en la función insertar,  Esta función permite visualizar los elementos ingresados a la pila, como respuesta a elegir la opción visualizar del menú de opciones, recuerde quitar la instrucción  cout <<«visualiza»;   que se definió temporalmente en esta función para efectos de probar el menú de opciones.

 

  Imagen 9. Definición de la unción visualizar

Expliquemos en detalle cada linea de código de esta función.

La función insertar al igual que la anterior carece de parámetros y no retorna ningún valor, recordemos que el apuntador final es el utilizado para la reserva de memoria y es el que almacena la información de la pila. En la linea 71 se hace la comprobación si hay datos en la pila, en caso que no los haya saca un mensaje en pantalla indicando que no hay elementos en la pila , esto ocurre en la linea 74 después de haber hecho una limpieza de pantalla. En caso contrario, es decir, que haya elementos en la pila  se limpia pantalla con la instrucción de la linea 78, y se muestra un mensaje como título de los elementos insertados en la pila; en la linea 80  se igualan los apuntadores final e inicio, inicio apunta donde apunta final. En la linea 81 a través del ciclo condicional While() se   muestra en pantalla los números que se hayan insertado en la pila, y este proceso se repite hasta que inicio apunte a  NULL, es decir que no haya más elementos en la pila, tal como lo indica  la instrucción de la linea 84 que hace que el apuntador inicio recorra toda la pila.

Si ha seguido las instrucciones paso a paso y todo va bien ya puede hacer una prueba del código insertando datos y mostrandolos en pantalla a través de la función visualizar, veamos que nos muestra.

Imagen 10. Salida en pantalla del opción visualizar

 

Definición de la función Extraer.

 

Finalmente tenemos la definición de la función extraer o eliminar que al igual que las funciones anteriores no retorna ningún valor y tampoco tiene parámetros.

 

 

 

 

 

 

 

 

 

 

 

Imagen 11. Definición de la función extraer

De la linea 93 a la 97  se hace la comprobación si hay o no elementos en la pila y en caso que no haya, se muestra un mensaje en pantalla,  en caso que la pila tenga elementos  se igualan los dos punteros para que inicio apunte a donde apunta final, que para este caso es al tope de la pila.  En la linea 104  se muestra el ultimo elemento ingresado a la pila, es decir el que está en el tope; en la linea 106 el apuntador final avanza una posición hacia el siguiente nodo y en la linea 107 se hace la liberación de la memoria y por ende el dato donde apunta inicio que es el tope de la pila.

Finalizamos mostrando en pantalla la salida de la opción eliminar que indica que el elemento a eliminar es el 8 que fue el ultimo dato ingresado a la pila.

 

 

 

 

 

 

Imagen 12. Salida en pantalla  de la función extraer