MODULO 2:
“Strutture dati avanzate
e allocazione dinamica della memoria”
UD 3: “Le Liste”
UD 4: “Pile e Code”
UD 5: “Alberi e grafi”
MODULO 2:
“Strutture dati avanzate e allocazione
dinamica della memoria”
Questo modulo è proposto per una quarta
classe di un Istituto Tecnico Industriale ad
indirizzo Informatico.
L’obiettivo del modulo è di presentare:
 schemi significativi di organizzazione delle
informazioni;
 le regole operative per la manipolazione delle
strutture astratte di dati;
 i metodi di rappresentazione (memorizzazione)
delle strutture dati all’interno di un elaboratore.
UNITA’ DIDATTICA 4: Pile e code
A cura di Tania Barbagallo
Docente: Prof. D. Cantone
Classe di Concorso: 42A
Prerequisiti






Conoscenza della rappresentazione della
memoria di un calcolatore.
Conoscenze sicure del linguaggio C++.
Conoscenza e utilizzo delle strutture di controllo,
delle strutture di dati e delle funzioni.
Conoscenza dei puntatori.
Definizione delle classi con attributi e metodi.
Applicazione dei concetti della programmazione
ad oggetti nel linguaggio C++.
Competenze
Al termine di questa unità didattica lo studente
dovrà essere in grado di:
 definire le caratteristiche delle strutture
astratte ”pila” e “coda”;
 comprendere la differenza tra gestione statica
e gestione dinamica della memoria;
 implementare ”pila” e “coda” come strutture
dinamiche di dati;
 definire i modelli di classe.
Conoscenze
Al termine di questa unità didattica lo studente
dovrà possedere le seguenti conoscenze:
 strutture astratte di “pila” e “coda”;
 creazione dinamica di aree di memoria;
 gestione di pile e code;
 modelli di classe.
Abilità
Al termine di questa unità didattica lo
studente dovrà aver acquisito le
seguenti abilità:
 saper utilizzare i metodi per la gestione
della ”pila” ;
 saper utilizzare i metodi per la gestione
della “coda”.
Contenuti





Richiami sul concetto di struttura
astratta di dati.
La ”pila” come struttura statica.
La ”pila” come struttura dinamica.
La “coda” come struttura statica.
La “coda” come struttura dinamica.
Metodologia

Lezione frontale

Lezione dialogata

Brainstorming

Gruppi di lavoro
Strumenti

Libro di testo

Dispense fornite dal docente

Lavagna luminosa

Proiettore

Computer
Spazi

Aula

Laboratorio di Informatica
Verifiche

Questionari e test (strutturati e
semistrutturati).

Prove di laboratorio.

Interventi di vario genere.
Valutazione


Di tipo sommativo - in relazione al
raggiungimento degli obiettivi; sia in
termini di conoscenza dei contenuti, sia
in termini di acquisizione di competenze
e abilità specifiche.
Di tipo formativo - in relazione
all’impegno, costanza nello studio e
partecipazione.
Tempi

Lezione: 5 ore

Laboratorio: 3 ore

Verifica: 2 ore

Potenziamento e recupero: 2 ore
Cos’è una struttura astratta di
dati?
Struttura
astratta di
dati
Insiemi finiti di dati
tra i quali esistono
delle relazioni logiche.
Ha la funzione di un contenitore
che può essere riempito con dati di
volta in volta di tipo diverso.
Esempi di insiemi di dati correlati tra
loro da relazioni logiche

Elenco telefonico

Schedario di una biblioteca

Elenco degli alunni di una classe
Le tessere degli abbonati
di un garage di autovetture

Operazioni relative alle strutture dati
Accesso
a un elemento (o nodo) per leggere il
contenuto.
Ricerca
di un elemento con un determinato
contenuto.
Inserimento
Modifica
di un nuovo elemento.
del contenuto di un elemento tramite
la ricerca e l’accesso al nodo.
Cancellazione di un elemento senza alterare le
connessioni con gli altri nodi.
Struttura astratta di dati

Il processo di
realizzazione delle
strutture della
memoria del
calcolatore
prende il nome di
implementazione.
Struttura astratta di dati
Statica
Dinamica
Quando la dimensione è definita
nel momento di creazione della
struttura e non può essere
modificata.
Quando non è posto alcun vincolo
sulla dimensione della struttura.
Struttura astratta di dati
Lineare
Quando un nodo può avere al più un
nodo che lo precede e al più un
nodo che lo segue.
Non
lineare
Quando un nodo può avere due o
più nodi che lo precedono o lo
seguono.
Strutture informative
significative








Array
Tabelle
Lista lineare
Lista concatenata
Pila
Coda
Grafi
Alberi
La Pila
Una pila (detta anche STACK) è una struttura
dati lineare, i cui elementi possono essere inseriti
o estratti da un’unica estremità (LIFO).
LIFO è acronimo di Last In First Out, ovvero l’ultimo ad
entrare è il primo ad uscire.
Modalità d’impiego delle pile


La pila è un tipo di dato astratto che trova impiego
nell’organizzazione dei dati in memoria centrale in
molti sistemi operativi, nonché nella memorizzazione
degli indirizzi di ritorno delle funzioni.
Tale struttura è comune nei processi nei quali un
problema in corso d’esame viene lasciato
temporaneamente sospeso per affrontare un
sottoproblema che, a sua volta è lasciato in sospeso,
per affrontare un nuovo sottoproblema e così via
finché l’ultimo sottoproblema generato è messo in
testa alla pila dei vari sottoprogrammi da risolvere.
Operazioni sulle Pile
Le operazioni che si possono definire per una
pila (stack) sono:


Push: aggiunge nuovo elemento alla pila.
Pop: elimina l’elemento emergente dalla pila
viene ritornato l’elemento inserito da meno tempo!

TopElem: ritorna il valore del primo elemento della
pila, senza estrarlo.
IsEmpty: per verificare se la pila è vuota
(ritorna true se la pila non ha elementi).
IsFull: per verificare se la pila è piena.

Clear: per cancellare tutti i dati.


La pila come struttura statica


In alcuni casi le strutture LIFO hanno una
dimensione limitata, per cui è necessario
definire un valore massimo di elementi
inseribili.
Per l’implementazione di una pila servono:


uno spazio di memoria ordinato, dove inserire gli
elementi;
un indice per sapere quale è l’ultimo elemento
inserito.
La pila come struttura statica


L’indice deve tener conto di quanti elementi ci
sono nella pila.
Si utilizza un array per memorizzare gli
elementi e un numero intero che indica la
prima posizione libera dello stack.
Top = 0
Top=max
Pila vuota
Pila piena
top
5
5
4
3
2
1
Definizione della classe “pila”
public class Pila
{ private int top;
private final int MAX;
private int elem[];
private static final int MAXDEFAULT = 10;
public Pila()
{
this(MAXDEFAULT);
}
public Pila(int max)
{
top = 0;
MAX = max;
elem = new int[MAX];
}
…
}
Definizione della classe “pila”
public class Pila
{…
public bool IsFull()
{
return (top == MAX);
}
}
Procedura IsFull
public bool IsEmpty()
{
return (top == 0);
}
Procedura IsEmpty
public void Clear()
{
top = 0;
}
…
Procedura Clear
Definizione della procedura “TopElem”
public int TopElem()
{
if (IsEmpty())
return 0);
return elem[top-1] ;
}
E’ la procedura
che restituisce
il valore
dell’oggetto in
cima.
Definizione della procedura “Push”
public bool Push(int val)
{
if (IsFull())
return false);
elem[top++] = val;


return true;
}

Nella procedura di
inserimento bisogna
eseguire i seguenti passi:
verificare che la pila non
sia piena;
inserire l’elemento appena
passato;
spostare di una posizione
in alto l’indice top.
Definizione della procedura “Pop”
public int Pop()
{
if (IsEmpty())
return 0);
return elem[--top] ;
}



Nella procedura di
estrazione bisogna eseguire i
seguenti passi:
verificare che la pila non sia
vuota;
decrementare il valore
dell’indice;
leggere l’oggetto che sta in
cima alla pila.
Esercizio da proporre agli studenti

Dati in input una sequenza di numeri,
visualizzarla in ordine inverso. L’ultimo
numero della sequenza sia zero.
Descrizione del problema
I numeri della sequenza vengono acquisiti da tastiera uno ad uno ed
inseriti nella pila con l’operazione di Push, finché viene inserito il valore 0.
Successivamente in una ripetizione i numeri vengono estratti dalla pila con
l’operazione di Pop finché la pila è vuota.
Dati di input
Dati di output
Numeri della sequenza.
Numeri in ordine inverso all’inserimento.
Gestione statica e gestione dinamica
Gestione
statica
Gestione
dinamica
Le aree di memoria richieste dal
codice sorgente vengono
predisposte dal compilatore
attraverso la dichiarazione delle
variabili e allocate all’avviamento
del programma eseguibile.
Le istruzioni per l’allocazione di
nuova memoria vengono
richiamate durante l’esecuzione
del programma.
C++
:istruzioni relative alla memoria
New
Delete
Per l’allocazione di
nuova memoria.
Per la cancellazione
di un’area di
memoria.
Istruzione: New




Questa istruzione restituisce l’indirizzo di memoria.
Deve essere seguita dal tipo di dato a cui si vuole
allocare la memoria.
Si assegna il risultato di questa istruzione a un
puntatore.
Una volta esaurito lo spazio di memoria, new
restituisce un puntatore vuoto (0).
Esempio:
int *p=new int;
Istruzione: Delete


Questa istruzione permette di cancellare un
indirizzo di memoria.
E’ seguita dall’indirizzo di memoria da
deallocare, solitamente contenuto in un
puntatore.
Esempio:
delete p;
La pila come struttura dinamica
Push
dati
3
2
Si distingue una
parte di dati e una
parte di puntatori
di collegamento
1
(link).
dati
link
dati
link
dati
link
Pop
dati
Esempio “garage”
Creare la classe con i
relativi metodi per
gestire con
un’organizzazione
LIFO le tessere degli
abbonati di un garage
di autovetture. Il
numero di posti auto
del garage non è
conosciuto a priori.
Esempio “garage”
Organizzazione LIFO con gestione dinamica della memoria




Per realizzare tale struttura si deve definire l’elemento
della pila che contiene l’informazione, cioè il numero
dell’abbonato.
Quindi si predispongono le operazioni indispensabili a
garantire la connessione di questi dati tra loro.
La parte di collegamento deve consentire di unire tra
loro gli elementi della pila in modo da definire una
sequenza ordinata per i dati memorizzati, per poter
passare da un dato al successivo.
Il programma deve contenere una procedura di
eliminazione delle aree create dinamicamente in
modo da renderle disponibili ad altre applicazioni.
Esempio “garage” -
DESCRIZIONE DEGLI OGGETTI
La classe “Lista” serve per la definizione dei
dati da archiviare. I suoi attributi sono i
puntatori agli elementi della lista.
Un elemento della lista è
di tipo “Tessera” ed è
formato da:
 numero, che
rappresenta la parte dati;
 successiva, che
costituisce la parte dei
link.
Tessera
numero
*successiva
Lista
cima
coda
Inserisci
Posto
PostiOccupati
Algoritmo in pseudocodifica
INIZIO
crea oggetto garage di tipo Pila
aperto
true
MENTRE (aperto = true)
chiedi “Numero di tessera”, leggi (num_tessera)
inserisci num_tessera nella pila
chiedi “0=Chiuso, 1=Ingresso cliente”, leggi (aperto)
PER (i=0; i < numero posti occupati; i++)
scrivi (numero posto, numero cliente)
FINE
Esempio “garage” – Codice C++ (1)
#include <iostream.h>
class Tessera {
public:
int numero;
Tessera *successiva ;
}; // fine classe
La classe “Tessera”
è formata da una
parte contenente il
dato vero e
proprio, cioè il
numero
dell’abbonato e
una parte per il
collegamento con
l’elemento
successivo della
pila (*successiva) .
Esempio “garage” – Codice C++ (2)
class Lista {
Tessera *cima;
public:
Lista() : cima(0) {} // costruttore
~ Lista () {
// distruttore
Tessera *tessera = cima;
while (tessera) {
cima = tessera ->successiva;
delete tessera;
tessera = cima;
}
}
Il costruttore della
classe si preoccupa
di inizializzare gli
attributi.

Il distruttore libera
la memoria
svuotando la lista.

Esempio “garage” – Codice C++ (3)
void Inserisci (int n) {
Tessera *tessera = new Tessera;
tessera ->numero = n;
tessera ->successiva = cima;
cima = tessera;
}
La funzione
Inserisci serve
alla creazione di
ciascun elemento
della pila.
Il metodo Inserisci utilizza l’istruzione new per creare
un nuovo elemento della lista, inserisce i dati ricevuti
nell’apposita area e aggiorna il puntatore *cima in
modo da creare un collegamento con l’ultimo elemento
inserito.
Esempio “garage” – Codice C++ (4)
int posto (int n) {
int i;
Tessera *tessera = cima;
for (i=0; tessera!=0; i++) {
if (i==n)
return tessera->numero;
tessera = tessera->successiva;
}
return –1;
}
Il metodo “posto”
restituisce il
numero di tessera
del cliente che ha
parcheggiato al
posto n-esimo.
Esempio “garage” – Codice C++ (5)
int postiOccupati () {
int i;
Tessera *tessera = cima;
for (i=0; tessera != 0; i++)
tessera = tessera->successiva;
return i;
}
}; // fine classe
istream &operator>>(istream &s, bool &b) {
int r;
s>>r;
if (r) b = true; else b = false;
retun s;
}
Il metodo
“postiOccupati”
restituisce il
numero di posti
occupati.
Si utilizza l’overloading
dell’’operatore >>, per
acquisire da tastiera un
tipo di dato booleano,
indicante l’ingresso di
un cliente o la chiusura
del garage.
Esempio “garage” – Codice C++ (6)
void main()
{
bool aperto=true;
int num_tessera,i;
Lista garage;
while (aperto) {
cout << “Numero di tessera del cliente: “;
cin >> num_tessera;
garage.inserisci (num_tessera);
cout << “Immettere: 0= Chiuso, 1= Ingresso cliente\n“;
cin >> aperto;
}
cout << “Posto n.\tcliente\n”;
for (i=0; i < garage.postiOccupati(); i++)
if (garage.posto(i) ! = -1)
cout << “ “ << i << “\t\t “ garage.posto(i) <<endl;
}
Output prodotto
dall’esecuzione del programma
Numero di tessera del cliente: 10
Immettere 0=Chiuso, 1=Ingresso cliente
1

Numero di tessera del cliente: 20
Immettere 0=Chiuso, 1=Ingresso cliente
1

Numero di tessera del cliente: 30
Immettere 0=Chiuso, 1=Ingresso cliente
0

OUTPUT
INPUT
da
tastiera
Posto
Cliente
0
1
2
30
20
10
Osservazioni (1)
In questo caso il programma riporta
l’elenco dei clienti che occupano il
garage in ordine inverso rispetto al
loro ingresso in autorimessa.
Da notare che il programma è in grado di
gestire pile di qualsiasi dimensione
limitatamente alla capacità della memoria
del calcolatore impiegato nell’esecuzione.
Osservazioni (2)

La gestione delle pile vista finora
prevede la memorizzazione di un solo
dato (numero). In una soluzione più
generale si deve prevedere
un’opportuna struttura per la parte
dedicata ai dati.
Osservazioni (3)
typedef struct DatiTessera {
int numero;
char nome_cliente[30];
char targa_auto[30];
} DatiTessera;
class Tessera {
public:
// parte dei dati
DatiTessera dato;
// parte dei links
Tessera *successiva;
// costruttore
Tessera() : successiva(0) {}
};
In una soluzione più
generale,
nell’esempio
dell’autorimessa è
possibile introdurre
informazioni dati
relative ai clienti
prevedendo di
conseguenza
un’opportuna
struttura per la parte
dedicata ai dati .
Esempio “pila”
Scrivere il codice in
grado di gestire una
pila.
Verificarne il
funzionamento
utilizzando un
programma di collaudo
in cui la struttura dei
dati contenga un
intero e un reale.
“Soluzione per la
gestione di una
generica pila”
Esempio “pila” 



DESCRIZIONE DEGLI OGGETTI
In una gestione generica delle pile la classe
della lista dispone dei seguenti metodi:
Push() , che aggiunge un elemento alla pila;
Pop() , che estrae l’ultimo elemento inserito;
Size() , che restituisce il numero di elementi
presenti nella lista attraverso l’attributo conta.
~ Pila è il distruttore
definito per l’eliminazione
di eventuali dati rimasti in
memoria.
Nodo
dato
*successivo
Nodo
Pila
*cima
conta
Pila
~ Pila
Push
Pop
Size
Algoritmo in pseudocodifica
INIZIO
crea oggetto pila di tipo Pila
chiedi “numero intero”, leggi (dato.x)
MENTRE (dato.x<>0)
chiedi “numero reale”, leggi (dato.y)
inserisci dato nella pila
chiedi “numero intero”, leggi (dato.x)
chiedi “svuotamento della pila”, leggi (risp)
SE (risp==“si”)
MENTRE (dimensione della pila<>0)
estrai dato dalla pila
scrivi(dato.x, dato.y)
scrivi (“la memoria è stata liberata”)
FINE
Esempio “pila” – Codice C++ (1)
//STRUTTURA DEI DATI
typedef struct Dato {
int x;
float y;
} Dato;
const Dato Dato_NULLO = {0,0.0};
//PILA
#include <iostream.h>
class Nodo {
public:
Dato dato;
Nodo *successivo ;
Nodo (Dato d=Dato_NULLO, Nodo *n=0): dato(d), successivo(n) {}
}; // fine classe
Esempio “pila” – Codice C++ (2)
class Pila {
Nodo *cima;
double conta
public:
Pila() : cima(0), conta(0) {}
~ Pila () {while (Size() ) Pop();}
virtual bool Push(Dato &d) {
Nodo *p = new Nodo(d, cima);
if (!p) {
cerr<< “\nMemoria esaurita\n”;
return false;
}
cima = p;
conta++;
return true;
}
Esempio “pila” – Codice C++ (3)
virtual Dato Pop() {
Nodo *p = cima;
Dato d = Dato_NULLO;
if (p) {
d =p->dato;
cima = p ->successivo;
delete p;
conta--;
}
return d;
}
virtua double Size() { return conta;
}; // fine classe
}
Esempio “pila” – Codice C++ (4)
void main()
{
Pila pila;
Dato dato = Dato_NULLO;
char risposta;
cout << “Immissione di un intero e di un reale (0 = fine): “;
cin >> dato.x;
while (dato.x) {
cin >> dato.y;
if (!(pila.Push(dato)))
return ;
cout << “Immissione di un intero e di un reale (0 = fine): “;
cin >> dato.x;
} // fine while
…
Esempio “pila” – Codice C++ (5)
…
cout << endl;
cout << “Procedere allo svuotamento della pila (S/N) ? “;
cin >> risposta;
if risposta == ‘ S ’ ‫ ׀ ׀‬risposta == ‘ s ’) {
while (pila.Size() ) {
dato = pila.Pop();
cout << dato.x << “ “ << dato.y << endl;
}
cout << “La memoria è stata liberata” << endl;
}
}
Osservazioni (1)

Dopo la struttura dei dati è stata
definita la costante di annullamento del
loro contenuto Dato_NULLO.Tale
costante risulta molto utile per la
creazione di un costruttore con valori di
default:
Nodo(Dato d=Dato_NULLO, Nodo *n=0): dato(d), successivo(n) {}
Osservazioni (2)

Questo tipo di costruttore, che giustifica
l’impiego di una classe anziché di una
struttura per la definizione degli
elementi della lista, permette di
inizializzare un nuovo elemento durante
la sua creazione:
Nodo *p = new Nodo(d, cima);
Osservazioni (3)

Questo modo di inserire i dati nel nuovo
elemento della lista risulta più elegante
rispetto a quello tradizionale:
Nodo *p = new Nodo;
…
P->dato = d;
P->successivo = cima;
N. B. Gli attributi della classe sono
privati e i metodi sono tutti virtual.
La Coda
Le code (queue) sono strutture lineari i cui
elementi si inseriscono da un estremo e si
estraggono dall’altro (FIFO).
FIFO è acronimo di First In First Out, ovvero il primo entrato
è il primo ad uscire.
Modalità d’impiego delle code



Come si usa dire impilare o accatastare riferendosi
alle pile, si dice accodare riferendosi alle code.
Lavorando sui computer multiutente è frequente che
si accodino stampe o lavori nelle rispettive code: i
moduli software del sistema operativo che gestiscono
queste attività del sistema di elaborazione seguono
infatti il principio FIFO.
Così, ad esempio, se più utenti richiedono le stampe
sulla stessa stampante, esse vengono eseguite nello
stesso ordine con cui sono state richieste (coda di
SPOOL).
Operazioni sulle Code
Le operazioni che si possono definire per una
coda (queue) sono:


Enqueue (o Push): aggiunge nuovo elemento
alla coda.
Dequeue (o Pop): estrae un elemento dalla coda.
viene ritornato l’elemento inserito da più tempo!

FirstElem: ritorna il valore del primo elemento
della coda, senza estrarlo.
IsEmpty: per verificare se la coda è vuota
(ritorna true se la coda non ha elementi).
IsFull: per verificare se la coda è piena.

ClearQueue: per cancellare tutti i dati.


La coda come struttura statica


In alcuni casi anche le strutture FIFO
hanno una dimensione limitata, oltre la
quale non vengono più accettati
inserimenti.
Per definire una coda servono:


uno spazio di memoria ordinato, dove
inserire gli elementi;
due indici per sapere quali sono il primo e
l’ultimo elemento.
La coda – Estrazione\Inserimento


In seguito ad ogni estrazione, gli elementi rimanenti
vengono fatti avanzare di una posizione.
Per l’inserimento, invece, viene occupata l’ultima
posizione libera.
5
5
7
2
4
3
1
7
2
4
3
1
5
7
2
4
3
1
5
7
2
4
3
5
7
2
4
5
7
2
4
9
9
La coda come struttura statica


E’ possibile implementare una coda per
mezzo di un array.
Si tenga presente, però, che diventa
oneroso eseguire uno shift di tutti gli
elementi dopo ogni estrazione.
La coda come struttura statica
Per tale motivo conviene pensare
all’array come una struttura nella
tail
quale si passa dall’ultimo al primo
elemento in modo “circolare” (nel
quale l’elemento che segue l’ultimo è
il primo). E quindi occorre tener
presente due indici, head e tail, che
indicano il primo elemento e l’ultimo.
2
4
5
9
2
4
1
1
9
5
head
tail
3
head
8
3
8
La coda come struttura “circolare”

Il vantaggio di una simile struttura logica è
che non è necessario effettuare uno shift per
ogni inserimento, ma basta una sola
assegnazione (più la modifica della variabile
head).
Head viene incrementato per ogni operazione di Estrazione.
Tail viene incrementato per ogni operazione di Inserimento.
La coda come struttura “circolare”

Il valore di tail potrà raggiungere, ma non
superare il valore di head (a seguito di
operazioni di Inserimento ne segue il
riempimento della coda).
tail
head
La coda come struttura “circolare”

Analogamente, il valore di head non potrà
superare tail (dopo operazioni di Estrazione
ne segue lo svuotamento della coda).
head
tail
La coda come struttura “circolare”


Se però i due puntatori coincidono, dobbiamo
distinguere le condizioni di coda vuota o coda
con un solo elemento.
Si può decidere se:


lasciare sempre una casella vuota e far indicare a
tail la prima posizione vuota;
usare una variabile booleana per sapere se la coda
contiene elementi.
La coda come struttura “circolare”




Nel primo caso gli indici head e tail si possono
sovrapporre solo se la coda è vuota.
Head punta al primo elemento della coda.
Tail punta alla prima posizione libera dopo l’ultimo
elemento (tranne se la coda è vuota).
In ogni caso rimane sempre una casella vuota.
head
tail
x
x
x
x
x
x
x
x
x
La coda come struttura “circolare”




Nel secondo caso si ha:
Head punta alla prima posizione piena.
Tail punta all’ultima posizione piena (tranne se la coda
è vuota).
In tal caso se gli indici head e tail si sovrappongono la
coda può essere vuota o con un solo elemento.
Tramite una variabile booleana si possono distinguere
i due casi.
tail
head
head
tail
x
Empty=true
Empty=false
La coda come struttura “circolare”
Nella implementazione si considererà il
primo caso cioè si fa in modo che rimanga
sempre una casella vuota.
Head
Tail
punta al primo elemento della coda.
punta alla prima posizione libera dopo
l’ultimo elemento.
Qualunque operazione coinvolga gli indici deve
essere fatta modulo la dimensione dell’array.
Esempio (1)
Push(A)
Coda
vuota
head tail
head tail
Push(B)
Push(C)
A B
head tail
Push(D)
A B C
head
Pop(A)
A B C D
head
A
tail
tail
B C D
head
tail
Esempio (2)
Coda
Push(E)
Push(F)
B C D E
head
Pop(B)
piena
tail
tail
C D E F
B C D E F
Push(G)
head
G
C D E F
Coda
piena
tail
Pop(C)
head
G
tail head
D E F
tail
head
Pop(D)
G
E F
tail
head
Esempio (3)
Push(H)
G H
E F
tail
Pop(F)
G H
Pop(E)
head
tail
Pop(G)
head tail
Pop(H)
H
head tail
Coda
vuota
head tail
G H
F
head
Definizione della classe “coda”
public class Coda
{ private int head, tail;
private final int MAX;
private int elem[];
private static final int MAXDEFAULT = 10;
public Coda()
{
this(MAXDEFAULT);
}
public Coda(int max)
{
head = tail = 0;
MAX = max;
elem = new int[MAX];
}
…
}
Definizione della classe “coda”
public class Coda
{…
public bool IsFull()
{
return (head == (tail+1) % MAX);
}
public bool IsEmpty()
{
return (head == tail);
}
public void ClearQueue()
{
head = tail = 0;
}
…
}
Procedura IsFull
Procedura IsEmpty
Procedura
ClearQueue
Definizione della procedura “FirstElem”
public int FirstElem()
{
if (IsEmpty())
return 0);
return elem[head];
}
E’ la procedura
che restituisce
il valore del
primo
elemento .
Definizione della procedura“Push”
public bool Push(int val)
{ if IsFull())
return false;
elem[tail] = val;
tail = ++tail % MAX;
return true;
}



Nella procedura di
inserimento bisogna
eseguire i seguenti
passi:
verificare che la coda
non sia piena;
inserire l’elemento
appena passato;
aumentare di una
posizione l’indice tail
(modulo la dimensione
dell’array).
Definizione della procedura“Pop”
public int Pop()
{ if IsEmpty()
return 0;
int val = elem[headl];
head = ++head % MAX;
return val;
}



Nella procedura di
estrazione bisogna
eseguire i seguenti passi:
verificare che la coda non
sia vuota;
leggere l’oggetto che
occupa la prima
posizione;
aumentare di una
posizione il valore
dell’indice head (modulo
la dimensione dell’array).
Esercizio da proporre agli studenti

Dati in input una sequenza di numeri, si visualizzino gli ultimi
dati inseriti secondo l’ordine di inserimento. Per segnalare la fine
dell’inserimento, l’ultimo numero della sequenza sia 0.
Descrizione del problema
I numeri della sequenza vengono inseriti nella coda in seguito a quelli già
esistenti; se però nella coda tutti i posti sono occupati viene segnalato un
messaggio di indisponibilità perché la coda è piena: in questo caso il procedimento
forza un’operazione di estrazione all’inizio della coda, prima di inserire il nuovo
elemento. Al termine dell’elaborazione (con l’inserimento del numero 0),
svuotando la coda si ha il risultato desiderato.
Dati di input
Dati di output
Numeri della sequenza.
Gli ultimi numeri inseriti secondo l’ordine di inserimento.
La coda come struttura dinamica
Si distingue una
parte di dati e una
parte di puntatori
di collegamento
(link).
dati
1
2
3
Push
dati
link
dati
link
dati
link
Pop
dati
Struttura dati di una coda


La realizzazione di una coda generica prevede
la stessa struttura dati vista per la pila, cioè
una classe per la gestione della lista e una
classe per la definizione degli elementi.
In questo caso la lista contiene due puntatori
ai suoi elementi in modo da gestire il
caricamento, metodo Push(), e l’estrazione,
metodo Pop(), attraverso la modalità FIFO.
Esempio “coda”
Scrivere il codice in
grado di gestire una
coda.
Verificarne il
funzionamento
utilizzando un
programma di collaudo
in cui la struttura dei
dati contenga un intero
e un reale.
“Soluzione per la
gestione di una
generica coda”
Esempio “coda” 



DESCRIZIONE DEGLI OGGETTI
In una gestione generica delle code la classe
della lista dispone dei seguenti metodi:
Push() , che aggiunge un elemento alla coda;
Pop() , che estrae l’elemento inserito da più
tempo;
Size() , che restituisce il numero di elementi
presenti nella lista attraverso l’attributo conta.
~ Coda è il distruttore
definito per l’eliminazione
di eventuali dati rimasti in
memoria.
Nodo
dato
*successivo
Nodo
Coda
*cima
*coda
conta
Coda
~ Coda
Push
Pop
Size
Algoritmo in pseudocodifica
INIZIO
crea oggetto coda di tipo Coda
chiedi “numero intero”, leggi (dato.x)
MENTRE (dato.x<>0)
chiedi “numero reale”, leggi (dato.y)
inserisci dato nella coda
chiedi “numero intero”, leggi (dato.x)
chiedi “svuotamento della pila”, leggi (risp)
SE (risp==“si”)
MENTRE (dimensione della coda<>0
estrai dato dalla coda
scrivi(dato.x, dato.y)
scrivi (“la memoria è stata liberata”)
FINE
Esempio “coda” – Codice C++ (1)
//STRUTTURA DEI DATI
typedef struct Dato {
int x;
float y;
} Dato;
const Dato Dato_NULLO = {0,0.0};
//CODA
#include <iostream.h>
class Nodo {
public:
Dato dato;
Nodo *successivo ;
Nodo(Dato d=Dato_NULLO, Nodo *n=0): dato(d), successivo(n) {}
}; // fine classe
Esempio “coda” – Codice C++ (2)
class Coda {
Nodo *cima;
Nodo *coda;
double conta
public:
Coda() : cima(0), conta(0) {}
~ Coda () {while (Size() ) Pop();}
virtual bool Push(Dato &d) {
Nodo *p = new Nodo(d);
if (!p) {
cerr<< “\nMemoria esaurita\n”;
return false;
}
if (cima) coda->successivo =p; else cima=p;
coda = p;
conta++;
return true;
}
Esempio “coda” – Codice C++ (3)
virtual Dato Pop() {
Nodo *p = cima;
Dato d = Dato_NULLO;
if (p) {
d =p->dato;
cima = p ->successivo;
delete p;
conta--;
}
return d;
}
virtua double Size() { return conta;
}; // fine classe
}
Esempio “coda” – Codice C++ (4)
void main()
{
Coda coda;
Dato dato = Dato_NULLO;
char risposta;
cout << “Immissione di un intero e di un reale (0 = fine): “;
cin >> dato.x;
while (dato.x) {
cin >> dato.y;
if (!(coda.Push(dato)))
return ;
cout << “Immissione di un intero e di un reale (0 = fine): “;
cin >> dato.x;
} // fine while
…
Esempio “coda” – Codice C++ (5)
…
cout << endl;
cout << “Procedere allo svuotamento della coda (S/N) ? “;
cin >> risposta;
if risposta == ‘ S ’ ‫ ׀ ׀‬risposta == ‘ s ’) {
while (coda.Size() ) {
dato = coda.Pop();
cout << dato.x << “ “ << dato.y << endl;
}
cout << “La memoria è stata liberata” << endl;
}
}
Osservazioni


La gestione di una coda richiede una
particolare attenzione per l’implementazione
per l’inserimento di nuovi elementi.
La struttura dell’elemento che è
rappresentato dalla classe Nodo, il metodo di
estrazione Pop() e il metodo che restituisce la
dimensione della lista Size() , rimangono
invece invariati.
Si può pensare di derivare la classe Coda
dalla classe Pila
class Coda : public Pila {
Nodo *coda;
double conta
public:
Coda() : Pila(), coda(0) {}
virtual bool Push(Dato &d) {
Nodo *p = new Nodo(d);
if (!p) {
cerr<< “\nMemoria esaurita\n”;
return false;
}
if (cima) coda->successivo =p; else cima=p;
coda = p;
conta++;
return true;
}
}; // fine classe
Il distruttore
della classe
derivata viene
omesso in quanto
la lista viene
svuotata dal
distruttore della
classe di base.
 La cima della pila
non potrà più
essere di tipo
private.

FINE