1

FONDAMENTI DI INFORMATICA IIIngegneria Gestionale

a.a. 2001-2002 - 4° Ciclo

Pile e Code

2

Pile e Code

Le Pile

Le Pile (o Stack) sono liste concatenate sulle quali i nuovi nodi possono essere aggiunti o rimossi soltanto dalla sua testa. Una struttura di questo tipo viene detta Last In First Out (LIFO), poiché l’ultimo nodo aggiunto è anche il primo ad essere rimosso.

Operazioni per le pile

Push: crea un nodo in cui memorizza i dati passati dalla funzione chiamante e lo posiziona alla testa della pila.

Pop: rimuove un nodo dalla testa della pila, acquisisce i dati in esso contenuti, rilascia la memoria allocata dal nodo estratto e restituisce il valore booleano true se l’operazione è andata a buon fine, altrimenti false.

3

Pile e Code

Utilizzo delle pile

Sono fondamentali, sotto il controllo del sistema operativo, per l’esecuzione della corretta sequenza delle operazioni nel corso di un programma. Un esempio è l’utilizzo per tenere traccia delle chiamate di funzione memorizzando l’indirizzo di ritorno della funzione chiamante.

____________________FunzioneA()__________________________________________________

Programma

Addr1 __________ FunzioneB()____________________Return

FunzioneA

Addr2

______________________________Return

FunzioneB

push(Addr1)push(Addr2)

pop(Addr2)pop(Addr1)

4

Pile e CodeEsempio per le pile

// Stack class template definition// Derived from class List#ifndef STACK_H#define STACK_H#include "list.h"

template< class STACKTYPE >class Stack : private List< STACKTYPE > {public: void push( const STACKTYPE &d ) { insertAtFront( d ); } bool pop( STACKTYPE &d ) { return removeFromFront( d ); } bool isStackEmpty() const { return isEmpty(); } void printStack() const { print(); }};

#endif

5

Pile e Code// Driver to test the template Stack class#include <iostream>#include "stack.h"using std::endl;

int main(){ Stack< int > intStack; int popInteger, i; cout << "processing an integer Stack" << endl;

for ( i = 0; i < 4; i++ ) { intStack.push( i ); intStack.printStack();}

while ( !intStack.isStackEmpty() ) { intStack.pop( popInteger ); cout << popInteger << " popped from stack" << endl; intStack.printStack();}

6

Pile e Code

Stack< double > doubleStack; double val = 1.1, popdouble; cout << "processing a double Stack" << endl;

for ( i = 0; i < 4; i++ ) { doubleStack.push( val ); doubleStack.printStack(); val += 1.1; }

while ( !doubleStack.isStackEmpty() ) { doubleStack.pop( popdouble ); cout << popdouble << " popped from stack" << endl; doubleStack.printStack(); } return 0;}

7

Pile e Code

processing an integer Stack

The list is: 0

The list is: 1 0

The list is: 2 1 0

The list is: 3 2 1 0

3 popped from stack

The list is: 2 1 0

2 popped from stack

The list is: 1 0

1 popped from stack

The list is: 0

0 popped from stack

The list is empty

8

Pile e Codeprocessing a double Stack

The list is: 1.1

The list is: 2.2 1.1

The list is: 3.3 2.2 1.1

The list is: 4.4 3.3 2.2 1.1

4.4 popped from stack

The list is: 3.3 2.2 1.1

3.3 popped from stack

The list is: 2.2 1.1

2.2 popped from stack

The list is: 1.1

1.1 popped from stack

The list is empty

All nodes destroyed

All nodes destroyed

9

Pile e Code

Le code

Le code sono liste concatenate nelle quali i nodi sono inseriti soltanto in coda e rimossi soltanto dalla testa. Una struttura di questo tipo viene detta First In First Out (FIFO), poiché il primo nodo aggiunto è anche il primo ad essere rimosso.

Operazioni per le pile

Enqueue: crea un nodo in cui memorizza i dati passati dalla funzione chiamante e lo posiziona alla fine della coda.

Dequeue: rimuove un nodo dalla testa della coda, acquisisce i dati in esso contenuti, rilascia la memoria allocata dal nodo estratto e restituisce il valore booleano true se l’operazione è andata a buon fine, altrimenti false.

10

Pile e Code

Utilizzo delle code

Le code, che hanno la proprietà di portare all’elaborazione i nodi che da più tempo sono stati inseriti (ossia i nodi più “vecchi”), hanno numerose applicazioni nell’ambito delle gestioni di un sistema operativo. Tra queste ricordiamo:

- Le code di elaborazione dei processi nei sistemi Time Sharing

- Le code di stampa.

- Le code di instradamento dei messaggi gestiti da un router …ecc.

11

Pile e CodeEsempio per le code

// Queue class template definition// Derived from class List#ifndef QUEUE_H#define QUEUE_H#include "list.h"

template< class QUEUETYPE >class Queue: private List< QUEUETYPE > {public: void enqueue( const QUEUETYPE &d ) { insertAtBack( d ); } bool dequeue( QUEUETYPE &d ) { return removeFromFront( d ); } bool isQueueEmpty() const { return isEmpty(); } void printQueue() const { print(); }};#endif

12

Pile e Code// Driver to test the template Queue class#include <iostream>#include "queue.h"using std::endl;

int main(){ Queue< int > intQueue; int dequeueInteger, i; cout << "processing an integer Queue" << endl;

for ( i = 0; i < 4; i++ ) { intQueue.enqueue( i ); intQueue.printQueue(); } while ( !intQueue.isQueueEmpty() ) { intQueue.dequeue( dequeueInteger ); cout << dequeueInteger << " dequeued" << endl; intQueue.printQueue(); }

13

Pile e Code Queue< double > doubleQueue; double val = 1.1, dequeuedouble;

cout << "processing a double Queue" << endl;

for ( i = 0; i < 4; i++ ) { doubleQueue.enqueue( val ); doubleQueue.printQueue(); val += 1.1; } while ( !doubleQueue.isQueueEmpty() ) { doubleQueue.dequeue( dequeuedouble ); cout << dequeuedouble << " dequeued" << endl; doubleQueue.printQueue(); } return 0;}

14

Pile e Codeprocessing an integer Queue

The list is: 0

The list is: 0 1

The list is: 0 1 2

The list is: 0 1 2 3

0 dequeued

The list is: 1 2 3

1 dequeued

The list is: 2 3

2 dequeued

The list is: 3

3 dequeued

The list is empty

15

Pile e Codeprocessing a float Queue

The list is: 1.1

The list is: 1.1 2.2

The list is: 1.1 2.2 3.3

The list is: 1.1 2.2 3.3 4.4

1.1 dequeued

The list is: 2.2 3.3 4.4

2.2 dequeued

The list is: 3.3 4.4

3.3 dequeued

The list is: 4.4

4.4 dequeued

The list is empty

All nodes destroyed

All nodes destroyed