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:
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.
Ahora sí vamos a ver cómo implementar una stack dinámica en C; paso por paso y operación por operación.
// Un nodo tiene un dato, el cual es el número. Y otro nodo al que apunta
struct nodo {
int numero;
struct nodo *siguiente;
};
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[].
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:
// Todo comienza con el nodo superior
struct nodo *superior = NULL;
Veamos la operación push, que agrega un elemento a la pila.
// Operación push
void agregar(int numero) {
printf("Agregando %d\n", numero);
// El que se agregará; reservamos memoria
struct nodo *nuevoNodo = malloc(sizeof(struct nodo));
// Le ponemos el dato
nuevoNodo->numero = numero;
// Y ahora el nuevo nodo es el superior, y su siguiente
// es el que antes era superior
nuevoNodo->siguiente = superior;
superior = nuevoNodo;
}
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.
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.
// Operación pop, eliminar el de hasta arriba
void eliminarUltimo(void) {
printf("Eliminando el último\n");
if (superior != NULL) {
// Para liberar la memoria más tarde debemos
// tener la referencia al que vamos a eliminar
struct nodo *temporal = superior;
// Ahora superior es a lo que apuntaba su siguiente
superior = superior->siguiente;
// Liberar memoria que estaba ocupando el que eliminamos
free(temporal);
}
}
Esto sólo ocurre en caso de que superior no sea nulo.
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:
void imprimir(void) {
printf("Imprimiendo...\n");
struct nodo *temporal = superior;
while (temporal != NULL) {
printf("%d\n", temporal->numero);
temporal = temporal->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.
Esto es muy parecido al de imprimir; pero en lugar de imprimir vamos aumentando un contador dentro del ciclo:
int tamanio(void){
int contador = 0;
if(superior == NULL) return contador;
struct nodo *temporal = superior;
while (temporal != NULL) {
contador++;
temporal = temporal->siguiente;
}
return contador;
}
Comprobamos si superior es nulo y en caso de que sí ya no hacemos el ciclo, pues la pila está vacía.
bool vacia(void){
return superior == NULL;
}
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.
Esto es fácil, se lee el último elemento de la pila y en este caso es un entero.
int ultimo(){
if(superior == NULL) return -1;
return superior->numero;
}
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.
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:
int main() {
int eleccion;
int numero;
while(eleccion != -1){
printf("\n--BIENVENIDO--\n1.- Agregar\n2.- Eliminar\n3.- Imprimir pila\n4.- Imprimir tamaño\n5.- Comprobar si está vacía\n6.- Mostrar último elemento\n-1.- Salir\n\n\tElige: ");
scanf("%d", &eleccion);
switch(eleccion){
case 1:
printf("Ingresa el número que agregaremos:\n");
scanf("%d", &numero);
agregar(numero);
break;
case 2:
eliminarUltimo();
break;
case 3:
imprimir();
break;
case 4:
printf("La pila mide %d\n", tamanio());
break;
case 5:
if(vacia()){
printf("La pila está vacía\n");
}else{
printf("La pila NO está vacía\n");
}
break;
case 6:
printf("El último elemento es: %d\n", ultimo());
break;
}
}
}
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:
/*
Estructuras de datos en C: implementación de pila de enteros
Recuerda que el último en entrar es el primero en salir
LIFO: https://es.wikipedia.org/wiki/Last_in,_first_out
Basado en las operaciones que dice la Wikipedia:
https://es.wikipedia.org/wiki/Pila_(inform%C3%A1tica)#Operaciones
@author parzibyte
Visita: parzibyte.me
*/#include <stdio.h> // printf
#include <stdlib.h> // malloc y free
#include <stdbool.h> // Booleanos
// Un nodo tiene un dato, el cual es el número. Y otro nodo al que apunta
struct nodo {
int numero;
struct nodo *siguiente;
};
// Prototipos de funciones
void agregar(int numero); // push
void eliminarUltimo(void); // pop
void imprimir(void);
int tamanio(void); // El tamaño de la pila
bool vacia(void); // Indica si la pila está vacía
int ultimo(void); // El último elemento. Devuelve 0 si no hay elementos
// Todo comienza con el nodo superior
struct nodo *superior = NULL;
int main() {
int eleccion;
int numero;
while (eleccion != -1) {
printf("\n--BIENVENIDO--\n1.- Agregar\n2.- Eliminar\n3.- Imprimir "
"pila\n4.- Imprimir tamaño\n5.- Comprobar si está vacía\n6.- "
"Mostrar último elemento\n-1.- Salir\n\n\tElige: ");
scanf("%d", &eleccion);
switch (eleccion) {
case 1:
printf("Ingresa el número que agregaremos:\n");
scanf("%d", &numero);
agregar(numero);
break;
case 2:
eliminarUltimo();
break;
case 3:
imprimir();
break;
case 4:
printf("La pila mide %d\n", tamanio());
break;
case 5:
if (vacia()) {
printf("La pila está vacía\n");
} else {
printf("La pila NO está vacía\n");
}
break;
case 6:
printf("El último elemento es: %d\n", ultimo());
break;
}
}
}
int tamanio(void) {
int contador = 0;
if (superior == NULL)
return contador;
struct nodo *temporal = superior;
while (temporal != NULL) {
contador++;
temporal = temporal->siguiente;
}
return contador;
}
bool vacia(void) { return superior == NULL; }
int ultimo() {
if (superior == NULL)
return -1;
return superior->numero;
}
// Operación push
void agregar(int numero) {
printf("Agregando %d\n", numero);
// El que se agregará; reservamos memoria
struct nodo *nuevoNodo = malloc(sizeof(struct nodo));
// Le ponemos el dato
nuevoNodo->numero = numero;
// Y ahora el nuevo nodo es el superior, y su siguiente
// es el que antes era superior
nuevoNodo->siguiente = superior;
superior = nuevoNodo;
}
void imprimir(void) {
printf("Imprimiendo...\n");
struct nodo *temporal = superior;
while (temporal != NULL) {
printf("%d\n", temporal->numero);
temporal = temporal->siguiente;
}
}
// Operación pop, eliminar el de hasta arriba
void eliminarUltimo(void) {
printf("Eliminando el último\n");
if (superior != NULL) {
// Para liberar la memoria más tarde debemos
// tener la referencia al que vamos a eliminar
struct nodo *temporal = superior;
// Ahora superior es a lo que apuntaba su siguiente
superior = superior->siguiente;
// Liberar memoria que estaba ocupando el que eliminamos
free(temporal);
}
}
Hoy te voy a presentar un creador de credenciales que acabo de programar y que…
Ya te enseñé cómo convertir una aplicación web de Vue 3 en una PWA. Al…
En este artículo voy a documentar la arquitectura que yo utilizo al trabajar con WebAssembly…
En un artículo anterior te enseñé a crear un PWA. Al final, cualquier aplicación que…
Al usar Comlink para trabajar con los workers usando JavaScript me han aparecido algunos errores…
En este artículo te voy a enseñar cómo usar un "top level await" esperando a…
Esta web usa cookies.
Ver comentarios
Baje tu codigo pero no funciona. Da un error de invalid conversion from `void*' to `nodo*'
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
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 :)
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.