Prima di addentrarci nella loro realizzazione dobbiamo ricordare che in Java le variabili di tipo non base sono in pratica dei riferimenti a zone di memoria in cui l'oggetto viene memorizzato. Questi riferimenti non sono però direttamente manipolabili come in altri linguaggi.
Proviamo a vedere...
TextField b = new TextField("pluto"); TextField a = new TextField("paperino"); String x; a=b; x = a.getText();
Quanto varrà la variabile x alla fine del frammento di programma sopra?
errore no, il programma è corretto "paperino"no,a=b
cambia l'oggetto riferito dalla variabile a
"pluto" giusto,
a=b
rende a
un riferimento allo stesso oggetto a cui si riferisce b
E che fine ha fatto l'oggetto (il TextField) che contiene la scritta "paperino"? È andato perso! La memoria occupata dall'oggetto verrà resa libera automaticamente da java (da una parte della JVM che si chiama garbage collector).
Le code
In pratica la coda viene realizzata come un insieme di blocchi concatenati tra loro chiamati nodi.
Nodo
L'elemento base viene chiamato Nodo e contiene una informazione (ad esempio un numero) e un modo per raggiungere l'elemento successivo.
Quando dichiariamo la variabile Button b
in pratica stiamo dicendo che b
indicherà una zona di memoria in cui è descritto un oggetto di tipo Button.
Proviamo a vedere come possiamo dichiarare il Nodo
nel caso di una coda che
memorizzi delle stringhe:
public class Nodo { String dato; Nodo successivo; }
Parafrasi: un Nodo
è formato da un dato
(in questo caso una stringa)
e un modo per raggiungere l'elemento successivo. L'oggetto non contiene un altro nodo al suo
interno perché, come dicevamo prima, successivo
è soltanto un modo per
indicare in memoria dove si trova un altro Nodo
Coda
Avendo il singolo blocchetto implementiamo la coda cercando di fare il meno possibile! Sarebbe a dire che implementeremo soltanto le funzionalità strettamente necessarie.
La coda di per se deve mantenere un riferimento al suo primo elemento (che è tradizionalmente chiamato testa), e poi due metodi per inserire (accoda) ed estrarre (estrai) elementi dalla coda stessa. Non importa un granche da che parte (inizio o fine) si inseriscono gli elementi: l'importante è che vengano estratti dalla parte opposta.
La nostra implementazione inserisce in coda e estrae in testa, per esercizio è possibile fare l'inverso.
public class Coda { private Nodo testa; public Coda(){ testa = null; } public void accoda(String nuovoDato){ Nodo nuovoElemento; // creo il nuovo elemento della lista nuovoElemento = new Nodo(); nuovoElemento.dato = nuovoDato; nuovoElemento.successivo = null; // controllo se in lista c'è già qualcosa if(testa == null){ // in lista non c'è nulla quindi la lista è costituita // solamente dal nuovo elemento testa = nuovoElemento; }else{ // esistono già elementi Nodo temp; // lo uso per scorrere la lista temp = testa; // continua finché non sei arrivato in fondo while(temp.successivo!=null){ // vai avanti temp = temp.successivo; } temp.successivo = nuovoElemento; } } public String estrai(){ Nodo temp; // il primo elemento della lista temp = testa; // visto che il primo elemento lo tolgo // la testa della lista deve puntare al successivo if(testa!=null) { testa = testa.successivo; } return temp.dato; } }
Implementazione della pila
La pila non è poi molto diversa dalla coda, in realtà è molto semplicemente implementabile come una coda in cui si inserisce e si estrae dalla stessa parte. Sebbene teoricamente sia possibile lavorare sia in coda che in testa l'implementazione più semplice (quella riportata qui) inserisce/estrae dalla testa della pila.
Per evitare confusione chiamiamo ElementoPila
quello che prima
abbiamo chiamato Nodo
, ma come è facile vedere sono praticamente uguali.
ElementoPila
public class ElementoPila { public String dato; public ElementoPila precedente; }
Pila
package lezioni.strutturedati; /**************************************************************************** * Una pila con le operazioni fondamentali ***************************************************************************/ public class Pila { private ElementoPila testa; public Pila(){ testa = null; } /************************************************************************ * @param nuovoDato l'elemento da inserire sulla pila ***********************************************************************/ public void push(String nuovoDato){ ElementoPila nuovoElemento; // creo il nuovo elemento della pila nuovoElemento = new ElementoPila(); nuovoElemento.dato = nuovoDato; nuovoElemento.precedente = null; // controllo se in lista c'è già qualcosa if(testa == null){ // in lista non c'è nulla quindi la lista è costituita // solamente dal nuovo elemento testa = nuovoElemento; }else{ // esistono già elementi nuovoElemento.precedente = testa; testa = nuovoElemento; } } /************************************************************************ * @return il primo elemento della pila (e lo toglie dalla pila) ***********************************************************************/ public String pop(){ ElementoPila temp; // il primo elemento della lista temp = testa; // scorri avanti testa = testa.precedente; return temp.dato; } /************************************************************************ * @return true se la lista è vuota ***********************************************************************/ public boolean vuota(){ return testa == null; } }
Quanto varrà la variabile n alla fine del seguente frammento di programma?
p.push("ciao");
p.push("mondo");
String n = p.pop();