1. ADT Stack Implementazione tramite variabili dinamiche

2. Perch?

L'implementazione con array (sia essa dinamica o statica) ci obbliga a allocare in anticipo la memoria.

3. Con l'implementazione a lista, utilizzeremosolola memoria che ci serve (o quasi) 4. La struttura

Per realizzare la cosa, utilizzeremo una struttura formata da due parti; la prima un campo informativo (dato) che contiene, in questo esempio, un intero; la seconda un puntatore che punta all'elemento successivo

5. Dovremo sempre avere modo di recuperare il primo elemento dello stack: chiameremo s la variabile (di tipo puntatore) che punta all'elemento attualmente in cima allo stack; 6. La struttura typedef struct Stack{ int info; Stack *next; } //useremo due variabili, s & t Stack *s, *t; 7. Inizializzazione L'inizializzazione risulta piuttosto semplice: basta assegnare alla variabile s il valore NULL. Null una costante predefinita del C/C++ che segnala un puntatore che non punta a... nulla, appunto. Come tale molto utilizzata nei controlli.All'inizio il nostro stack vuoto, quindi: s = null; 8. Inserimento di un elemento (PUSH) Per inserire un valore nello stack, dapprima creiamo un nuovo elemento in una variabile di appoggio, poi questo nuovo elemento diverr il nuovo elemento pi in alto dello stack. Dopo aver inserito l'informazione, lo agganceremo allo stack; 9. Il codice //creo nuovo elemento t= (stack *)malloc(sizeof(stack)); //inserisco valore (in questo caso 63) t->dato=83; //aggancio il nuovo elemento t->succ=s; //aggiorno s, che punta al nuovo primo elemento s=t; 10. Graficamente...

s=NULL;

MEMORIA HEAP s t 11. Graficamente...

t= (stack *)malloc(sizeof(stack));

MEMORIA HEAP s t 12. Graficamente... MEMORIA HEAP

t->dato=83;

s t 83 13. Graficamente... MEMORIA HEAP

t->succ=s;

s t 83 14. Graficamente... MEMORIA HEAP

s=t;

s t 83 15. Graficamente... MEMORIA HEAP

Ripetiamo il codice, ma questa volta inseriamo 12

s t 83 16. Graficamente...(x2) MEMORIA HEAP

t= (stack *)malloc(sizeof(stack));

s t 83 17. Graficamente...(x2) MEMORIA HEAP

t->dato=12

s t 83 12 18. Graficamente...(x2) MEMORIA HEAP

t->succ=s;

s t 83 12 19. Graficamente...(x2) MEMORIA HEAP

s=t;

s t 83 12 20. Eliminazione di un elemento (POP)

Occorre operare in modo inverso

21. Per prima cosa preleviamo il dato (dopo aver controllato se lo stack non vuoto) e lo assegnamo a una variabile (la useremo nel main) 22. Salviamo il vecchio valore di s in t 23. Poi cambiamo s in modo che punti all'elemento successivo 24. Infine, liberiamo lo spazio allocato in memoria 25. Il codice //recupero dato out=s->dato //salvo il puntatore al dato da eliminare t=s; //lo stack passa all'elemento successivo s=s->succ; //libero la memoriafree(t); 26. Graficamente...(x2) MEMORIA HEAP

out=s->dato;

s t 83 12 out 12 27. Graficamente...(x2) MEMORIA HEAP

t=s;

s t 83 12 28. Graficamente...(x2) MEMORIA HEAP

s=s->succ;

s t 83 12 29. Graficamente...(x2) MEMORIA HEAP

free(t);

s t 83 30. Deinizializzazione

Prima di chiudere il programma, occorre essere certi che lo stack sia vuoto, se no occorre farlo manualmente.

31. Migliorabile?

Certamente si...poich questo codice lascia alquanto a desiderare...

Non fa alcun tipo di controllo

32. Non permette di osservare il dato nello stack senza toglierlo 33. Non compatibile con l'interfaccia che abbiamo definito in precedenza 34. QUESTI SONO I PROBLEMI DA RISOLVERE! BUON LAVORO