[C] (Aporte) Estructura de pila y cola con memoria dinámica

[class_OpenGL]

Hola, muy buenas. Dado un tema reciente decidí implementar en C una estructura que funcione como cola y otra como pila (estructuras FIFO y LIFO respectivamente). Bueno, parece que son muchas líneas, pero entre comentarios, y saltos de líneas "innecesarios", el código no es tan largo. Aquí se los dejo.

NOTA: Ya sé que ya se ha subido la implementación de estas estructuras, pero eso fue en C++, no en C.

Código (c) [Seleccionar] Expandir

#include <stdlib.h>
#include <stdio.h>

// Para generalizar, uso un tipo de datos predefinido, así puedo
// cambiar entre int y el tipo de datos que quiera
typedef int tipo;

typedef struct ElementoLista{
tipo dato;
struct ElementoLista *siguiente;
} Elemento;

// En la estructura de una pila, solo necesitamos la referencia al
// último elemento agregado
typedef struct {
Elemento *ultimo;
unsigned int num_elementos;
} Pila;

// Pero en la estructura de una cola, también necesitaremos la
// referencia del primer elemento
typedef struct {
Elemento *primero;
Elemento *ultimo;
unsigned int num_elementos;
} Cola;

// Si alguna de estas dos funciones retorna 0, significa que
// ha ocurrido un error, de lo contrario, retornará un valor
// diferente de 0
int agregar_a_pila(Pila *pila, tipo dato);
int agregar_a_cola(Cola *cola, tipo dato);

// Destruye el último elemento y retorna los datos almacenados en el
tipo quitar_a_pila(Pila *pila);
tipo quitar_a_cola(Cola *cola);

// Para demostrar el uso de 'quitar_a_pila' y 'quitar_a_cola'
// estas funciones destruyen la pila y la cola respectivamente
// al mostrarlas
void mostrar_pila(Pila *pila);
void mostrar_cola(Cola *cola);

int main() {
// No hay que olvidarse de inicializar, porque si no,
// no hay manera de determinar si un puntero a memoria
// dinámica es válido o no...
Pila pila = {NULL, 0};
Cola cola = {NULL, NULL, 0};
tipo dato;

// Para probar que todo funciona perfectamente, hacemos que el
// usuario introduzca enteros para almacenarlos tanto en una cola
// como en una pila.
fprintf(stdout, "Introduzca una serie de numeros (0 para acabar): ");
fscanf(stdin, "%d", &dato);
while(0 != dato) {
agregar_a_pila(&pila, dato);
agregar_a_cola(&cola, dato);
fscanf(stdin, "%d", &dato);
}

// Mostramos la pila y la cola (destruyendo a su vez los datos
// de las mismas)
mostrar_pila(&pila);
fputc('\n', stdout);
mostrar_cola(&cola);

return 0;
}

int agregar_a_pila(Pila *pila, tipo dato) {
Elemento *elemento;

// Creamos elemento y guardamos datos...
elemento = malloc(sizeof(Elemento));
if(NULL == elemento)
return 0;

elemento->dato = dato;

// Reconfiguramos pila...
if(NULL == pila->ultimo) {
elemento->siguiente = NULL;
pila->num_elementos = 1;
pila->ultimo = elemento;
} else {
elemento->siguiente = pila->ultimo;
pila->num_elementos += 1;
pila->ultimo = elemento;
}

return 1;
}

int agregar_a_cola(Cola *cola, tipo dato) {
Elemento *elemento;

// Creamos elemento y guardamos datos...
elemento = malloc(sizeof(Elemento));
if(NULL == elemento)
return 0;

elemento->dato = dato;
elemento->siguiente = NULL;

// Reconfiguramos cola...
if(NULL == cola->primero) {
cola->num_elementos = 1;
cola->primero = elemento;
cola->ultimo = elemento;
} else {
cola->ultimo->siguiente = elemento;
cola->num_elementos += 1;
cola->ultimo = elemento;
}

return 1;
}

tipo quitar_a_pila(Pila *pila) {
Elemento *temp;
tipo dato;

if(NULL != pila->ultimo) {
dato = pila->ultimo->dato;
temp = pila->ultimo;
pila->ultimo = pila->ultimo->siguiente;
pila->num_elementos -= 1;
free(temp);
} else {
dato = -1;
}

return dato;
}

tipo quitar_a_cola(Cola *cola) {
Elemento *temp;
tipo dato;

// Hacemos esta asignación, porque si el primer elemento de la cola y
// el último son iguales, destruiremos el primer elemento, dejando al último
// sin memoria asignada, por lo que directamente al último elemento le
// asignamos NULL para que no haya errores
if(cola->primero == cola->ultimo)
cola->ultimo = NULL;

if(NULL != cola->primero) {
dato = cola->primero->dato;
temp = cola->primero;
cola->primero = cola->primero->siguiente;
cola->num_elementos -= 1;
free(temp);
} else {
dato = -1;
}

return dato;
}

void mostrar_pila(Pila *pila) {
tipo dato;

while(NULL != pila->ultimo) {
dato = quitar_a_pila(pila);
fprintf(stdout, "%d ", dato);
}
}

void mostrar_cola(Cola *cola) {
tipo dato;

while(NULL != cola->primero) {
dato = quitar_a_cola(cola);
fprintf(stdout, "%d ", dato);
}
}

[AlbertoBSD]

 

Y con tipos de datos Genericos!!!

Código (c) [Seleccionar] Expandir

// cambiar entre int y el tipo de datos que quiera
typedef int tipo;

Podrían ocultar ahi una estructura incluso hasta apuntadores 

Saludo!

[class_OpenGL]

¡Claro! Podrías poner un puntero void * que guarde datos genéricos, e incluso hacer que la función haga una copia de esos datos para que así hacer que el que programa no tenga que preocuparse por liberar o no la memoria almacenada en la pila!