Aniello Murano » 6.Esercitazione di Laboratorio su Stack e Code

Esercizio: Prima parte

Si implementino in Linguaggio C una libreria per la gestione di uno Stack che possa contenere al più MAX elementi.

Si implementino in Linguaggio C una libreria per la gestione di una Coda che possa contenere al più MAX elementi.

Esercizio: Seconda parte

Si implementi inoltre una libreria in linguaggio C per la gestione di una coda di MAX elementi utilizzando la libreria per Stack precedentemente implemen-tata.

In particolare, questa libreria deve prescindere “il più possibile” dal modo in cui sono stati implementati gli stack.

Discutere sulle eventuali cambiamenti di complessità di dequeue e enqueue in questa nuova implementa-zione rispetto alle implementazioni viste nella lezione precedente.

Una Possibile Soluzione al II esercizio

Siano H e T sue Stack tali che la coda sia il risultato della concatenazione dello Stack H (partendo dal Top al Bottom) con lo Stack T (dal Bottom al Top).

Nella situazione iniziale, tutti gli elementi sono posti nello Stack H dove l’elemento al Top è la testa (Head) della coda, mentre quello al Bottom rappresenta la fine della coda (Tail).

Quando H è vuoto allora si svuota il rewerse di T in H. In dettaglio, per ogni elemento di T, si farà il Pop in T e il Push in H, fino a quando T non diventa vuoto.

Per cancellare un elemento dalla coda, si farà un POP dallo stack H, il quale non sarà mai vuoto a meno che l’intera coda non diventi vuota.

Per inserire un elemento nella coda si fa un Push nello Stack T.

Esercizio III parte

Scrivere un programma in linguaggio C per la gestione di code che possa funzionare indipendentemente da quale delle due librerie precedentemente definite venga utilizzata.

Attenzione: L’implementazione deve avvenire modificando “al minimo” il main() già implementato per la gestione delle code visto nella precedente lezione.

Domanda: Quante volte ciascun elemento sarà oggetto di un Push e di un Pop prima di lasciare la coda?

L’esercizio completo va consegnato via mail al tutor entro 5 giorni lavorativi allegando un breve documentazione (1-2 pagine).