LABORATORIO DI PROGRAMMAZIONE DI STRUTTURE DATI ESERCIZI SU PILE 10 Aprile 2002

Per questa esercitazione è necessario utilizzare il package lab2, in particolare la classe ArrayStack.

Risolvere i problemi elencati sotto NELL'ORDINE IN CUI SONO ELENCATI. Non si richiede di scrivere TUTTI i programmi, ma quelli risolti devono compilare correttamente e produrre i risultati richiesti.

Alla fine dell'esercitazione, copiare tutti i file prodotti in una cartella identificata dai cognomi dei componenti del gruppo, sotto serverPu/Esercizi/Lez1004.

Siete invitati a completare (alcuni de)gli esercizi fuori dall'orario di esercitazione, soprattutto se avete trovato serie difficoltà a svolgerli. Potete mandare l'eventuale completamento all'indirizzo guerrini@disi.unige.it.

Esercizio 1

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.

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

Esercizio 3

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
        */
        Stackswap ( ) ;
}

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.

Esercizio 4

Si scriva una classe RemoveStack contentente il metodo statico remove:

import lab2.*;

class RemoveStack {
    static int remove ( Stack s, Object o ){
    // da completare
   }
}

Il metodo remove toglie della pila ricevuta in input tutte le occorrenze dell'oggetto o, restituendo il numero di elementi cancellati. Il metodo deve alterare la pila ricevuta in input.
Per testare la classe RemoveStack, si compili ed esegua la classe UseRemoveStack. L'output deve essere ESATTAMENTE il seguente:

Stato della pila prima di 'remove 5':
7 6 5 4 3 2 1 7 6 5 4 3 2 1
Numero occorrenze trovate:2
Stato della pila dopo di 'remove 5':
7 6 4 3 2 1 7 6 4 3 2 1

Stato della pila prima di 'remove 12':
9 8 7 6 5 4 3 2 1
Numero occorrenze trovate:0
Stato della pila dopo di 'remove 12':
9 8 7 6 5 4 3 2 1

ALTRI ESERCIZI SULL'USO DELLE PILE:

Si vuole stampare il contenuto di una pila senza distruggerla, e usando solo operazioni pop e push. Scrivere un programma StampaPila per ottenere questo risultato.

Una parola o una frase palindroma può essere letta indifferentemente da sinistra a destra o da destra a sinistra (ignorando spazi e punteggiatura). Scrivere un metodo booleano isPalindroma(String input) che controlli se una data stringa è palindroma utilizzando una pila, e provarlo con un semplice programma di verifica.

Scrivere un metodo ordinaPila(Stack input) che ordina in senso crescente gli elementi della pila specificata nel parametro usando un'altra pila ed alcune variabili di appoggio, e provarlo con un semplice programma di verifica.