Pila o stack dinámica en el lenguaje C

Una pila es una estructura de datos simple. Los datos se van apilando uno tras otro. Podemos abstraer cada elemento como un nodo que puede apuntar a otro nodo.

Su modo de acceso es LIFO: el último en entrar es el primero en salir. Las operaciones que tiene son 2: push y pop; la primera le pone un elemento y la segunda quita el último.

Pila dinámica en C

Pila dinámica en C

Veremos las operaciones básicas de una pila o stack en C; además de otras que hice para exponer aquí. Son:

  • Tamaño: devolver el tamaño de la pila
  • Apilar, también conocido como push: agregar un elemento
  • Desapilar, o la operación pop: quitar el último elemento; es decir, el elemento superior
  • Leer último: leer el elemento superior de la pila
  • Vacía: indica si la pila está vacía
  • Imprimir: recorrer la pila e imprimir sus valores

Por cierto, esta pila será dinámica: podremos poner elementos infinitos siempre y cuando nuestra memoria RAM alcance (cosa que es muy, muy difícil que ocurra)

Lecturas recomendadas

  1. Booleanos en C
  2. Funciones en C
  3. Búsqueda binaria en arreglos de cadenas en C
  4. Más tutoriales de este lenguaje de programación

Ahora sí vamos a ver cómo implementar una stack dinámica en C; paso por paso y operación por operación.

1.- El nodo

Esto es de lo que estará compuesta nuestra pila, para ello usaremos una lista ligada en donde un nodo apunta a otro y este otro a otro (opcionalmente), así infinitamente.

Claro que el elemento siguiente de un nodo es opcional; porque el elemento de hasta abajo no apunta a nadie.

También tiene un número, que es el dato en sí que guardaremos en la pila. Si quisiéramos que nuestra pila fuera de strings entonces comenzaríamos cambiando el tipo de dato de int a char[].

2.- El elemento superior

En el inicio de todos los tiempos, debe haber un elemento superior aunque no tenga valor y no apunte a nada. Es decir, aunque la pila esté vacía debemos tener un elemento que será el inicio de todo:

3.- Agregar elementos a la pila: push

Veamos la operación push, que agrega un elemento a la pila.

El nodo superior es una variable global, por eso no necesitamos recibirla en la función.

Lo que hacemos es alojar espacio en memoria para almacenar nuestro nuevo elemento usado memory allocate o malloc, como decidió bautizar esta función el gran Dennis.

A ese nuevo nodo le ponemos el dato que llevará (el entero), y como es el que estará hasta arriba entonces hacemos que apunte hacia el que era el superior; y este nuevo ahora tomará su lugar.

Explicado en otras palabras, este nuevo nodo será el superior y apuntará al que antes era el superior; se está poniendo encima de él.

La próxima vez que apilemos, se creará otro nuevo y este dejará de ser el superior para pasar a ser el siguiente del nuevo; y así sucesivamente.

4.- Eliminar el último elemento (operación pop)

Esto es fácil pero interesante a la vez. Como vamos a desapilar el elemento, necesitamos hacer que el elemento superior ahora sea al que apuntaba; es decir, su siguiente.

Pero eso no es todo, debemos liberar la memoria que se estaba usando y para ello respaldamos lo que ocupaba el que vamos a eliminar dentro de temporal y llamamos a free.

Esto sólo ocurre en caso de que superior no sea nulo.

5.- Imprimir pila

Imprimir la pila no es una operación necesaria, pero como este es un ejercicio sí lo haremos. Únicamente recorremos toda la pila mientras haya un apuntador a siguiente:

Para esto necesitamos un nodo temporal y comenzamos recorriendo desde superior. Asignamos a temporal lo que esté apuntando a siguiente; si ya no apunta a nada entonces temporal será nulo y se terminará el ciclo.

6.- Tamaño de pila o stack en C

Esto es muy parecido al de imprimir; pero en lugar de imprimir vamos aumentando un contador dentro del ciclo:

Comprobamos si superior es nulo y en caso de que sí ya no hacemos el ciclo, pues la pila está vacía.

7.- Método para saber si la pila está vacía

Siendo perezosos podríamos decir que, si ya tenemos el método tamanio, podríamos regresar un booleano resultante de la comparación de tamanio == 0 pero eso sería un desperdicio de recursos

Ya que si la pila tiene 0 elementos todo va bien, pero, ¿qué tal si la pila tiene 100000 elementos? tendríamos que recorrer todos dentro de tamanio para determinar al final que la pila no está vacía.

Es por eso que mejor usamos otra lógica… si el elemento superior no apunta a nada, entonces no hay más elementos y por lo tanto la pila está vacía.

8.- Operación top o peek de la pila: último elemento

Esto es fácil, se lee el último elemento de la pila y en este caso es un entero.

Si superior es nulo, devolvemos -1 (no supe qué otra cosa poner).

En caso de que no, entonces devolvemos lo que tenga el elemento superior.

Poniendo todo junto

Todo esto no tendría sentido si no estuviera implementado en un código completo, preciso, limpio, bien comentado y con ejemplos de uso.

Así que para poner todo junto dejaremos que el usuario juegue con nuestra pila:

Con eso le damos al usuario la posibilidad de que elija qué hacer con la pila. El código completo lo dejo en un gist:

Igualmente lo he puesto en un replit para que puedas probar directamente en el navegador:


Estoy disponible para trabajar en tu proyecto o realizar tu tarea pendiente, no dudes en ponerte en contacto conmigo.
Si el post fue de tu agrado muestra tu apoyo compartiéndolo, suscribiéndote al blog, siguiéndome o realizando una donación.

Suscribir por correo

Ingresa tu correo y recibirás mis últimas entradas sobre programación, open source, bases de datos y todo lo relacionado con informática

Únete a otros 2,867 suscriptores


parzibyte

Programador freelancer listo para trabajar contigo. Aplicaciones web, móviles y de escritorio. PHP, Java, Go, Python, JavaScript, Kotlin y más :) https://parzibyte.me/blog/software-creado-por-parzibyte/

5 Comentarios

Gastón Rosales · noviembre 16, 2020 a las 10:09 am

Baje tu codigo pero no funciona. Da un error de invalid conversion from `void*’ to `nodo*’

    parzibyte · noviembre 16, 2020 a las 10:18 am

    Se me hace extraño, pues a mí me compila perfectamente (y en repl.it también funciona). Puede que sea su compilador o la versión de C a la que está compilando
    Saludos 🙂

Sebastian · febrero 3, 2020 a las 2:31 pm

Muchísimas gracias! Estoy practicando para hacer una lista de tareas que reciba un controlador por el puerto serie. Estaba intentando que las funciones de push y pop reciban un puntero a la pila para no tener que estar usando una variable global (y poder usar las mismas funciones con distintas pilas), y no lo estoy pudiendo hacer.

    Sebastian · febrero 3, 2020 a las 5:07 pm

    Ya lo solucione, a las funciones debían recibir un puntero a puntero como parametro.

Contar frecuencia de palabras en C - Parzibyte's blog · noviembre 13, 2018 a las 10:47 am

[…] de varias maneras pero yo he decidido hacerlo a través de una pila en donde almacenaremos structs. Aquí puedes ver un ejemplo de una pila de enteros, la modificaremos un poco para que funcione con […]

Deja un comentario

Marcador de posición del avatar

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

A %d blogueros les gusta esto: