Appunti di informatica sulle Pile

Pile

Una pila è una sequenza di elementi (tutti dello stesso tipo) in cui l’inserimento e l’eliminazione di elementi avvengono secondo la regola seguente: l’elemento che viene eliminato tra quelli presenti nella pila deve essere quello che è stato inserito per ultimo. Si parla di gestione LIFO (per "Last In, First Out").

Esempio: rappresentazione grafica di una pila

L’elemento in cima alla pila viene detto elemento affiorante. Una pila senza elementi viene detta pila vuota.

Il tipo pila è un ADT <S,F,C> dove

• S = {pila, atomo, boolean} pila è il dominio di interesse, atomo è il dominio degli elementi che formano le liste.
• F = {push, top, empty, pop}

Funzioni

• push: atomo x pila -> pila inserisce un elemento in cima alla pila
• top: pila -> atomo ritorna l'elemento in cima alla pila
• empty: pila -> boolean ritorna il valore vero se la pila è vuota
• pop: pila -> pila ritorna la pila privata dell'elemento in cima

C = pila vuota, è la costante che denota la coda priva di elementi.

Pile mediante array

Definizione

typedef int TAtomo;
typedef struct StElem {    
    TAtomo *e;    
    int primo, NMax;
} Pila;

Pile

Una pila è una sequenza di elementi (tutti dello stesso tipo) in cui l’inserimento e l’eliminazione di elementi avvengono secondo la regola seguente: l’elemento che viene eliminato tra quelli presenti nella pila deve essere quello che è stato inserito per ultimo. Si parla di gestione LIFO (per "Last In, First Out").

Esempio: rappresentazione grafica di una pila

L’elemento in cima alla pila viene detto elemento affiorante. Una pila senza elementi viene detta pila vuota.

Il tipo pila è un ADT <S,F,C> dove

• S = {pila, atomo, boolean} pila è il dominio di interesse, atomo è il dominio degli elementi che formano le liste.
• F = {push, top, empty, pop}

Funzioni

• push: atomo x pila -> pila inserisce un elemento in cima alla pila
• top: pila -> atomo ritorna l'elemento in cima alla pila
• empty: pila-> boolean ritorna il valore vero se la pila è vuota
• pop: pila -> pila ritorna la pila privata dell'elemento in cima

C = pila vuota, è la costante che denota la coda priva di elementi.

Pile mediante array

Definizione

typedef int TAtomo;
typedef struct StElem {
    TAtomo *e;
    int primo, NMax;
} Pila;

Funzioni

int InizializzaPila( Pila *PP, int NElemMax ) {
    PP->e = (TAtomo *) malloc(sizeof(TAtomo) * NElemMax);
    if( PP->e == NULL ) return 0;
    PP->primo = -1;
    return PP->NMax = NElemMax;
}
int empty( Pila P ) {
    return (P.primo == -1);
}
int full( Pila P ) {
    return (P.primo == P.NMax-1);
}
int pop ( Pila *PP ) {
    if( !null(*PP) ) return 0;
    PP->primo--;
    return 1;
}
int push (Pila *PP, TAtomo A ) {
    if( full(*PP)) return 0;
    if( null(*PP)) PP->primo = 0;
    else PP->primo++;
    PP->e[PP->primo] = A;
    return 1;
}
TAtomo top( Pila P ) {
    if( null(P) ) return NULL;
    return P.e[P.primo];
}

Implementazioni concatenate (puntatori)