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.

#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);
	}
}

¡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!