Realizzazione di pile con liste concatenate
In questa realizzazione di Pila<E>, gli elementi sono memorizzati in una lista concatenata, cioè una sequenza di nodi ognuno dei quali contiene un elemento della lista (un oggetto di tipo E) e un puntatore al prossimo nodo.

Una pila contenente gli elementi <A1, A2, ..., An> viene rappresentata con una lista concatenata, dove il primo elemento è puntato dalla variabile top e contiene l'ultimo elemento inserito:
 
 

 

Scelte progettuali
Per la classe PilaList<E> 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<E>. 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.
 Primo passo: creazione di un nuovo nodo [ new ListNode<E>(A,top)]
Secondo passo: assegnamento a top
  •  Quando si toglie un elemento, si cambia top in modo da puntare all'elemento successivo.

    •  
  • Tutte le operazioni hanno complessità costante nel caso pessimo, O(1). 

La classe PilaList<E>
Il codice completo della classe PilaList<E> è mostrato sotto. La realizzazione si appoggia ovviamente sulla classe ListNode<E>.
  
import java.util.*;

/**
 * Classe PilaList<E>:
 *
 * Realizzazione della pila mediante Liste Concatenate
 */
public class PilaList<E> implements Pila<E> {
    ListNode<E> top;

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

    /**
     * Verifica che la pila sia logicamente vuota.
     * @return  <code>true</code> se la pila &egrave; vuota;
     *          <code>false</code> altrimenti.
     */
    public boolean empty() {
        return top == null;
    }

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

    /**
     * Restituisce l'oggetto in cima alla pila senza estrarlo.
     * @return   l'oggetto in cima.
     * @exception NoSuchElementException con pila vuota.
     */
    public E  peek() {
        if (empty()) throw new NoSuchElementException();
        return top.element;
    }

    /**
     * Inserisce un oggetto in cima alla pila.
     * @param x  l'oggetto da inserire.
     * @return   l'oggetto inserito.
     */
    public E push(E x) {
        top = new ListNode<E>(x, top);
        return x;
    }

    /**
     * Rimuove e restituisce l'oggetto in cima alla pila.
     * @return   l'oggetto in cima.
     * @exception EmptyStackException con pila vuota.
     */
    public E pop() {
        if (empty() throw new NoSuchElementException();
        E x = top.element;
        top = top.next;
        return x;
    }

    /**
     * Conversione in array
     * @return un array di Object con gli elementi della struttura
     */
    public Object[] toArray(){
                                // da realizzare
    }
}
 

Esercizi
1) Si consideri la seguente interfaccia
  
public interface RevPila<E> extends Pila<E> {

    /**
     * Rovescia il contenuto della pila
     */
    void reverse();
}

Si scriva la classe RevPilaList che estende PilaList e implementa l'interfaccia RevPila in modo tale che il metodo reverse() rovesci la pila su cui viene chiamato.

SOLUZIONE