1. Strutture dati: Stack Un'introduzione (soft) alle variabili dinamiche

2. Cos' uno stack? Una struttura dati (astratta) di tipo LIFO (Last In First Out) Ovvero, I dati sono estratti in modo inverso rispetto all'ordine di inserimento Quindi esattamente come una pila di libri, o di altri oggettiNovembre 20132 3. Struttura Lo stack una struttura estremamente semplice Dotato di poche operazioni: inserimento di un oggetto nello stack ed estrazione di un oggetto dallo stack Opzionalmente si possono inserire altre funzionalit di supporto, per esempio per controllare se lo stack vuoto oppure no.Novembre 20133 4. Struttura Le operazioni di inserimento ed estrazione sono chiamate classicamente push e pop. Lo stack una struttura informatica FONDAMENTALE. E' usato infatti per (livello macchina): chiamate a funzioni Ricorsione Risoluzione di espressioni ...Novembre 20134 5. Schema UMLNovembre 20135 6. Possibile scheletro di implementazione abstractpublicclassStack{ abstractpublicObjectpop(); abstractpublicvoidpush(Object obj); abstractpublicbooleanisEmpty(); }Novembre 20136 7. Classe... astratta? Una classe astratta una classe che non si implementa direttamente, ma nella quale si dichiarano tutti i metodi che si vogliono implementare nella classe vera E' una classe che non si pu utilizzare direttamente, ma deve essere implementata tramite sottoclassi. Ricorda un po' le dichiarazioni delle funzioni in C/C++ (ma non troppo)Novembre 20137 8. E allora? Sono possibili due implementazioniNovembre 20138 9. Implementazione statica In questo caso, occorre allocare in anticipo lo spazio da utilizzare (tipicamente un array, stimandone la dimensione) Una variabile (tipicamente chiamata top) punta all'elemento dell'array nel quale avverr il prossimo inserimento.Novembre 20139 10. Implementazione statica (1/2) publicclassStackStaticoextendsStack{ publicstaticfinalintSIZE=100; privateinttop; privateObjectarr[]; StackStatico(){arr=newObject[SIZE]; top=0;}; publicObjectpop(){ if(isEmpty())returnnull; returnarr[top];};op());}Novembre 201310 11. Implementazione statica (2/2) publicclassStackStaticoextendsStack{ publicvoidpush(Objectobj){ arr[top++]=obj; } publicbooleanisEmpty(){ returntop==0; }; }Novembre 201311 12. Stack statico: programma di esempio publicstaticvoidmain(Stringargs[]){ StackStaticos=newStackStatico(); s.push(newInteger(83)); s.push(newInteger(12)); s.push(newInteger(67)); while(!s.isEmpty()){ System.out.println(s.pop()); } }Novembre 201312 13. Problema Obbligo di definire le dimensioni massime possibilit di eccedere le dimensioni stabilite (stack overflow) se la nostra stima troppo bassa. spreco di memoria, se la nostra stima troppo altaNovembre 201313 14. Alternativa? Si! Possiamo implementare lo stack in modo dinamico, cio utilizzando quella parte di memoria RAM che non utilizzata da nessun processo ed a disposizione (tale memoria chiamata memoria heap, o mucchio di memoria) Utilizzeremo cos solo la memoria che ci serve (o quasi)Novembre 2013 15. La struttura dell'oggetto Per farlo, dovremo utilizzare un oggetto molto diverso, formato da due attributi il campo informativo (dato) che contiene l'oggetto un puntatore la seconda un puntatore che punta all'elemento successivo (idealmente, una freccia)Novembre 201315 16. Novembre 201316 17. La strutturapublicclassStackDinamico{ privateObjectobj; privateStackDinamiconext; publicStackDinamico(){}; publicObjectpop(){}; publicvoidpush(Objecto){} publicbooleanisEmpty(){}; }Novembre 201317 18. Inizializzazione Dovremo sempre avere modo di recuperare il primo elemento dello stack: chiameremo top la variabile che punta all'elemento in cima allo stack; Tale variabile sar nel main (e la chiameremo s) s=newStackDinamico();Novembre 201318 19. Graficamente... s=new StackDinamico(); MEMORIA HEAPs tNovembre 201319 20. Questo elemento serve solo a segnare la fine dello stack, e non contiene oggetti. E' gestito dal costruttoreNovembre 201320 21. Inizializzazione In sostanza, l'inizializzazione gestita totalmente dal costruttore, che dovr fare due cose: Settare a null il puntatore all'elemento successivo Settare a null il puntatore al dato (non ci sono dati, infatti e in questo primo elemento non ci saranno mai.)Novembre 201321 22. Inserimento di un elemento (PUSH) Per inserire un elemento nello stack, dobbiamo utilizzare il metodo push(). Al suo interno, dovremo creare 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 preesistente;Novembre 201322 23. Graficamente... StackDinamico t=new StackDinamico(); MEMORIA HEAPs tNovembre 201323 24. Graficamente... t.obj=o; // object un Integer con valore 83 MEMORIA HEAPs tNovembre 20138324 25. Graficamente... t.next=s.next; MEMORIA HEAPs tNovembre 20138325 26. Graficamente... s.next=t; MEMORIA HEAPs tNovembre 20138326 27. Graficamente... Ripetiamo il codice, ma questa volta inseriamo 12 MEMORIA HEAPs tNovembre 20138327 28. Graficamente... t=new StackDinamico(); MEMORIA HEAPs tNovembre 20138328 29. Graficamente... t.o=object;//object un Integer con valore 12 MEMORIA HEAPs t83 12Novembre 201329 30. Graficamente... t.next=s.next; MEMORIA HEAPs t83 12Novembre 201330 31. Graficamente... s.next=t; MEMORIA HEAPs t83 12Novembre 201331 32. Eliminazione di un elemento (POP) Come funziona il metodo pop()? Ancora pi semplice. Stacchiamo il primo elemento (se esiste) dal resto dello stack, assegnandolo alla variabile t Andiamo avanti di un posto Restituiamo l'oggetto contenuto Poniamo t=null (opzionale). Privo di riferimenti, la memoria allocata torna disponibile. (In C/C++ va deallocata manualmente)Novembre 201332 33. Graficamente...MEMORIA HEAPs t83 12Novembre 201333 34. Graficamente... if (s.next==null) return null; MEMORIA HEAPs t83 12Novembre 201334 35. Graficamente... t=s; MEMORIA HEAPs t83 12Novembre 201335 36. Graficamente... s=s.next; MEMORIA HEAPs t83 12Novembre 201336 37. Importante! L'assegnazione di puntatori significa: puntano allo MEMORIA HEAP stesso oggetto s t83 12Novembre 201337 38. Importante! return t.o;//restituisce l'oggetto MEMORIA HEAPs t83out12Novembre 201338 39. Importante! Al termine del metodo, la variabile t scompare MEMORIA HEAPs t83 12Novembre 201339 40. Importante! Al termine del metodo, la variabile t scompare MEMORIA HEAPs t83 12Novembre 201340 41. Importante! Priva di riferimenti, la memoria torna nell'heap MEMORIA HEAPs 83Novembre 201341 42. Confronto tra le due implementazioniNovembre 201342 43. Migliorabile? Certamente si... Non permette di osservare il dato nello stack senza toglierlo Non sappiamo quanti elementi contiene Altri miglioramenti, al vostro buon cuoreNovembre 201343 44. Migliorabile?Realizzate quindi un programma che inserisca diversi oggetti nello stack e li estragga. Implementate ENTRAMBE le versioni (statiche e dinamiche) dello stack, con la stessa interfaccia pubblica. Il programma di prova deve funzionare in modo identico con le due implementazioni.Novembre 201344 45. BUON LAVORONovembre 201345