5.6 Gestione di una pila

La pila può essere implementata in memoria utilizzando sia una struttura sequenziale se, per esempio, si prevede una dimensione massima che potrà avere la struttura, sia una struttura concatenata. Nel programma seguente viene utilizzata una struttura sequenziale per gestire una pila di libri. In questo programma vengono messe in evidenza principalmente le funzioni per la gestione di una pila.

/*
  Gestione di uno STACK con un elenco di libri 
*/

#include <stdio.h>

/* Implementazione dello Stack */

#define DIMSTACK 8	/*1*/

typedef struct rec {
  char titolo[50]; 
  char autore[20]; 
  char editore[20]; 
  float prezzo; 
}libro;
libro libreria[DIMSTACK];
int cima=-1;

/* Funzioni per la gestione dello Stack */

int pieno();	/*2*/
int vuoto();	/*2*/
void push(const libro *lib);	/*3*/
libro pop();	/*3*/
    
/* Altre funzioni del programma */

void inserisci();
void estrai();

main(){
  int scelta; 
  for(;;){

    /* Menu operazioni disponibili */

    printf("\nGestione di una pila di libri\n");	/*4*/
    printf("\n1) Inserimento di un libro"); 
    printf("\n2) Estrazione di un libro"); 
    printf("\n0) Fine elaborazione\n"); 
    printf("\nScelta operazione (1,2,0) "); 
    scanf("%d",&scelta); 
    while(!getchar()=='\n');

    if(!scelta)	/*5*/ 
      break;

    /* Richiama funzione scelta */

    switch(scelta){ 
      case 1: 
        inserisci(); 
        break; 
      case 2: 
        estrai(); 
    }
  } 
  return 0;
}

/* Inserimento di un libro nella pila */
    
void inserisci(){
  libro buflib;	/*6*/
  if(pieno()){	/*7*/ 
    printf("\n\aPresenti %d elementi",DIMSTACK); 
    printf("\nPila piena: inserimento impossibile"); 
  }else{ 
    printf("\nInserimento di un libro");	/*8*/ 
    fflush(stdin); 
    printf("\nTitolo : "); 
    gets(buflib.titolo); 
    printf("Autore : "); 
    gets(buflib.autore); 
    printf("Editore : "); 
    gets(buflib.editore); 
    printf("Prezzo : "); 
    scanf("%f",&buflib.prezzo); 

    push(&buflib);	/*9*/ 
  }
}

/* Estrazione di un libro */

void estrai(){
  libro buflib; 
  if(vuoto())	/*10*/ 
    printf("\n\aPila vuota: estrazione impossibile"); 
  else{ 

    buflib=pop();	/*11*/ 
    
    puts(buflib.titolo); 
    puts(buflib.autore); 
    puts(buflib.editore); 
    printf("%4.2f\n",buflib.prezzo); 
  }
}

/* Funzioni standard per la gestione di uno stack */

/* Funzioni che ritornano lo stato dello stack */
    
int vuoto(){	/*12*/
  if(cima==-1) 
    return 1; 
  else 
    return 0; 
}

int pieno(){	/*13*/
  if(cima==DIMSTACK-1) 
    return 1; 
  else 
    return 0; 
}

/* Inserimento di un elemento nella pila */

void push(const libro *lib){	/*14*/
  libreria[++cima]=*lib; 
}


/* Prelievo di un elemento dalla pila */

libro pop(){	/*15*/ 
  return libreria[cima--]; 
}

A cominciare dalla 1 viene definita la struttura: la dimensione massima dello stack, la struttura dell’elemento generico, la struttura sequenziale su cui verrà implementata la pila. Il puntatore cima, attualmente inizializzato al valore –1, sarà l’indice utilizzato per rintracciare la posizione dell’elemento su cui effettuare le operazioni. Si ricorda che, in una pila, le operazioni vengono effettuate sempre ad un estremo.

Nelle righe 2 e 3 sono indicate le funzioni utilizzate per la manipolazione della struttura. Le funzioni possiamo raggrupparle in due categorie: le 2 restituiscono informazioni sulla struttura, le 3 forniscono le operazioni ammesse sulla struttura. Qui finisce la definizione della struttura fornita in termini di tipo di dati che ne fanno parte e di funzioni per la loro manipolazione.

Il programma presentato offre un menù di operazioni possibili (visualizzato a cominciare da 4) da cui si esce, tramite 5, digitando un opportuno valore. Il programma consente solo operazioni di inserimento ed estrazione di un libro dalla pila.

La funzione di inserimento prepara nella 6 un buffer su cui conservare temporaneamente il libro da inserire nella struttura. Prima di effettuare l’inserimento nella pila è necessario assicurarsi che ci sia posto: ciò viene fatto, effettuando nella 7 una chiamata alla funzione pieno, affinché si sappia se è possibile effettuare l’inserimento. L’inserimento effettivo viene svolto ricevendo, cominciando da 8, i dati forniti in input nella memoria temporanea buflib e comunicando nella 9 alla funzione push l’indirizzo di tale area di memoria.

La funzione di estrazione di un elemento dalla pila è simile alla funzione di inserimento. Si interroga la pila al fine di conoscere se ci sono elementi da prelevare (linea 10). Se ci sono elementi da prelevare, si riceve dalla funzione pop, chiamata in 11, l’elemento cercato che viene conservato in un buffer appositamente predisposto.

La funzione vuoto, definita in 12, restituisce indicazioni sulla presenza di elementi nello stack. È necessario chiamarla prima di effettuare una estrazione.

La funzione pieno, definita nella 13, ritorna al chiamante un indicatore sullo stato della pila: se cima contiene l’indice dell’ultimo elemento la pila è piena: non si possono, per esempio, inserire ulteriori elementi.

La funzione push, definita in 14, dopo aver aggiornato cima copia nello stack l’elemento attualmente conservato in una memoria temporanea. Dal modo come è definita tale funzione si può dedurre, come d’altra parte riportato nel programma, che l’operazione di inserimento non controlla se effettivamente c’è posto nella struttura. La funzione, per poter funzionare correttamente, è necessario che sia chiamata condizionatamente ad una risposta ottenuta dal richiamo della funzione pieno. La funzione riceve come parametro passato un puntatore al buffer che contiene l’elemento da inserire. Tale parametro poteva essere anche una variabile di tipo libro. La scelta, nel caso di strutture, di passare un puntatore al posto di una variabile è comune nei programmi in C: passando un puntatore si effettua una elaborazione più veloce (non si spreca tempo nell’effettuare una copia della struttura passata nel parametro. Si consideri che una struttura può contenere parecchi membri) ed inoltre non si occupa memoria per conservare la struttura in una variabile locale.

La funzione pop della 15 ha un funzionamento analogo alla push, solo che qui le operazioni hanno verso opposto: dalla pila al buffer.

La scelta effettuata di distinguere, per esempio, la funzione di inserimento di un elemento (push) e la verifica della possibilità di inserimento (pieno), è motivata dalla volontà di distinzione fra le funzioni tipiche della gestione di uno stack (push e pop) e le necessità di gestione di una struttura fisica statica.