Cognome___________________ Nome ____________________ Matricola____________________
Questo compito è stato discusso e definito collegialmente dalla commissione di esame di Fondamenti di Informatica.
Esame di Fondamenti di Informatica II (N.O.) (prova pratica di programmazione n.1)
11-luglio-2002
Testo dell’esercizio
Una pila è una struttura di dati che consente di collezionare oggetti in base ad una strategia LIFO (Last In First Out), cioè l’ultimo elemento inserito è sempre il primo che può essere rimosso.
L’ultimo elemento inserito si chiama anche “elemento affiorante” dalla pila. Una pila consente sempre due tipi di operazioni: inserimento di un elemento (push) e rimozione dell’elemento affiorante (pop). In figura è mostrato una sequenza di operazioni su una pila inizialmente vuota.
Sia data la seguente interfaccia Java, che descrive i metodi di una pila:
public interface Pila {
/* inserisce un elemento nella pila */
public void push (Object data);
/* ritorna e rimuove l’elemento affiorante dalla pila: */
/* PRE: la pila è non vuota */
public Object pop ();
/* ritorna true se la pila è vuota e false altrimenti */
public boolean isEmpty();
}
Si supponga inoltre data la classe LinkedList che implementa una struttura di dati lista con i seguenti metodi:
/* costruttore: crea una nuova lista vuota */
public LinkedList ();
/* aggiunge un elemento in testa alla lista */
public void addToHead (Object data);
/* ritorna e rimuove l’elemento in testa alla lista */
/* PRE: la lista non è vuota */
public Object removeFromHead ();
/* ritorna il numero di elementi della lista */
public int size ();
1. Utilizzando la tecnica del forwarding, definire la classe PilaConLista che implementa l’interfaccia Pila utilizzando la classe LinkedList. (Suggerimento: ogni metodo della classe PilaConLista deve essere implementato usando un metodo della classe LinkedList).
2. Definire la classe TestPilaConLista per il test della classe PilaConLista. Tale classe di test contiene il solo metodo main, il quale svolge le seguenti azioni:
- Fa inserire all’utente un insieme di oggetti String in una pila P; l’insieme degli oggetti da inserire è deciso dall’utente stesso.
- Rimuove da P un numero al più n di oggetti, e visualizza tali oggetti. Il numero n è deciso dall’utente: se n è minore o uguale al numero di oggetti in P, allora vengono rimossi da P esattamente n oggetti; se n è maggiore del numero di elementi di P, allora P viene svuotata.
- Visualizza il numero di oggetti effettivamente rimossi da P.
pop pila
vuota
push push push pop push
Cognome___________________ Nome ____________________ Matricola____________________
Questo compito è stato discusso e definito collegialmente dalla commissione di esame di Fondamenti di Informatica.
Note importanti:
• Sul dischetto che ti è stato dato trovi le classi ReadStream e LinkedList già compilate e pronte per l’uso.
• Salva le classi e le interfacce che devi definire sul dischetto.
• Scrivi Cognome, Nome e Matricola sia su questo foglio sia in un commento in testa alle classi che devi definire.
• Il dischetto va riconsegnato ben incartato in questo foglio
