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.
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)
Nota: esto será un tipo de lista ligada, así como la cola.
Lecturas recomendadas
- Booleanos en C
- Funciones en C
- Búsqueda binaria en arreglos de cadenas en C
- 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:
Baje tu codigo pero no funciona. Da un error de invalid conversion from `void*’ to `nodo*’
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 🙂
Ya se cual es el error ya que a mi me pasaba lo mismo, al parecer si lo corres como c++ que da un error en el struct nodo *nuevoNodo=malloc(sizeof(struct nodo));
La cual dice que no se puede utilizar un tipo void en un struc
Asi que decidi cree otro proyecto en el dev c++ pero esta vez como c y no me dio nungun error
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.
Ya lo solucione, a las funciones debían recibir un puntero a puntero como parametro.
Pingback: Contar frecuencia de palabras en C - Parzibyte's blog