Una coda è una lista di tipo FIFO (First in, first out). Ovvero il primo atomo ad essere entrato nella coda è il primo che esce. Precedentemente abbiamo visto l’implementazione in linguaggio C della struttura dati dinamica, Pila.

Qui di seguito, la definizione della struttura, e le varie funzioni primitive che operano sulle code:

/*
CODE
 
typedef int t_atomo; //ci definiamo un nuovo tipo di dato generico t_atomo, lo facciamo a parte così riceverà in ingresso questo tipo di dato che possiamo cambiare in float etc. Senza quindi modificare il tipo di dato nelle funzioni che implementeremo per lavorare sulle CODE.
 
Una coda sarà identificata dal puntatore al suo primo elemento: t_coda *p;
Struttura ricorsiva:
 
typedef
 struct coda{
 t_atomo info;
 struct coda *prox;
 } t_coda;
 
*/

Poichè in una coda gli inserimenti degli elementi si fanno alla fine e i prelievi all’inizio, si può rendere più efficente la funzione primitiva in_coda() = CONS, conservando il riferimento sia al primo elemento che all’ultimo elemento della coda.
Possiamo quindi definire una struttura di questo tipo (ci sarà utile per non far scorrere tutta la coda alla funzione in_coda() per far agganciare il nuovo elemento all’ultimo elemento), in questo modo invece di avere una complessità O(n), otterrà anch’essa così come le altre funzioni primitive, una C. computazionale costante: O(1):

/*
typedef
 struct{
 t_coda *primonodo, *ultimonodo;
 } t_coda_coda
 
Che andrà inizializzata mettendo in entrambi i suoi campi il valore NULL: t_coda_coda p = {NULL, NULL};
 
Le funzioni primitive sulle code, (anche la funzione in_coda() se definiamo la struttura sopra) hanno complessità computazionale costante: O(1).
 
*/
 
void inizializza_coda(t_coda_coda *p){
p->primonodo = NULL;
p->ultimonodo = NULL;
}
 
 
int null_coda(t_coda_coda p){ //Funzione NULL: Riceve in ingresso una coda e restituisce il valore di verità V = 1 se la coda è vuota, F = 0 se la coda non è vuota.
 return (p.primonodo == NULL); 
}
 
 
int primo(t_coda_coda p, t_atomo *x){ //Equivale alla funzione CAR: Riceve in ingresso una coda non vuota e restituisce il suo primo elemento (inserendolo nella variabile x che passiamo per indirizzo alla funzione).
if (p.primonodo){ // Se esiste il primo nodo della coda
*x = (p.primonodo)->info; //Inserisce il X, il valore del primonodo (memorizzato nel campo info).
return 0; //restituisce 0, operazione andata a buon fine
}else return 1; //La coda non esiste.
 
}
 
 
int out_coda(t_coda_coda *p){ //Equivale a CDR: Riceve in ingresso una Coda non vuota, e la priva del suo primo elemento.
 
 if (p->primonodo){ //Se esiste il primo nodo (elemento) della Coda, prosegue.
 
 p->primonodo = (p->primonodo)->prox; //mette primonodo uguale al prossimo nodo.
 if (p->primonodo == NULL) //Controlliamo se primo nodo adesso punta a NULL, se è vero, allora vorrà dire che la coda era formata da 1 solo elemento, ed rimuovendolo equivale a inizializzare la coda... di conseguenza operiamo come se dovessimo inizializzarla:
  p->ultimonodo = NULL; //Poniamo anche l'ultimo nodo = NULL. Adesso la Coda essendo stata privata del suo unico elemento, con questa assegnazione è come se viene inizializzata nuovamente (è vuota).
 
  return 0; //Elemento rimosso con successo.
 
 } else return 1; //La coda è vuota.
 
}
 
 
//Inserisce un elemento di tipo t_atomo alla coda. 
int in_coda(t_coda_coda *p, t_atomo x){ //Equivale alla funzione CONS. Trattandosi di code, l'elemento da inserire viene posto alla fine della coda.
t_coda *temp;
temp = (t_coda *) malloc(sizeof(t_coda)); //Ci allochiamo una coda formata da 1 solo elemento.
 
if (temp){ //Se l'allocazione di memoria va a buon fine:
 
 temp->info = x; //Assegna al campo info della coda appena allocata, il valore dell'elemento che vogliamo inserire in coda. 
 temp->prox = NULL; //Assegna come successivo elemento di questa coda, NULL.
 if (p->primonodo == NULL){ //se la coda è vuota (inizializzata a NULL quindi).
 p->primonodo = temp; //Inserisce nel primo nodo la coda temp (formata dal campo info e prox).
 p->ultimonodo = temp; //E anche nell'ultimo nodo inserisce temp (poichè essendo la coda vuota, immettendo un solo elemento, automaticamente esso è sia il primo che l'ultimo elemento di tale coda).
 }else{ //Altrimenti la coda conterrà già altri elementi
 (p->ultimonodo)->prox = temp; // il prossimo elemento dell'ultimo nodo punterà a temp.
 p->ultimonodo = temp; //l'ultimo nodo diventa temp.
 }
 return 0; //Operazione avvenuta con successo.
 
}else return 1; //Allocazione di memoria non riuscita.
 
}