// codal.h // classe rappresentate una coda // tramite una lista semplice con puntatore di coda #ifndef _CODA_L_H_ #define _CODA_L_H_ template<class T> class CodaL { public: CodaL (bool Possiede = true) { // costruttore default possiede = Possiede; primo = ultimo = 0; } ~CodaL (); T* first () const { return primo->oggetto; } T* last () const { return ultimo->oggetto; } T* pop (); T* push (T* nuovo_oggetto); bool vuota () const { if (primo == 0) return true; return false; } bool unitaria () const { if (primo == ultimo && primo != 0) return true; return false; } private: // il costruttore di copia e la sovrapposizione // dell'operatore di assegnamento sono formalmente // identici alle medesime funzioni per una lista // semplice con puntatore di coda, per cui // eviteremo di definirle; esse vengono dichiarate private // per evitare un loro uso improprio CodaL (const CodaL&); const CodaL& operator= (const CodaL&); struct elem { elem* next; T* oggetto; elem (T* Oggetto, elem* Next = 0) { oggetto = Oggetto; next = Next; } }; bool possiede; elem* primo; // puntatore al primo elemento della lista elem* ultimo; // puntatore all'ultimo }; template<class T> CodaL<T>::~CodaL () { if (!vuota()) { for (elem* p = primo; primo != 0; p = primo) { primo = primo->next; if (possiede == true) delete p->oggetto; delete p; } } } template<class T> T* CodaL<T>::pop () { T* tmp = 0; if (vuota()) ; else if (unitaria()) { if (possiede == true) delete primo->oggetto; else tmp = primo->oggetto; delete primo; primo = ultimo = 0; } else { elem* p = primo; primo = primo->next; if (possiede == true) delete p->oggetto; else tmp = p->oggetto; delete p; } return tmp; } template<class T> T* CodaL<T>::push (T* nuovo_oggetto) { if (vuota()) primo = ultimo = new elem(nuovo_oggetto); else ultimo = ultimo->next = new elem (nuovo_oggetto); return nuovo_oggetto; } #endif // _CODA_L_H_
Non c'è praticamente nulla di nuovo nella classe su presentata; un semplice esempio sull'utilizzo di essa è il seguente:
// ex11_3_1.cpp #include "codal.h" #include <iostream.h> // librerie per la generazione di numero casuali #include <stdlib.h> #include <time.h> void svuota(CodaL<double>& c) { while (!c.vuota()) cout << *c.pop() << "\n"; } void main() { CodaL<double> c(false); for (int i = 0; i < 5; i++) c.push(new double(double(rand()) / double(RAND_MAX))); *c.first() = -1.0; *c.last() = 1.0; svuota(c); }
esempio di output:
-1
0.394383
0.783099
0.79844
1
Si noti che, al contrario dello stack, la coda rispetta l'ordine di inserimento dei dati.
Una interessante implementazione alternativa di una coda potrebbe essere
quella di una ``coda limitata'', avente cioè un massimo numero di elementi
in essa contenuti. Un esempio di utilizzo di tale struttura potrebbe essere il
seguente: supponiamo di avere della memoria a disposizione, fisicamente
limitata, possiamo tenere una coda di elementi in memoria, in maniera tale da
eliminare automaticamente gli oggetti più ``vecchi'' una volta riempita la
coda, supponendo che essi siano obsoleti. A titolo di esempio, implementeremo
la classe CodaA
come una classe template con due gradi di
libertà: il tipo di dato immagazzinato (T
) e il massimo numero di
elementi contenuti nella coda (MAX
).
Siccome MAX
viene valutato a tempo di compilazione, possiamo
addirittura utilizzare un array non dinamico; si nota comunque che tale metodo
potrebbe risultare inefficiente nel caso si intenda costruire un gran numero
di code aventi un numero massimo di elementi sempre diverso: in tal caso
infatti il compilatore generebbe e compilerebbe una diversa classe per ogni
diverso MAX
. Tale problema si risolve facilmente utilizzando un array
dinamico e passando il massimo numero di elementi al costruttore.
// codaa.h // classe rappresentante una coda limitata // tramite un array #ifndef _CODA_A_H_ #define _CODA_A_H_ template<class T, unsigned int MAX> class CodaA { public: CodaA (bool Possiede = true); // tutti i membri sono non dinamici, per cui e` inutile // definire il cc, l'operatore = e il distruttore // CodaA (const CodaA&); // const CodaA& operator= (const CodaA&); // ~Coda (); T* primo () const; T* ultimo () const { if (indice == 0) return coda[MAX-1]; else return coda[indice - 1]; } T* push (T* nuovo_oggetto); unsigned int max () const { return MAX; } private: T* coda[MAX]; unsigned indice; // indice del primo elemento bool possiede; unsigned n_elem; // funzione interna che segnala quando l'array e` pieno bool pieno () const { if (n_elem >= MAX) return true; return false; } }; template<class T, unsigned int MAX> CodaA<T,MAX>::CodaA (bool Possiede) { possiede = Possiede; for (int i = 0; i < MAX; i++) coda[i] = 0; indice = 0; n_elem = 0; } template<class T, unsigned int MAX> T* CodaA<T,MAX>::primo () const { if (!pieno() || (indice == MAX - 1)) return coda[0]; return coda[indice]; } // attenzione: push restituisce un puntatore all'oggetto // che viene (eventualmente) estratto template<class T, unsigned int MAX> T* CodaA<T,MAX>::push (T* nuovo_oggetto) { T* tmp = 0; if (!pieno()) { if (indice == (MAX - 1)) { indice = 0; coda[MAX - 1] = nuovo_oggetto; } else { indice++; coda[indice - 1] = nuovo_oggetto; } n_elem++; coda[indice - 1] = nuovo_oggetto; return tmp; } else if (indice == (MAX - 1)) { if (possiede == true) delete coda[0]; else tmp = coda[MAX - 1]; indice = 0; coda[MAX - 1] = nuovo_oggetto; } else { if (possiede == true) delete coda[indice]; else tmp = coda[indice]; indice++; coda[indice - 1] = nuovo_oggetto; } return tmp; } #endif // _CODA_A_H_
La funzione pop()
non è stata implementata in quanto non necessaria:
una volta che la coda è piena sarà la stessa funzione push
a
estrarre i primi elementi inseriti; si noti che tale funzione restituisce un
puntatore all'oggetto estratto, non, come negli stack e nella CodaL
,
all'oggetto inserito.
Il seguente esempio mostra come si possa semplicemente utilizzare un oggetto
di tipo CodaA
:
// ex11_3_2.cpp #include "codaa.h" #include <iostream.h> void main() { CodaA<int, 5> c(false); for (int i = 1; i <= c.max(); i++) c.push(new int(i)); cout << "primo:\t" << *c.primo() << "\n"; cout << "ultimo:\t" << *c.ultimo() << "\n"; for (int i = 1; i <= c.max(); i++) cout << *c.push(new int(-i)) << "\n"; cout << "primo:\t" << *c.primo() << "\n"; cout << "ultimo:\t" << *c.ultimo() << "\n"; }
output:
primo: 1
ultimo: 5
1
2
3
4
5
primo: -1
ultimo: -5
CodaL
;
CodaA
utilizzando la variabile membro
max
come massimo numero di elementi contenuti, piuttosto
dell'argomento template MAX