Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
I corsi di Scienze Matematiche Fisiche e Naturali
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Ernesto Burattini » 23.Le classi pila e coda


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)

Le definizioni della classe sono di seguito:

Mostra codice

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.

Esempio di una classe pila (segue)

Esempio di una classe pila (segue)

Allegato: pile

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)

Di seguito definiamo la classe coda:

Mostra codice

Le Code (segue)

I metodi della classe coda sono:

Mostra codice

Le Code (segue)

Mostra codice

Le Code (segue)

Il main del programma code si articola come di seguito:

Mostra codice

Le Code (segue)

Mostra codice

Esercizio

Implementare le pile e le code invece che con una struttura ad array con delle liste legate.

Le Code (segue)

Mostra codice

Allegati: Code

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

Riprendiamo i metodi della classe pila.

Mostra codice

Classe pila (segue)

Avremo:

Mostra codice

Classe pila (segue)

Mostra codice

Classe pila (segue)

Mostra codice

Classe pila (segue)

Mostra codice

Classe pila (segue)

Mediante una procedura ricorsiva realizziamo il meccanismo descritto in precedenza.

Allegato: pile

I materiali di supporto della lezione

Code

pila_coda2

pileMat

pileS

pileSx

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion