In questo articolo andiamo a raccogliere le quattro funzioni caratteristiche delle code, le funzioni che analizzeremo sono:

  • Is Empty;
  • Front;
  • Enqueue;
  • Dequeue;

Ricordiamo brevemente la definizione data all’interno dell’articolo Analisi Strutture Dati: le code sono delle strutture dati che presentano caratteristiche simili alle liste, tuttavia esse permettono l’esecuzione delle operazioni solo sul primo elemento inserito, ovvero l’ultimo elemento della coda. Per questo motivo si dice che le code operano secondo il principio FIFO (First Input First Output). Per maggiori informazioni circa la sintassi del linguaggio si faccia riferimento alla guida al Linguaggio C.

algo_str3

Iniziamo definendo la struttura che conterà i nostri valori:

struct node {
 int value;
 struct node *next;
};
typedef struct node node;

struct node *first = null;

Funzione Is Empty

La funzione IS_EMPTY(node *first) permette la verifica dell’esistenza della struttura dati di tipo cosa passata come parametro, la funzione accetta in input un riferimento ad una struttura dati di tipo node (il seme della coda) e restituisce in output un valore intero (1 se la struttura esiste, 0 in caso contrario). Ricordiamo che nel linguaggio C non esiste un tipo nativo Boolean.

int is_empty(node *first) {
  if(first == NULL) {
    return 1;
  }
  else {
    return 0;
  }
}

Funzione Front

La funzione FRONT(node *first) permette di acquisire il valore contenuto all’interno del primo nodo della coda. La lettura del valore della coda è semplicemente la stampa del valore del primo nodo.

int front(node *first) {
  return first -> value;
}

Funzione enqueue

La funzione ENQUEUE(node *first, int value) permette l’inserimento di un nuovo valore all’interno della coda, questo a sua volta richiede lo scorrimento di tutti i valori di quest’ultima, al fine di determinare l’ultimo elemento inserito.

node *enqueue(node *first, int value) {
  node *current = first, *new;

  if(is_empty(first) == 1) { // è il primo valore che inserisco
    first = malloc(sizeof(node));
    if(first == NULL) {
      printf("Allocazione fallita");
      return NULL;
    }
    
    first->value = value;
    first->next  = NULL;
  }
  else {
    while(current->next != NULL) {
      current = current -> next;
    }

    new = malloc(sizeof(node));
    if(new == NULL) {
      printf("Allocazione fallita");
      return NULL;
    }
    
    new->value = value;
    new->next  = NULL;
    
    current->next = new;
  }
  
  return first;
}

Funzione Dequeue

La funzione DEQUEUE(node *first) consente l’eliminazione di un valore dalla coda, tale operazione può essere paragonata ad uno shift completo a sinistra di tutti gli elementi della coda.

node *dequeue(node *first) {
  node *temp = first->next;

  free(first);
  return temp;
}

Altre informazioni

Per altre informazioni potete leggere anche: