Tipo di dati astratto pila
Le  pile  (stack) sono un tipo di dati astratto molto semplice, ma dal diffuso impiego.

Intuitivamente, una pila è un sequenza di zero o più elementi
 

<a1, a2, ..., an>

in cui è possibile  aggiungere o togliere elementi soltanto ad un estremo della sequenza, detto cima (top) della pila.

Politica di accesso:

LIFO  (Last In, First Out)
[ultimo elemento inserito, primo elemento rimosso]

Esempi: una pila di piatti, un tubetto di pastiglie, ...

Presentazione grafica di una pila
Di solito una pila viene rappresentata graficamente come una sequenza verticale di "caselle" contenenti i suoi elementi. La casella più in alto è la cima (top).
 
<A, B, C>
 
C
B
A
pila di tre elementi vista come sequenza  e sua rappresentazione grafica 

Operazioni su pile
La specifica del TDA pila comprende normalmente le seguenti operazioni:
  • Inserimento di un elemento in cima alla pila (normalmente chiamata push)
  • Estrazione dell'elemento in cima alla pila (chiamata pop)
  • Lettura dell'elemento in cima alla pila, senza eliminarlo (chiamata top o peek)
  • Svuotamento della pila (chiamata clear)
  • Controllo se la pila è vuota oppure no
Esempio di estrazione e inserimento: 
C
B
A

 
B
A
D
B
A
pila iniziale; dopo l'eliminazione della cima;
dopo l'inserimento di D

Pile in Java: l'interfaccia Stack
La seguente interfaccia definisce il tipo di dati astratto Stack
 
 
public interface Stack{

    // Inserisce un oggetto in cima alla pila.
    Object push ( Object x ) ;

    // Rimuove e restituisce l'oggetto in cima alla pila
    Object pop ( ) ;

    // Restituisce l'oggetto in cima alla pila senza rimuoverlo
    Object peek ( ) ;

    // Verifica che la pila sia logicamente vuota.
    boolean isEmpty ( ) ;

    // Svuota la pila.
    void clear ( ) ;
  }

Significato dei metodi

Il significato dei metodi (la loro semantica) viene spiegato (in modo informale) dai commenti al codice, leggibili anche con un browser grazie a javadoc: 
 
    /**
     * Inserisce un oggetto in cima alla pila.
     * @param x  l'oggetto da inserire.
    * @return   l'oggetto inserito.
    * @exception  IllegalArgumentException se l'argomento passato 
    *            &egrave; <code>null</code>. 
    */
    Object push ( Object x ) ;

Quindi:

  • il paramentro attuale viene inserito in cima alla pila;
  • tale parametro viene anche restituito alla fine del metodo;
  • viene lanciata un'eccezione di tipo IllegalArgumentException  [locale, Medialab, Sun] se il parametro vale null.
Vediamo la documentazione di pop:
 
  /**
   * Rimuove e restituisce l'oggetto in cima alla pila.
   * @return   l'oggetto in cima.
   * @exception EmptyStackException con pila vuota.
   */
  Object pop ( ) ;

Si noti il metodo lancia un'eccezione se viene eseguito da una pila vuota. L'eccezione EmptyStackException è definita all'interno del package lab2.

Un esempio: Parentesi bilanciate (1)
Supponiamo di voler scrivere un algoritmo che riceva in ingresso una espressione aritmetica, e verifichi il corretto bilanciamento delle parentesi.
Se le parentesi sono solo tonde, basta utilizzare una variabile intera (un contatore). 
 
Esercizio: Scrivere un algoritmo che risolva il problema, restituendo true se l'espressione è bilanciata, false altrimenti.

Se le parentesi possono essere graffe, quadre o tonde, è facile convincersi che non bastano uno o più contantori, ma occorre ricordare la sequenza delle parentesi aperte. Il seguente algoritmo risolve il problema usando una pila:
 

0. Sia data una stringa str in input;
1. crea una pila vuota;
2. leggi il prossimo carattere c di str:
2.1. se c non è una parentesi, passa al carattere successivo;
2.2. se c è una parentesi aperta, inseriscilo nella pila;
2.3. altrimenti (c è una parentesi chiusa),
2.3.1 se la pila è vuota, restituisci false;
2.3.2 altrimenti (la pila non è vuota), estraine la cima (il carattere c')
2.3.2.1 se la parentesi aperta c' e quella chiusa c sono dello stesso tipo, passa al carattere successivo
2.3.2.2 altrimenti restituisci false
3. quando sono finiti i caratteri, 
3.1 se la pila è vuota, restituisci true;
3.2 altrimenti restituisci false. 

Parentesi bilanciate (2)
Vediamo il codice Java. Definiamo prima una classe Bracket, che funga da contenitore per char, ed offra un ulteriore metodo utile.
 
public class Bracket {
    protected char token;

    public Bracket ( char tok ) {
    token = tok ;
    }

    public char charValue ( ) {
        return token ;
    }

    public boolean IsMatch ( Bracket b ) {
        return ( ( token == '(' ) && ( b.charValue ( ) == ')' ) ||
                 ( token == '[' ) && ( b.charValue ( ) == ']' ) ||
                 ( token == '{' ) && ( b.charValue ( ) == '}' ) ) ;
    }
} 

 
Esercizio: Perché non abbiamo definito Bracket come una sottoclasse di Character? Provare a dichiarare una classe Bracket2 che estenda Character e vedere cosa segnala il compilatore.

Parentesi bilanciate (3)
Ed ecco infine il cui metodo statico checkBalPar della classe BalPar,  che implementa l'algoritmo descritto in precedenza. Può essere provato con la classe TestBalPar
 
public static boolean checkBalPar ( String toCheck ) {
    // si usa ArrayStack come realizzazione di Stack
    Stack stck = new ArrayStack ( ) ;

    for ( int i=0; i < toCheck.length( ); i++ ) {
    Bracket current = new Bracket ( toCheck.charAt ( i ) ) ;

        switch ( current.charValue ( ) ) {
                case '(': case '[': case '{':
                    stck.push( current ) ;
                    break;

                case ')': case ']': case '}':
                    try {
                 Bracket match = (Bracket) stck.pop ( ) ;
                        if ( ! match.IsMatch( current ) )
                            return false; // annidamento errato
                    } catch( EmptyStackException e ) {
                            return false; // troppe parentesi chiuse
                       }
                    break;

                default: // simbolo diverso da parentesi
        }
    } 

    if  ( ! stck.isEmpty ( ) ) {
        return false ; // parentesi rimaste aperte
    } else return true ;
}

Esercizi sull'uso di pile
1) Si definisca una classe con la seguente struttura:
 
public class ReverseStack {
   /**
    * Restituisce una nuova pila, che contiene i valori 
    * della pila passata per argomento, ma in ordine inverso.
    * La pila originale non viene modificata.
    */
    public static Stack reverse( Stack input ) {
          // DA DEFINIRE
    }
}

Soluzione: Si osservi che quando si dice "La pila originale non viene modificata" si intende che il suo stato deve essere ripristinato prima della fine del metodo.

2)   Si fornisca una implementazione della seguente classe astratta
 
abstract class SwapStackInterface{
   protected Stack scambia ;

   public SwapStackInterface ( Stack input ) {
     scambia = input ;
   }

   /**
   * Scambia il contenuto dei primi due elementi della pila
   * @return una nuova pila, che contiene i valori della pila
   * che esegue il metodo, con i primi due elementi scambiati
   */
   abstract Stack swap ( ) ;
}

dove il metodo swap deve restituire un pila ottenuta da quella in scambia scambiando i primi due elementi, senza alterare la pila scambia. Se scambia contiene meno di due elementi, swap deve lanciare un'eccezione EmptyStackException.

3)    Si definisca una classe con la seguente struttura
 

public class Clone {
    /**
     * Crea una copia della pila passata come parametro
     * @return  la copia della pila
     */
   public static Stack clone( Stack daClonare ) {
     // DA DEFINIRE
   }
}

dove il metodo clone non deve alterare la pila originale.