Noi presenteremo, a titolo di esempio, due possibili implementazioni di uno
stack: StackL
tramite una lista semplice, StackA
tramite un
array dinamico; i nostri stack saranno di tipo molto semplice, consentendo
essenzialmente le tre operazioni fondamentali su descritte. Entrambe,
ovviamente, saranno implementate con una classe template. Visto che
le funzioni costruttore di copia e sovrapposizione dell'operatore di
assegnamento sono formalmente identiche alle corrispodenti funzioni della
classe Lista
, eviteremo di ripeterle; esse saranno pertante dichiarate
private, in maniera tale da inibire un uso improprio da parte
dell'utilizzatore della classe.
// stackl.h // classe rappresentante uno stack // implementato tramite una lista semplice #ifndef _STACK_L_H_ #define _STACK_L_H_ #include <iostream.h> template<class T> class StackL { public: StackL (bool Possiede = true) { possiede = Possiede; testa = 0; } ~StackL (); bool possesso () const { return possiede; } T* peek () const; T* pop (); T* push (T* nuovo_oggetto); StackL& operator+= (T* nuovo_oggetto) { push(nuovo_oggetto); return *this; } private: StackL (const StackL&); const StackL operator= (const StackL&); struct elem { elem* next; T* oggetto; elem (T* Oggetto, elem* Next = 0) { oggetto = Oggetto; next = Next; } }; elem* testa; bool possiede; }; template<class T> StackL<T>::~StackL () { if (testa != 0) { for (elem* p = testa; p != 0; p = testa) { testa = p->next; if (possiede == true) delete p->oggetto; delete p; } } } template<class T> T* StackL<T>::peek () const { if (testa != 0) return testa->oggetto; return 0; } template<class T> T* StackL<T>::pop () { T* tmp = 0; if (testa != 0) { elem* p = testa; testa = testa->next; if (possiede == true) delete p->oggetto; else tmp = p->oggetto; delete p; } return tmp; } template<class T> T* StackL<T>::push (T* nuovo_oggetto) { testa = new elem (nuovo_oggetto, testa); return nuovo_oggetto; } #endif // _STACK_L_H_
Come si vede, la rappresentazione di uno stack tramite una lista semplice è
del tutto naturale: le funzioni di inserimento ed estrazioni corrispondono ad
operazioni effettuare sulla testa della lista e, per questo motivo, sono
semplici da realizzare e efficienti nella esecuzione. Un esempio di utilizzo
della classe StackL
è:
// ex11_2_1.cpp #include "stackl.h" void svuota(StackL<int>& s) { while (s.peek() != 0) cout << *s.pop() << "\n"; } void main() { StackL<int> s1 (false); s1.push(new int(4)); s1.push(new int(-1)); s1.push(new int(3)); s1 += new int(7); svuota(s1); }
output:
7
3
-1
4
Una struttura dati che può ugualmente rappresentare uno stack è l'array dinamico. Supponiamo di avere dunque il nostro vettore di puntatori; se dobbiamo effettuare un inserimento le operazioni che dobbiamo effettuare sono le seguenti: copia dell'intero vettore in uno temporaneo, eliminazione del vettore preeistente, allocazione di memoria per il nuovo vettore, copia degli elementi dal vettore temporaneo a quello definitivo; tali operazioni hanno un costo di esecuzione che, se lo stack è ``grande'', è non indifferente; un discorso del tutto analogo lo si può condurre per la rimozione di un elemento. Dunque utilizzare un array per rappresentare uno stack, nel quale le uniche operazioni sono l'inserimento e l'estrazione, sembra una strada poco agibile. In realtà possiamo allocare e deallocare memoria non una cella per volta, ma a blocchi: stabiliamo a nostra discrezione la dimensione di un blocco11.3 e, in un certo senso, quantizziamo le operazioni di inserimento ed estrazione. Supponiamo ad esempio di prendere blocchi di 5 celle; quando operiamo il primo pop allochiamo un array di 5 elementi, il quale permane fino al sesto pop, con il quale dovremo deallocare l'array di 5 elementi e allocarne uno di 10, e così via.
// stacka.h // classe rappresentante uno stack // implementato tramite un array dinamico #ifndef _STACK_A_H_ #define _STACK_A_H_ const int DIM_BLOCCO = 5; template<class T> class StackA { public: StackA (bool Possiede) { stack = 0; n_elem = 0; possiede = Possiede; } StackA (const StackA&); ~StackA (); unsigned int quanti () const { return n_elem; } T* peek () const; T* pop (); T* push (T* nuovo_oggetto); private: const StackA& operator= (const StackA&); T** stack; unsigned int n_elem; unsigned int allocati; bool possiede; }; template<class T> StackA<T>::StackA (const StackA& s) { possiede = false; n_elem = s.n_elem; allocati = s.allocati; if (n_elem != 0) { int i; // variabile contatore stack = new T*[allocati]; for (i = 0; i < n_elem; i++) stack[i] = s.stack[i]; // azzera i puntatori rimasti fluttuanti for (i = n_elem; i < allocati; i++) stack[i] = 0; } else stack = 0; } template<class T> StackA<T>::~StackA () { if (possiede == true) for (int i = 0; i < n_elem; i++) delete stack[i]; delete[] stack; } template<class T> T* StackA<T>::peek () const { if (n_elem > 0) return stack[n_elem - 1]; return 0; } template<class T> T* StackA<T>::pop () { T* tmp = 0; if (n_elem <= 0) return tmp; if (n_elem % DIM_BLOCCO == 1) { if (n_elem == 1) { if (possiede == true) delete stack[0]; else tmp = stack[0]; delete[] stack; stack = 0; allocati = 0; n_elem = 0; } else { allocati -= DIM_BLOCCO; T** stack2 = new T*[allocati]; for (int i = 0; i < allocati; i++) stack2[i] = stack[i]; if (possiede == true) delete stack[allocati]; else tmp = stack[n_elem - 1]; stack = stack2; n_elem--; } } else { if (possiede == true) delete stack[n_elem - 1]; else tmp = stack[n_elem - 1]; stack[n_elem - 1] = 0; n_elem--; } return tmp; } template<class T> T* StackA<T>::push (T* nuovo_oggetto) { if (n_elem == 0) { allocati = DIM_BLOCCO; stack = new T*[allocati]; for (int i = 0; i < allocati; i++) stack[i] = 0; stack[0] = nuovo_oggetto; n_elem = 1; } else if (n_elem % DIM_BLOCCO == 0) { allocati += DIM_BLOCCO; T** stack2 = new T*[allocati]; for (int i = 0; i < n_elem; i++) stack2[i] = stack[i]; n_elem++; stack2[n_elem - 1] = nuovo_oggetto; for (int j = n_elem; j < allocati; j++) stack2[j] = 0; stack = stack2; } else { n_elem++; stack[n_elem - 1] = nuovo_oggetto; } return nuovo_oggetto; } #endif // _STACK_A_H_
Un programma che mostri l'utilizzo di uno StackA
è il seguente:
// ex11_2_2.cpp #include "stacka.h" #include "stringa.h" #include <iostream.h> void stampa(const StackA<Stringa>& s) { StackA<Stringa> copia(s); while (copia.peek() != 0) cout << *copia.pop() << "\n"; } void main() { StackA<Stringa> s(false); s.push(new Stringa("BeOS")); s.push(new Stringa("FreeBSD")); s.push(new Stringa("IRIX")); s.push(new Stringa("Linux")); s.push(new Stringa("NetBSD")); s.push(new Stringa("QNX")); s.push(new Stringa("Solaris")); s.push(new Stringa("SunOS")); s.push(new Stringa("Windows NT")); s.pop(); stampa (s); }
output:
SunOS
Solaris
QNX
NetBSD
Linux
IRIX
FreeBSD
BeOS
Abbiamo presentato dunque due alternative per la realizzazione di uno stack; la domanda che facilmente sorge è la seguente: qual è la strada migliore? Dipende. Uno stack implementato con una lista ha una velocità di esecuzione indipendente dal numero di elementi in esso contenuti, mentre uno stack implementato con un array dinamico impiega un tempo decisamente minore quando non deve riallocare nuova memoria per il push o deallocarne per il pop; per questo motivo uno stack il cui numero di elementi si mantiene più o meno costante, dal momento della creazione fino alla distruzione, è meglio rappresentabile con un array, mentre in generale è preferibile la struttura a lista.
CoseDaFare
, avente le seguenti funzioni
membro:
CoseDaFare ()
: costruttore default che inizializza un elenco
vuoto di compiti da svolgere;CoseDaFare (const CoseDaFare&)
: costruttore di copia;~CoseDaFare ()
: distruttore;aggiungiCompito (Stringa s)
: funzione che aggiunge il compito
s
all'elenco di compiti da svolgere;compitoEseguito ()
: funzione che permette di eliminare l'ultimo
compito svolto in ordine temporale;compitiEseguiti (unsigned int n)
: funzione che elimina gli ultimi
n
compiti in ordine temporale dall'elenco;numeroCompiti () const
: funzione che restituisce il numero di
commissioni da effettuare;ultimoCompito () const
: funzione che restituisce una
Stringa
contenente il primo compito da svolgere;operator Stringa () const
: operatore di conversione dell'oggetto
*
this in una Stringa
contenente l'elenco di
tutti i compiti da svolgere in ordine cronologico, separati tramite
il carattere `-
';