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

  • Is Empty;
  • Top;
  • Push;
  • Pop;

Ricordiamo brevemente la definizione data all’interno dell’articolo Analisi Strutture Dati: le pile, o stack, sono particolari strutture dati che presentano un funzionamento opposto rispetto a quanto visto per le precedenti strutture a coda. Esse sono basate sul sistema LIFO (Last Input First Output), secondo cui è possibile ottenere solo l’elemento più recente inserito nella struttura. Negli esempi sottostanti supporremo che la pila venga riempita sempre da destra verso sinistra e quindi che gli elementi più vecchi (i primi) siano quelli più a destra. 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 pila passata come parametro, la funzione accetta in input un riferimento ad una struttura dati di tipo node (il seme della pila) 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 Top

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

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

Funzione Push

La funzione PUSH(node *first, int val) permette l’inserimento di un nuovo nodo (contenente il valore scelto value). Il codice per l’inserimento di un nuovo valore viene ripreso dalla funzione utilizzata nelle liste, si tratta infatti, della prima condizione del programma.

node *push(node *first, int value) {
  node *new;

  new = malloc(sizeof(node));
  if(new == NULL) {
    printf("Allocazione fallita");
    return NULL;
  }

  new->value = value;
  new->next  = first;
  
  first = new;
  return first;
}

Funzione Pop

La funzione POP(node *first, int index) consente l’eliminazione di un nodo, l’eliminazione di un valore dalla pila può essere paragonato ad uno shift completo a sinistra di tutti gli elementi della pila.

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

  free(first);
  return temp;
}

Altre informazioni

Per altre informazioni potete leggere anche: