Esempio di una classe pila
Ricordiamo che:
La pila o stack è una struttura astratta composta da più elementi omogenei.
Una pila è uno stack di dati con accessi del tipo LIFO (Last In First Out) per cui l’ultimo elemento inserito nella pila è anche il primo elemento che si può estrarre da esso.
L’aggiunta di un elemento alla pila viene detta operazione di push, mentre la rimozione dalla pila viene detta operazione di pop.
Vogliamo implementare una classe astratta chiamata pila i cui elementi sono numeri interi e la cui struttura è quella di un vettore.
Esempio di una classe pila (segue)
Aggiungiamo alla struttura descritta un intero che indichi la posizione attuale dell’elemento da rimuovere.
Indichiamo con items il vettore che contiene i componenti della pila (supposta omogenea), con top l’indice dell’elemento attuale, con push l’operazione di aggiungere oggetti e con pop quella di eliminarli.
Prima di analizzare l’oggetto pila, osserviamo che dobbiamo necessariamente determinare il numero massimo di elementi che possiamo gestire: indichiamo con Max tale valore che rappresenterà una costante globale (ad esempio Max=100).
I data-member della pila sono
int top;
int items[Max];
rigorosamente privati, mentre il costruttore dovrà inizialmente indicare che la pila è vuota ponendo
top = -1;
Esempio di una classe pila (segue)
In questo caso non è necessario un distruttore.
Per usufruire della classe pila abbiamo la necessità di implementare i seguenti metodi:
push che inserisce un oggetto della pila in cima;
pop che elimina l’elemento dalla cima;
cima che ne stampi semplicemente il valore senza eliminarlo;
vuota, funzione booleana che restituisca true se la pila è vuota, false altrimenti;
piena, funzione booleana che restituisca true se la pila è piena, false altrimenti;
stampa, mostra a video tutti gli elementi nello stesso ordine in cui sono stati immessi.
Esempio di una classe pila (segue)
Data la non eccessiva lunghezza della definizione della classe pila abbiamo ritenuto utile non spezzarla in due file, per cui utilizzeremo un solo file pilaMat.cpp in cui sono incluse sia le definizioni che le implementazioni dei vari metodi.
Esempio di una classe pila (segue)
push : se la pila non è piena allora, per inserire l’elemento e in cima, s’incrementa di una unità la variabile top e si pone items[top]←e; se la pila è piena si scrive “Pila piena”;
pop : se la pila non è vuota allora, per eliminare l’elemento dalla cima, si restituisce prima l’elemento e posto in cima e poi si decrementa la variabile top di una unità;
cima : se la pila non è vuota, stampa il valore items[top] senza eliminarlo;
vuota : restituisce il valore booleano del confronto top==-1;
piena: restituisce il valore booleano del confronto top==Max-1;
overload di <<: stampa tutti gli elementi della pila a partire da top decrescendo fino all’indice 0.
Le Code
- Una coda è una successione lineare di elementi, eventualmente anche vuota.
- Se gli elementi che compongono una coda sono tutti dello stesso tipo la coda è detta omogenea.
- Le operazioni elementari che possono esser effettuate su una coda sono: aggiungere un elemento, cancellare e/o estrarre un elemento.
Le Code (segue)
E’ necessario descrivere una coda in funzione della sua testa, della sua coda, degli oggetti in coda e del loro numero in ogni istante della computazione.
Le Code (segue)
In una coda l’elemento inserito per primo viene anche estratto per primo First In First Out (FIFO).
In una coda, se si adopera una struttura ad array, occorrerà distinguere tra un inizio o TESTA della coda (punto di estrazione e/o cancellazione di un elemento) ed una fine o CODA della coda (punto di inserimento di un nuovo elemento).
Sia Items[ ] un array in cui si collocano gli oggetti.
- Testa l’indice dell’array corrispondente alla testa,
- Coda l’indice corrispondente alla coda,
- Item l’oggetto da aggiungere.
Le Code (segue)
Possiamo descrivere una coda in funzione della sua testa, della sua coda, e del numero di oggetti in coda (InUse) in ogni istante della computazione utilizzando l’espressione
coda:=coda % Maxcoda + 1 (elimina elemento)
testa:=testa % Maxcoda + 1 (preleva elemento)
Ovviamente nel caso in cui InUse< Maxcoda possiamo adoperare entrambe le espressioni per aggiungere e levare, in caso contrario possiamo solo levare.
Le Code (segue)
Mostra codiceLe Code (segue)
Mostra codiceEsercizio
Implementare le pile e le code invece che con una struttura ad array con delle liste legate.
Costruzione e gestione di una coda utilizzando pile
Supponiamo di voler realizzare una meccanismo FIFO avendo a disposizione solo metodi per la gestione di pile (LIFO).
Possiamo immaginare di riempire una pila B e poi trasferire in una seconda pila A il contenuto della prima. Per il meccanismo LIFO gli ultimi arrivati, che sono in testa alla pila B verrano inseriti nella pila B nelle ultime posizioni, mentre I rpimi si troveranno in testa. In questa maniera dalla lista A potremo estrarre gli elementi secondo la strategia FIFO.
Classe pila (segue)
Mostra codiceClasse pila (segue)
Mostra codiceClasse pila (segue)
Mostra codiceClasse pila (segue)
Mediante una procedura ricorsiva realizziamo il meccanismo descritto in precedenza.
Allegato: pile
