Le pile

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.

algo_str3

Quasi tutta l’implementazione delle pile viene ripresa dall’implementazione delle code, tuttavia le funzioni precedentemente esposte vengono, nell’uso comune, rinominate:

  • \text{IS\_EMPTY}(Q) , verifica l’esistenza della pila;
  • \text{TOP}(S, u), corrisponde alla funzione latex \text{GET}(Q, u), essa legge il primo elemento della pila;
  • \text{ENQUEUE}(Q, u) , ora \text{PUSH}(S, u) viene modificata, essa si occuperà di inserire un nuovo valore all’inizio della pila;
  • \text{POP}(S) , corrisponde a \text{DEQUEUE}(Q) , esegue la rimozione del primo elemento della pila.

In formule:
\text{IS\_EMPTY}(Q) = \{ 1 \text{ if } Q=\Lambda; 0 \text{ else } \}
\text{TOP}(Q) = \{ a_{1} \text{ if } Q=(a_{1}, \ldots, a_{n}); \perp \text{ else } \}
\text{PUSH}(S, u) = \{ (u) \text{ if } S=\Lambda; (u, a_{1}, \ldots, a_{n}) \text{ if } S=(a_{1}, \ldots, a_{n}) \}
\text{POP}(Q) = \{ (a_{2}, \ldots, a_{n}) \text{ if } Q=(a_{1}, \ldots, a_{n}); \perp \text{ else } \}

Implementazione delle Pile in Linguaggio C

Ancora una volta l’implementazione più efficiente prevede l’utilizzo delle strutture dati record. Durante la costruzione delle pile, l’implementazione della struttura dati e di molte funzioni possono essere fortunatamente ereditate dalle code. La struttura dati node, già vista nelle liste, può ad esempio essere utilizzata anche per contenere i valori delle code.

struct node {
 int value;
 struct node *next;
};
typedef struct node node;
struct node *first = null;

Implementazione delle operazioni fondamentali

In questa pagina andiamo a riscrivere la funzione enqueue, ora denominata push, l’unica funzione delle pile che differisce dall’implementazione delle code. Il codice per l’inserimento di un nuovo valore viene ripreso dalla funzione utilizzata nelle liste, si tratta, infatti, della prima condizione.

Procedura PUSH(S, a)
begin
  creo un nuovo nodo X (nuova struttura record)
  X∙valore := a
  X∙puntatore := ∗S
  return X
end

Il costo dell’operazione è unitario, \Theta(1) . Per l’implementazione in linguaggio C si faccia riferimento a questa pagina.