La Pila
Una de las estructuras de datos dinámicas más utilizadas es la Pila (stack), esta estructura de datos es del tipo Last In First Out (LIFO: Último que entra, primero que sale).
En este corto tutorial intentaré explicarles varios conceptos: Asignación de Memoria Dinámica, Relación entre Arreglos y Punteros, Estructuras y Listas Anidadas. Así que espero que esten familiarizados aunque sea un poco con estos conceptos.
Al final tendremos una implementación bastante sencilla de una Pila que puede ser utilizada o adaptada para almacenar diferentes tipos de datos.
Decidí escribir este pequeño tutorial en C ya que en lenguajes de más alto nivel aunque es más fácil entender la parte abstracta muchas veces no queda claro que es lo que sucede "tras bambalinas" al momento de asignar y utilizar la memoria en la computadora. (Además que casi no hay POSTS en C/C++)
Una vez dicho esto: ¡¡Comencemos!!
La memoria dinámica
Cuando comenzamos a programar en C, se nos enseña a utilizar diferentes tipos de datos según la información que vamos a guardar en nuestro programa. Cuando queremos guardar conjuntos de datos nos enseñan a utilizar los arreglos. Los arreglos nos permiten guardar en memoria un conjunto de datos del mismo tipo.
El problema de los arreglos es que son estáticos, es decir, una vez hemos declarado su tamaño no podemos modificarlo, al menos no sin correr el riesgo de generar un error de acceso en la memoria.
Para solventar este problema existen en las librerías estándar de C dos funciones sumamente útiles, estas son malloc y free.
"malloc" se encarga de reservar un espacio de memoria del tamaño en bytes que le especifiquemos.
"free" por el contrario se encarga de liberar la memoria que hemos asignado haciendo uso de malloc.
Por ejemplo, si quisieramos reservar espacio en memoria para un arreglo 4 bytes podríamos hacer lo siguiente:
#include <stdlib.h>
#include <stdio.h>
int main(int argc, char *argv[]) {
// Inicializamos el arreglo
int *array_int = (int*)malloc(sizeof(int)*4);
array_int[0] = 1;
array_int[1] = 2;
array_int[2] = 3;
array_int[3] = 4;
printf("Pos 0: %i\n",array_int[0]);
printf("Pos 1: %i\n",array_int[1]);
printf("Pos 2: %i\n",array_int[2]);
printf("Pos 3: %i\n",array_int[3]);
// Liberamos el arreglo
free(array_int);
return 0;
}
Output:
[root@localhost sf_Development]# ./array
Pos 0: 1
Pos 1: 2
Pos 2: 3
Pos 3: 4
Pro tip: sizeof es una función del lenguaje C que nos permite saber el tamaño en Bytes de un tipo de dato especifico.
Justo en este punto es donde las cosas se ponen interesantes: ¿Cómo es que declaré un puntero y lo accedo luego como un arreglo?
La respuesta es simple: los arreglos son en realidad "punteros disfrazados", la notación de los arreglos nos permite acceder a las direcciones de memoria del puntero sin tener que estar calculando las direcciones de memoria para cada uno de los elementos.
¿Como tendríamos que acceder a cada uno de los items si no existiera la notación del arreglo?
Pues deberíamos hacerlo de la siguiente manera:
#include <stdlib.h>
#include <stdio.h>
int main(int argc, char *argv[]) {
int *array_int = malloc(sizeof(int)*4);
*(array_int) = 1;
*(array_int+1) = 2;
*(array_int+2) = 3;
*(array_int+3) = 4;
int *int_ptr = array_int; // Primera direccion en memoria
printf("Pos 0: %i\n",*int_ptr);
int_ptr = array_int + 1; // segunda direccion en memoria
printf("Pos 1: %i\n",*int_ptr);
int_ptr = array_int + 2; // tercera direccion en memoria
printf("Pos 2: %i\n",*int_ptr);
int_ptr = array_int + 3; // cuarta direccion en memoria
printf("Pos 3: %i\n",*int_ptr);
free(array_int);
return 0;
}
Output:
[root@localhost sf_Development]# ./array
Pos 0: 1
Pos 1: 2
Pos 2: 3
Pos 3: 4
Nótese como utilizamos el "*" para acceder al contenido del puntero. Ojo con el uso de free, cuando declaramos las variables el compilador se encarga de agregar el código para liberar la memoria de las variables declaradas, sin embargo cuando utilizamos punteros y "malloc" DEBEMOS de utilizar siempre "free" ya que en este caso el compilador no generará el código para liberar la memoria. Muchos de los "memory leaks" son generados por algún programador descuidado que olvidó utilizar algún "free".
Las Estructuras
C es un lenguaje de "bajo nivel", esto significa que nos permite interactuar directamente con la memoria. Una de las características más interesantes y que precede al "concepto" de las "clases" en la POO son las famosas "estructuras".
Una estructura es un tipo especial de datos en C, que nos permite agrupar diferentes tipos de datos diferentes en un solo elemento.
Las estructuras se utilizan generalmente cuando queremos guardar datos asociados de diferente tipo. Un ejemplo práctico es cuando queremos definir una cordenada en el plano (x,y):
struct Coordenada {
int x;
int y;
}
Si quisieramos crear una coordenada podríamos hacerlo de la siguiente manera:
struct Coordenada primera;
primera.x = 4;
primera.y = 4;
O bien de una manera más abreviada:
struct Coordenada primera = {4,4};
Podemos crear estructuras de manera dinámica con malloc, en este caso el código sería similar al siguiente:
#include <stdlib.h>
struct Coordenada {
int x;
int y;
};
int main(int argc,char *argv[]) {
struct Coordenada* primera = (struct Coordenada*)malloc(sizeof(struct Coordenada));
primera->x = 4;
primera->y = 4;
free(primera);
return 0;
}
Pueden observar como utilizamos "->" en vez de "." para acceder a los datos de la estructura en puntero.
Las Listas
Una lista es una estructura dinámica de datos que nos permite almacenar una cantidad indefinida de datos, cada uno de los elementos de la lista se une al siguiente como en una pequeña cadena.
Una forma más sencilla de entender las listas es imaginarlas como "cadenas", donde cada dato es un eslabón dentro de la misma.
Podemos clasificar las cadenas en base como estan anidados sus eslabones entre sí, la forma en que estén anidados los eslabones determinará como la lista puede ser recorrida.
Una lista con anidación sencilla es la que cada item (o eslabón) tiene un puntero al siguiente item:
[dato 1]->[dato 2]->[dato 3]->[dato 4]
Una lista doblemente anidada es la que cada item tiene un puntero hacia el item siguiente, pero también tiene un puntero al item anterior:
[dato 1]<->[dato 2]<->[dato 3]<->[dato 4]
Pueden observar como en una lista simplemente anidada solo podemos recorrer los datos en una sola dirección, en cambio en una lista doblemente anidada podemos recorrer la lista en cualquier dirección.
El eslabón de la cadena
Vamos a hacer uso de una estructura que va a representar el eslabón de nuestra cadena, para nuestro caso vamos a hacer una lista doblemente anidada ya que posiblemente luego querramos recorrer la lista en cualquier dirección.
struct Item {
struct Item *prevPtr;
int data;
struct Item *nextPtr;
};
La Pila
Una pila es uno de las estructuras dinámicas más sencillas de realizar, en una pila el objetivo es ir agregando items al principio de la lista.
Este tipo de estructura es llamada usualmente una cola LIFO (de las siglas en ingles Last In, First Out en español último que entra, primero que sale).
Si fueran programadores encargados del desarrollo de Magic, utilizarían una cola LIFO para guardar su deck.
Usualmente a la función que agrega los items se le denomina "push" (de empujar).
La lógica de nuestra función push será la siguiente:
1-Vamos a revisar si se existe el primer eslabón
2-Si existe el primer eslabón lo creamos y definimos como NULL los punteros del eslabón.
3-Si ya existe el primer eslabón, entonces creamos un nuevo eslabón y asociamos los punteros.
En C y con la estructura de datos definida previamente, esto sería algo como lo siguiente:
struct Item* push(int data,struct Item* vector) {
if(vector==NULL) { // Si no hay item definido
vector = (struct Item*)malloc(sizeof(struct Item));
vector->prevPtr = NULL;
vector->data = data;
vector->nextPtr = NULL;
} else {
// Creamos un nuevo eslabon al principio de la cadena
vector->prevPtr = (struct Item*)malloc(sizeof(struct Item));
// Establecemos el eslabon previo a NULL (no hay items antes)
vector->prevPtr->prevPtr = NULL;
// Asignamos el dato
vector->prevPtr->data = data;
// El puntero siguiente del nuevo eslabón es el eslabón actual
vector->prevPtr->nextPtr = vector;
// empujamos el principio de la lista hacia el nuevo item
vector = vector->prevPtr;
}
return vector;
}
¿Cómo utilizamos esta nueva lista? La idea era hacerlo lo más simple posible, así que la función trabaja de la siguiente manera:
1-Si el argumento "vector" es NULL creará una nueva lista y nos devolvera el primer puntero de la misma.
2-Si el argumento "vector" es un puntero, esta función asumirá que este es el primer elemento de la pila, y agregará items antes de este.
OJO: Ustedes pueden pasar como argumento CUALQUIER item de la lista, obviamente si pasan un elemento intermedio está función no determinará si el eslabón está al inicio de la lista.
Ejercicio: Modifiquen la función PUSH para que al recibir cualquier puntero, se desplace automáticamente al inicio de la lista.
Agregar items a nuestra lista es relativamente fácil, en C sería algo como lo siguiente:
include <stdio.h>
#include <stdlib.h>
struct Item {
struct Item *prevPtr;
int data;
struct Item *nextPtr;
};
struct Item* push(int data,struct Item* vector) {
if(vector==NULL) {
vector = (struct Item*)malloc(sizeof(struct Item));
vector->prevPtr = NULL;
vector->data = data;
vector->nextPtr = NULL;
} else {
vector->prevPtr = (struct Item*)malloc(sizeof(struct Item));
vector->prevPtr->prevPtr = NULL;
vector->prevPtr->data = data;
vector->prevPtr->nextPtr = vector;
vector = vector->prevPtr;
}
return vector;
}
int main(int argc,char *argv[]) {
printf("Hello World! ;)\n");
struct Item* vector;
vector = push(1,NULL); // Inicializa la pila
vector = push(2,vector);
vector = push(3,vector);
vector = push(4,vector);
return 0;
}
Hasta ahora todo parece ir de color de rosa, pero hay un pequeño problema ¿Como hacemos para sacar los datos de nuestra pila?
Usualmente utilizamos una función denominada "POP" o quitar, esta función simplemente extrae el primer eslabón de la cadena, devuelve el dato y elimina el eslabón.
Nuestra función pop sería similar a la siguiente:
struct Item* pop(int *data,struct Item* vector) {
if(vector==NULL) {
return NULL;
} else {
*data = vector->data;
if(vector->nextPtr!=NULL) {
vector->nextPtr->prevPtr = NULL;
}
struct Item* nextPtr = vector->nextPtr;
free(vector);
return nextPtr;
}
}
Esta función trabaja de la siguiente manera:
1-Si el item enviado es NULL no se hace nada.
2-Si el item enviado no es NULL, extrae el dato y lo asigna al puntero "data".
3-Si existe el siguiente eslabón entonces elimina la referencia al eslabón actual.
4-Guarda la referencia al siguiente eslabón
5-Libera la memoria del eslabón actual
6-Devuelve la referencia al siguiente eslabón.
¿Cómo lo utilizamos?
Esta función devolverá NULL cuando el la lista ya no tenga más items por recorrer, por lo que un do-while nos será de mucha utilidad, el programa completo quedaría de la siguiente manera:
#include <stdio.h>
#include <stdlib.h>
struct Item {
struct Item *prevPtr;
int data;
struct Item *nextPtr;
};
struct Item* push(int data,struct Item* vector) {
if(vector==NULL) {
vector = (struct Item*)malloc(sizeof(struct Item));
vector->prevPtr = NULL;
vector->data = data;
vector->nextPtr = NULL;
} else {
vector->prevPtr = (struct Item*)malloc(sizeof(struct Item));
vector->prevPtr->prevPtr = NULL;
vector->prevPtr->data = data;
vector->prevPtr->nextPtr = vector;
vector = vector->prevPtr;
}
return vector;
}
struct Item* pop(int *data,struct Item* vector) {
if(vector==NULL) {
return NULL;
} else {
*data = vector->data;
if(vector->nextPtr!=NULL) {
vector->nextPtr->prevPtr = NULL;
}
struct Item* nextPtr = vector->nextPtr;
free(vector);
return nextPtr;
}
}
int main(int argc,char *argv[]) {
printf("Hello World!\n");
struct Item* vector;
vector = push(1,NULL); // Inicializa el vector
vector = push(2,vector);
vector = push(3,vector);
vector = push(4,vector);
int data;
do {
vector=pop(&data,vector);
printf("Data %i\n",data);
} while(vector!=NULL);
return 0;
}
Output:
[root@localhost sf_Development]# gcc main.c -o main
[root@localhost sf_Development]# ./main
Hello World!
Data 4
Data 3
Data 2
Data 1
Noten que la salida del programa los items salen en orden inverso, es decir, "El primero que entra, es el último que sale".
Espero este pequeño tutorial les haya gustado, muchas veces nos enseñan todos estos conceptos por separado y es muy difícil entender su utilidad de manera individual, una vez agarramos todos estos pequeños componentes y los utilizamos es donde podemos comenzar a hacer cosas interesantes.
