Lo stack: tipo di dato astratto e implementazione in Java
Download as ODP, PDF0 likes2,520 views
Una introduzione alle variabili dinamiche. Riealaborazione di un mio lavoro precedente, per嘆 scritto in java.
![Implementazione statica (1/2)
public油class油StackStatico油extends油Stack{
油油油油public油static油final油int油SIZE油=油100;
油油油油private油int油top;
油油油油private油Object油arr[];
油油油油StackStatico()油{arr=new油Object[SIZE];
油油油油油油油油top=0;};
油油油油public油Object油pop(){
油油油油油油油油if油(isEmpty())油return油null;
油油油油油油油油return油arr[足足top];油};op());油油}
Novembre 2013
10](https://image.slidesharecdn.com/stackoop-131102081609-phpapp02/85/Lo-stack-tipo-di-dato-astratto-e-implementazione-in-Java-10-320.jpg)
![Implementazione statica (2/2)
public油class油StackStatico油extends油Stack{
油油油油public油void油push(Object油obj)油{
油油油油油油油油arr[top++]=obj;
油油油油}
油油油油public油boolean油isEmpty()油{
油油油油油油油油return油top==0;
油油油油};
}
Novembre 2013
11](https://image.slidesharecdn.com/stackoop-131102081609-phpapp02/85/Lo-stack-tipo-di-dato-astratto-e-implementazione-in-Java-11-320.jpg)
![Stack statico: programma di esempio
public油static油void油main(String油args[])油{
油油油油油油油油StackStatico油s=new油StackStatico();
油油油油油油油油s.push(new油Integer(83));
油油油油油油油油s.push(new油Integer(12));
油油油油油油油油s.push(new油Integer(67));
油油油油油油油油while油(!s.isEmpty())油{
油油油油油油油油油油油油System.out.println(s.pop());
油油油油油油油油}
油油油油}
Novembre 2013
12](https://image.slidesharecdn.com/stackoop-131102081609-phpapp02/85/Lo-stack-tipo-di-dato-astratto-e-implementazione-in-Java-12-320.jpg)
More Related Content
Viewers also liked (15)
More from Marcello Missiroli (12)
Lo stack: tipo di dato astratto e implementazione in Java
- 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 oggetti Novembre 2013 2
- 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 2013 3
- 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 2013 4
- 6. Possibile scheletro di implementazione abstract油public油class油Stack油{ 油abstract油public油Object油pop(); 油abstract油public油void油push(Object油 obj); 油abstract油public油boolean油isEmpty()油; } Novembre 2013 6
- 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 2013 7
- 8. E allora? Sono possibili due implementazioni Novembre 2013 8
- 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 2013 9
- 12. Stack statico: programma di esempio public油static油void油main(String油args[])油{ 油油油油油油油油StackStatico油s=new油StackStatico(); 油油油油油油油油s.push(new油Integer(83)); 油油油油油油油油s.push(new油Integer(12)); 油油油油油油油油s.push(new油Integer(67)); 油油油油油油油油while油(!s.isEmpty())油{ 油油油油油油油油油油油油System.out.println(s.pop()); 油油油油油油油油} 油油油油} Novembre 2013 12
- 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 alta Novembre 2013 13
- 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 2013 15
- 16. Novembre 2013 16
- 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油=油new油StackDinamico(); Novembre 2013 18
- 20. Questo elemento serve solo a segnare la fine dello stack, e non contiene oggetti. E' gestito dal costruttore Novembre 2013 20
- 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 2013 21
- 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 2013 22
- 23. Graficamente... StackDinamico t=new StackDinamico(); MEMORIA HEAP s t Novembre 2013 23
- 24. Graficamente... t.obj=o; // object 竪 un Integer con valore 83 MEMORIA HEAP s t Novembre 2013 83 24
- 27. Graficamente... Ripetiamo il codice, ma questa volta inseriamo 12 MEMORIA HEAP s t Novembre 2013 83 27
- 29. Graficamente... t.o=object;//object 竪 un Integer con valore 12 MEMORIA HEAP s t 83 12 Novembre 2013 29
- 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 2013 32
- 34. Graficamente... if (s.next==null) return null; MEMORIA HEAP s t 83 12 Novembre 2013 34
- 37. Importante! L'assegnazione di puntatori significa: puntano allo MEMORIA HEAP stesso oggetto s t 83 12 Novembre 2013 37
- 38. Importante! return t.o;//restituisce l'oggetto MEMORIA HEAP s t 83 out 12 Novembre 2013 38
- 39. Importante! Al termine del metodo, la variabile t scompare MEMORIA HEAP s t 83 12 Novembre 2013 39
- 40. Importante! Al termine del metodo, la variabile t scompare MEMORIA HEAP s t 83 12 Novembre 2013 40
- 41. Importante! Priva di riferimenti, la memoria torna nell'heap MEMORIA HEAP s 83 Novembre 2013 41
- 42. Confronto tra le due implementazioni Novembre 2013 42
- 43. Migliorabile? Certamente si... Non permette di osservare il dato nello stack senza toglierlo Non sappiamo quanti elementi contiene Altri miglioramenti, al vostro buon cuore Novembre 2013 43
- 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 2013 44