Realizzazioni del TDA Pila

Realizzare il Tipo di Dati Astratto Pila (cioè l'interfaccia Java Stack) significa fornire un Tipo di Dati (una classe) le cui operazioni (metodi) rispettino la specifica dei corrispondenti metodi astratti in Stack, cioè il tipo e il significato descritto informalmente.

Vedremo due realizzazioni:

Nella prima, ArrayStack, una istanza (cioè una pila) memorizza i suoi elementi in un array;

Nella seconda, ListStack, la pila memorizza gli elementi in una lista concatenata.

Le due realizzazioni sono molto diverse concettualmente, ma sono simili per occupazione di memoria e complessità delle operazioni.

Verso la realizzazione con array

Nella prima realizzazione, una pila comprende:

un array, nel quale vengono memorizzati gli elementi;
una variabile intera che ad ogni istante indica la posizione in cui è memorizzato l'ultimo elemento inserito.

La realizzazione è semplice, ma

La dimensione di un array è fissata al momento della creazione, mentre una pila può contenere un numero illimitato di elementi.
Infatti nella specifica di "push" non è previsto che possa essere lanciata un'eccezione per un "troppo pieno".

Soluzione: quando l'array si riempie, lo sostituiamo con uno più grande.

Nota: Usando un Vectoral posto di un array questo problema sarebbe scomparso, infatti una realizzazione di Stack con Vector è molto semplice [Esercizio per casa: scriverla!].

Abbiamo preferito usare un array perché l'uso di un Vector avrebbe nascosto il meccanismo per l'allocazione del nuovo spazio in memoria, e quindi non avrebbe consentito un'analisi precisa della complessità della realizzazione.

Scelte progettuali

Per la classe ArrayStack abbiamo fatto le seguenti scelte:

Una pila memorizza i suoi elementi nell'array (chiamato theArray) a partire dalla posizione 0, in ordine di inserimento;
La variabile top indica in ogni istante la posizione della cima della pila.
La variabile top viene inizializzata con -1, incrementata quando si inserisce un elemento e decrementata quando si toglie. In questo modo ad ogni istante vale

top = <numero elementi della pila> - 1

Quando si rimuove un elemento, questo non viene cancellato dall'array ma viene solo decrementata top. La pila viene considerata vuota se e solo se top vale -1 , indipendentemente dal contenuto dell'array.
Quando l'array si riempie, viene sostituito con uno di dimensione doppia

<a,b,c>

Stato interno della pila dopo l'inserimento di tre elementi

La classe ArrayStack

Il codice della realizzazione diventa, a questo punto, quasi autoesplicativo.
Tutte le operazioni hanno complessità costante nel caso pessimo [O(1)], tranne push che ha complessità lineare, O(n). Tuttavia push ha complessità ammortizzata costante, poiché il metodo doubleArray viene invocato raramente.

package lab2;

/**
* Classe ArrayStack :
*
* Realizzazione del TDA Pila mediante array.
*/
public class ArrayStack implements Stack {
static final int DEFAULT_SIZE = 32 ;

protected Object [ ] theArray ;
protected int top ;

    /**
    * Costruttore della pila.
    */
    public ArrayStack ( ) {
        theArray = new Object [ DEFAULT_SIZE ] ;
        top = -1 ;
    }

    /**
    * Verifica che la pila sia logicamente vuota.
    * @return <code>true</code> se la pila è vuota;
    *          <code>false</code> altrimenti.
    */
    public boolean isEmpty ( ) {
        return top == -1 ;
    }

    /**
    * Svuota la pila.
    */
    public void clear ( ) {
        top = -1 ;
    }

    /**
    * Restituisce l'oggetto in cima alla pila senza estrarlo.
    * @return   l'oggetto in cima.
    * @exception EmptyStackException con pila vuota.
    */
    public Object peek ( ) {
        if ( isEmpty ( ) )
            throw new EmptyStackException ( ) ;
        return theArray [ top ] ;
    }

    /**
    * Inserisce un oggetto in cima alla pila.
    * @param x l'oggetto da inserire.
    * @return   l'oggetto inserito.
    * @exception IllegalArgumentException se l'argomento passato
    *            è <code>null</code>.
    */
    public Object push ( Object x ) {
    if ( x == null )
        throw new IllegalArgumentException ( ) ;
        if ( top == theArray.length - 1 )
    doubleArray ( ) ;
        return theArray [ ++top ] = x ;
    }

    /**
    * Rimuove e restituisce l'oggetto in cima alla pila.
    * @return   l'oggetto in cima.
    * @exception EmptyStackException con pila vuota.
    */
    public Object pop ( ) {
        if ( isEmpty ( ) )
            throw new EmptyStackException ( ) ;
        return theArray [ top-- ] ;
    }

    /**
    * Metodo interno per raddoppiare la dimensione di theArray.
    */
    protected void doubleArray ( ) {
    Object [ ] newArray ;

        newArray = new Object [ theArray.length * 2 ] ;
        for ( int i = 0; i < theArray.length; i++ )
              newArray[ i ] = theArray [ i ] ;
        theArray = newArray ;
    }
}

Verso la realizzazione con liste concatenate

Nella seconda realizzazione di Stack, una pila memorizza i sui elementi in una lista concatenata, cioè una sequenza di oggetti (nodi) ognuno dei quali contiene un elemento della lista (un generico oggetto) e un puntatore al prossimo nodo.

Graficamente un nodo, istanza della classe ListNode, viene rappresentato così:

Una pila contenente gli elementi <a₁, a₂, ..., a_n> viene rappresentata con una sequenza di nodi, dove il primo è puntato dalla variabile top e contiene l'ultimo elemento inserito:

Scelte progettuali

Per la classe ListStack abbiamo fatto le seguenti scelte:

Gli elementi della pila vengono memorizzati in una lista concatenata in ordine inverso: il primo elemento inserito sarà in fondo alla lista, e la cima della pila in testa alla lista.

Una pila ha un'unica variabile d'istanza, chiamata top, di tipo ListNode. Concettualmente, top è un puntatore al primo elemento (testa) della lista.

Una pila è vuota se e solo se top vale null.

Quando si inserisce un elemento nella pila lo si mette in un nuovo nodo, che diventa il primo della lista; quando si toglie un elemento, si cambia top in modo da puntare all'elemento successivo.

**Inserimento di un elemento. Primo passo: creazione di un nuovo nodo**

**Secondo passo: assegnamento a top**

La classe ListNode

I nodi sono saranno istanze della classe ListNode.

package lab2;

/**
* Classe ListNode:
*
* Classe usata per descrivere il singolo nodo di una lista.
*/

public class ListNode {

public Object element ;
public ListNode next ;

    /**
      * Costruttore nodo isolato
      */
    public ListNode ( Object element ) {
    this( element, null ) ;
    }

     /**
      * Costruttore nodo per liste unidirezionali, dove element e' non null
      */
    publicListNode ( Object element, ListNode next ) {
         if ( element == null )
                throw new IllegalArgumentException ( ) ;
         this.element = element ;
         this.next     = next ;
    }
}

La classe ListStack

Ecco il codice della realizzazione.
Tutte le operazioni hanno complessità costante nel caso pessimo, O(1).

package lab2;

/**
* Classe ListStack:
*
* Realizzazione del TDA Pila mediante liste.
*/

public class ListStack implements Stack {
protected ListNode top ;

    /**
    * Costruttore della pila.
    */
    public ListStack ( ) {
        top = null ;
    }

    /**
    * Svuota la pila.
    */
    public void clear ( ) {
        top = null ;
    }

    /**
    * Inserisce un oggetto in cima alla pila.
    * @param x l'oggetto da inserire.
    * @return   l'oggetto inserito.
    * @exception IllegalArgumentException se l'argomento passato
    *            è <code>null</code>.
    */
    public Object push ( Object x ) {
        if ( x == null )
            throw new IllegalArgumentException ( ) ;
        top = new ListNode ( x, top ) ;
        return x;
    }

Esercizi su realizzazione di pile

1) Si fornisca una implementazione dell'interfaccia Stack, utilizzando la classe Vector.

2) Si consideri la seguente interfaccia

import lab2.*;
public interface RevStack extends Stack {
    /**
    * Rovescia il contenuto della pila
    * @return una nuova pila, che contiene i valori della pila
    * che esegue il metodo, ma in ordine inverso
    */
    Stack reverse ( ) ;
}

dove il metodo introdotto rovescia il contenuto di una pila, senza alterare la pila originale. Si definisca una classe ArrayRevStack, che estende ArrayStack e implementa l'interfaccia.
Si confronti questa soluzione con la propria.

3) Si definisca una classe ListRevStack, che estende la classe ListStack e implementa l'interfaccia RevStack.

4) Si consideri la seguente interfaccia

public interface SwapStack extends Stack{
        /**
        *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
        */
        Stack swap ( ) ;
}

dove il metodo introdotto scambia il contenuto dei primi due elementi di una pila, senza alterare la pila originale, sollevando l'eccezione EmptyStackException nel caso la pila contenga meno di due elementi.
Si definisca una classe ArraySwapStack, che estende ArrayStack e implementa l'interfaccia SwapStack.

5) Si definisca una classe ListSwapStack, che estende la classe ListStack e implementa l'interfaccia SwapStack.