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

// Struttura del Nodo della Coda
typedef struct NodoCoda {
  int dato;
  struct NodoCoda *prossimo;
} NodoCoda;

// Struttura di Controllo con doppio puntatore per efficienza di inserimento
typedef struct {
  NodoCoda *head; // Punto di prelievo (inizio fila)
  NodoCoda *tail; // Punto di inserimento (fine fila)
} Coda;

// Inizializzazione
void inizializza_coda(Coda *c) {
  c->head = NULL;
  c->tail = NULL;
}

// Controllo stato
bool is_empty_coda(const Coda *c) { return c->head == NULL; }

// Operazione ENQUEUE (Inserimento in coda - Tempo Istantaneo)
void accoda(Coda *c, int valore) {
  NodoCoda *nuovo = (NodoCoda *)malloc(sizeof(NodoCoda));
  if (nuovo == NULL) {
    fprintf(stderr, "Errore: Memoria insufficiente per l'accodamento!\n");
    exit(1);
  }
  nuovo->dato = valore;
  nuovo->prossimo = NULL;

  if (c->head == NULL) {
    // Se la coda è vuota, il nuovo nodo è contemporaneamente testa e coda
    c->head = nuovo;
    c->tail = nuovo;
  } else {
    // L'attuale ultimo nodo aggancia il nuovo arrivato
    c->tail->prossimo = nuovo;
    // Spostiamo il marcatore di coda sul nuovo elemento
    c->tail = nuovo;
  }
}

// Operazione DEQUEUE (Estrazione dalla testa - Tempo Istantaneo)
bool decoda(Coda *c, int *valore_estratto) {
  if (is_empty_coda(c)) {
    return false; // Underflow
  }

  NodoCoda *da_eliminare = c->head;
  *valore_estratto = da_eliminare->dato;

  // Facciamo avanzare la testa
  c->head = c->head->prossimo;

  // Se la coda si è svuotata, azzeriamo anche il marcatore di coda
  if (c->head == NULL) {
    c->tail = NULL;
  }

  free(da_eliminare);
  return true;
}

// Svuota completamente lo Heap residuo della coda
void libera_coda(Coda *c) {
  int scarto;
  while (decoda(c, &scarto))
    ;
}

// Programma di Test
int main(void) {
  Coda mia_coda;
  inizializza_coda(&mia_coda);

  printf("--- TEST INSERIMENTO IN CODA (ENQUEUE) ---\n");
  printf("Accodo nell'ordine: 100, 200, 300\n");
  accoda(&mia_coda, 100);
  accoda(&mia_coda, 200);
  accoda(&mia_coda, 300);

  printf("\n--- TEST RIMOZIONE DALLA CODA (DEQUEUE - LOGICA FIFO) ---\n");
  int valore;
  while (decoda(&mia_coda, &valore)) {
    printf("Decodato (estratto): %d\n", valore);
  }
  // L'ordine di estrazione deve essere identico a quello di inserimento: 100,
  // 200, 300

  if (is_empty_coda(&mia_coda)) {
    printf("\nLa coda e' stata svuotata correttamente!\n");
  }

  // Cleanup finale
  libera_coda(&mia_coda);
  return 0;
}