#include<iostream>
#include<limits.h>

typedef int TipoInfo; // tipo contenuto nella coda

struct NodoSCL;

struct NodoSCL{
	TipoInfo info;
	struct NodoSCL* next;
};

typedef struct NodoSCL* Coda;
// Il primo elemento della SCL e' la testa della coda

bool isEmpty(Coda q){
	return q == NULL;
}

void enqueue(Coda* q, TipoInfo v){
	if (q == NULL){
		return;
	}
	// Tecnica del nodo generatore:
	// Aggiungo nodo fittizio in testa per trattare allo stesso
	// modo i casi in cui la coda e' vuota e non
	// Il nodo verra' rimosso e deallocato al termine

	struct NodoSCL* g = (struct NodoSCL*) malloc(sizeof(NodoSCL));
	g -> next = *q;

	NodoSCL* aux = g;
	//Posiziona aux sull'ultimo nodo
	while (aux -> next != NULL){
		aux = aux -> next;
	}
	
	// Crea nodo in fondo alla coda
	aux -> next = (struct NodoSCL*) malloc(sizeof(NodoSCL));
	aux = aux -> next;
	aux -> info = v;
	aux -> next = NULL;

	// Elimina nodo generatore dalla coda:
	*q = g-> next;

	//Dealloca nodo generatore
	free(g);

}

TipoInfo dequeue(Coda* q){
	if (q == NULL || isEmpty(*q)){
		return INT_MIN;// valore per segnalare errore
	}
	struct NodoSCL* aux = *q;
	TipoInfo info = aux -> info;
	*q = (*q) -> next;
	free(aux);
	return info;
}

TipoInfo first(Coda q){
	if (isEmpty(q)){
		return INT_MIN;// valore per segnalare errore
	}
	return q->info;
}

// Funzioni ausiliarie

void stampa(Coda q){
	if (isEmpty(q)){
		std::cout << std::endl;
		return;
	}
	std::cout << q->info << " ";
	stampa(q->next);
}

int main(){
	Coda q = NULL;
	stampa(q);
	for (int i = 0; i < 10; i++){
		enqueue(&q,i);
	}
	stampa(q);
	std::cout << "first(q)=" << first(q) << std::endl;
	stampa(q);
	std::cout << "dequeue(&q)=" << dequeue(&q) << std::endl;
	stampa(q);
}