Il 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

<A₁, A₂, ..., A_n>

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, ...

...una pila di libri... ... ma NON una batteria o una torcia elettrica!... ... anche se in realtà lo possono essere

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>

pila di tre elementi vista come sequenza e sua rappresentazione grafica

Operazioni su pile

Le operazioni definite su una pila sono le seguenti:

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 peek)

Controllo se la pila è vuota oppure no (predicato empty)

Svuotamento della pila (chiamata clear)

Esempio di uso di pile

Vediamo l'effetto di una sequenza di operazioni su di una pila:

Operazione Stato della pila
dopo l'operazione Risultato

Stato iniziale

Estrai

Inserisci C

Inserisci K

Vuota?

false

Leggi

Estrai

Svuota

Vuota?

true

Pile in Java: la classe Stack<E>

In Java la classe Stack estende Vector, implementa direttamente i metodi

empty(),
peek(),
pop(),
push(E item)

ed eredita da Vector (tra gli altri) il metodo clear().

Il fatto di estendere Vector permette di usare anche tutti i suoi metodi, in particolare l'accesso diretto agli elementi, (possibilità poco elegante ma spesso comoda).

Esempio di uso di pile (II)

Vediamo il codice Java corrispondente all'esempio precedente. Assumiamo che A, B, C e K siano variabili di tipo String

Invocazione di metodo Stato della pila
dopo l'invocazione Risultato

(Costruzione dello) Stato iniziale

Stack<String> pila = new Stack<String>();
pila.push(A);
pila.push(B);

Estrai

pila.pop();

Inserisci C

pila.push(C);

Inserisci K

pila.push(K);

Vuota?

pila.empty();

false

Leggi

pila.peek();

Estrai

pila.pop();

Svuota

pila.clear();

Vuota?

pila.empty();

true

Possibili eccezioni

Alcune delle operazioni definite su una pila non hanno senso in certe situazioni: in questi casi verrà lanciata un'eccezione, come descritto nell'interfaccia. In particolare:

i metodi pop e peek lanciano una eccezione di tipo java.util.EmptyStackException se la pila su cui sono invocati è vuota;

La capacità di uno Stack è limitata solo dalla capacità di memoria in quanto gli elementi di tipo Vector sono autoespandenti.

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.

Esempi:

(((())()))  -> true

((()())))(((()())) -> false

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.

Esempi:

([({})[]])  -> true

([({)}[]]) -> false

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.

stringa

operazione

stack (dopo operazione)

esito

([({})[]])
^
c

Stack<String> pila = new Stack<String>();
pila.push("(");

(

([({})[]])
 ^
 c

pila.push("[");

[

(

([({})[]])
  ^
  c

pila.push("(");

(

[

(

([({})[]])
   ^
   c

pila.push("{");

{

(

[

(

([({})[]])
    ^
    c

pila.empty() è false
c' = pila.pop(); ovvero c' = "{"
c match c' è true

(

[

(

([({})[]])
     ^
     c

pila.empty() è false
c' = pila.pop(); ovvero c' = "("
c match c' è true

[

(

([({})[]])
      ^
      c

pila.push("[")

[

(

([({})[]])
       ^
       c

pila.empty() è false
c' = pila.pop(); ovvero c' = "["
c match c' è true

[

(

([({})[]])
        ^
        c

pila.empty() è false
c' = pila.pop(); ovvero c' = "["
c match c' è true

(

([({})[]])
         ^
         c

pila.empty() è false
c' = pila.pop(); ovvero c' = "("
c match c' è true

([({})[]])
         
caratteri finiti!

pila.empty() è true

true

stringa

operazione

stack (dopo operazione)

esito

([({)}[]])
^
c

Stack<String> pila = new Stack<String>();
pila.push("(");

(

...

...

...

([({)}[]])
   ^
   c

pila.push("{");

{

(

[

(

([({)}[]])
    ^
    c

pila.empty() è false
c' = pila.pop(); ovvero c' = "{"
c match c' è false

(

[

(

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 { char token; public Bracket ( char tok ) { token = tok ; } public char charValue ( ) { return token ; } public boolean isMatch ( Bracket b ) { return ( ( token == '(' ) && ( b.token == ')' ) || ( token == '[' ) && ( b.token == ']' ) || ( token == '{' ) && ( b.token == '}' ) ) ; } }

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 che implementa l'algoritmo descritto in precedenza.

import java.util.Stack;
public class BalPar { public static boolean checkBalPar (String toCheck) { // si usa Stack come realizzazione delle pile Stack<Bracket> stck = new Stack<Bracket>(); 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 '}': if ( stck.empty() ) return false; // troppe parentesi chiuse{ Bracket match = stck.pop ( ) ; if ( ! match.isMatch( current ) ) return false; // annidamento errato break; default: // simbolo diverso da parentesi } } return stck.empty(); } }

Esercizi proposti sull'uso di pile

1) Si definisca una classe con la seguente struttura:

public class StackReverse { /** * Rovescia la pila passata per argomento * @return 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<String> reverse ( Stack<String> input ) { // DA COMPLETARE } }

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 definisca una classe con la seguente struttura:

public class StackPalindrom { /** * Crea una copia palindroma della pila passata per argomento * La pila originale non viene modificata. */ public static Stack<String> palindrom ( Stack<String> input ) { // DA COMPLETARE } }