LABORATORIO DI PROGRAMMAZIONE DI STRUTTURE DATI
ESERCIZI SU CODE
17 Aprile 2002

 

Per questa esercitazione è necessario utilizzare il package lab2.
 

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 ReverseQ {
    /**
    * Restituisce una nuova coda, che contiene i valori 
    * della coda passata per argomento, ma in ordine inverso. 
    * La coda originale non viene modificata. 
    */
    public static Queue reverse( Queue input ) {
        // DA DEFINIRE
    }
}

Esercizio 2

    Si fornisca una implementazione della seguente classe astratta:
 
import lab2.*;
import lab2.Exceptions.*;

abstract class IntegerQueueInterface {
    protected Queue prior ;

    public IntegerQueueInterface( Queue input ) {
        prior = input ;
    }

    /**
     * Restituisce il più alto elemento della coda, assumendo
     * che gli elementi contenuti siano istanze di Integer.
     * Lancia una EmptyQueueException se 'prior' è null
     * oppure è la coda vuota.
     */
    abstract Integer maxDequeue( ) ;

    /**
     * Ordina il contenuto della coda, assumendo che
     * gli elementi contenuti siano istanze di Integer
     */
     abstract void ordina( ) ;
}

Esercizio 3

Si fornisca una realizzazione ListQueue dell'interfaccia Queue utilizzando una lista concatenata per memorizzare gli elementi di una coda. Come per la classe ListStack, i nodi della lista saranno istanze della classe ListNode. Poiché enqueue e dequeue lavorano sulle estremità opposte della coda, sarà opportuno avere in ogni istanza di  ListQueue due puntatori alla lista: uno al primo elemento e uno all'ultimo.

Esercizio 4

Si consideri la seguente interfaccia
 
import lab2.*;
public interface ReverseQueue extends Queue {
    /**
    * Rovescia il contenuto della coda
    * @return  una nuova coda, che contiene i valori della coda
    * che esegue il metodo, ma in ordine inverso
    */
    Queue reverse ( ) ;
}

dove il metodo introdotto rovescia il contenuto di una coda, senza alterare la coda originale. 
Si definisca una classe ArrayReverseQueue, che estenda ArrayQueue ed implementi l'interfaccia.

Esercizio 5

Si consideri la seguente interfaccia
 
import lab2.*;
public interface IntegerQueue extends Queue {
    /**
    * Restituisce il massimo elemento della coda, assumendo
    * che gli elementi contenuti siano istanze di Integer
    */
    Integer maxDequeue ( ) ;

    /**
    * Ordina il contenuto della coda, assumendo che
    * gli elementi contenuti siano istanze di Integer
    */
    void ordina ( ) ;
}

dove i metodi introdotti devono rispettivamente cercare il massimo fra gli elementi presenti nella coda (sollevando l'eccezione EmptyQueueException nel caso la coda sia vuota), ed ordinare il contenuto di una coda, assumendo che gli elementi contenuti siano istanze di Integer.
Si definisca una classe ArrayIntegerQueue, che estenda ArrayQueue ed implementi l'interfaccia.

Esercizio 6

Si definisca una classe con la seguente struttura:
 
 

public class CloneQ {
    /**
     * Restituisce una copia della coda passata come parametro
     */
    public static Queue clone( Queue daClonare ) {
        // DA DEFINIRE
   
}