public class Nodo

Ciò che segue è una semplice rappresentazione di una lista:

Per costruire una lista come quella scritta sopra si può usare il seguente frammento di codice:

Nodo a = new Nodo(a1,null);

Nodo b = new Nodo(a2,null);

Nodo c = new Nodo(a3,null);

a.next = b;

b.next = c;

Per visitare una lista in modo iterativo si può far riferimento al seguente algoritmo:

Nodo n = a;   // a è il puntatore d'accesso alla lista

while (n!=null)

Per inserire un elemento in testa basta usare il seguente frammento di codice:

n.next = first; // n è il nodo da inserire

first = n; // first è il puntatore d'accesso

Per inserire un elemento in mezzo o in coda bisogna prima posizionarsi sul nodo precedente tramite un nodo d'appoggio (prec) e poi si può inserire, in questo modo:

n.next = prec.next; // n è il nodo da inserire

prec.next = n;

Per eliminare un elemento in testa basta rifarsi al seguente frammento di codice:

first = first.next;

Per eliminare un elemento in mezzo o in coda bisogna prima posizionarsi sul nodo precedente tramite un nodo d'appoggio (prec) e poi si può cancellare, in questo modo:

prec.next = prec.next.next;

Ci sono altri tipi di lista, come la lista doppiamente concatenate o la lista circolare, ma in questa tesina non ne parliamo, quindi passeremo a trattare le pile e le code.

Pila

Una pila è una successione di elementi in cui 929f59j tutte le operazioni di inserimento e di cancellazione avvengono dallo stesso estremo detto testa della pila. La pila esegue una disciplina LIFO(Last In First Out). Le pile sono molto utilizzate per controllare le chiamate ai sottoprogrammi. Le pile possono essere implementate in maniera illimitata, attraverso una lista, o in maniera limitata, attraverso un vettore.

In questa tesina vedremo solo l'utilizzo di una pila illimitata. Il diagramma UML di una classe Pila è il seguente:

Le operazioni che si possono eseguire su una pila sono quindi le seguenti:

push (x) : inserisce l'elemento x nella pila;

pop ( ) : elimina l'elemento in testa alla lista senza ritornarlo;

top ( ) : restituisce l'elemento in testa alla pila senza rimuoverlo;

isEmpty ( ) : indica se la pila è vuota;

Coda

Una coda è una struttura dati che utilizza la disciplina FIFO ( First In First Out ). Anche le code possono essere implementate, come le pile, o in modo illimitato, con delle liste concatenate, o in modo limitato, con un vettore.

In questa tesina vedremo solo l'utilizzo di una coda illimitata. Il diagramma UML di una classe Coda è il seguente:

Le operazioni che si possono eseguire su una coda sono quindi le seguenti:

enqueue (x) : inserisce l'elemento x in fondo alla coda;

dequeue ( ) : elimina l'elemento in testa alla coda senza ritornarlo;

front ( ) : restituisce l'elemento in testa alla coda senza rimuoverlo;

isEmpty ( ) : indica se la coda è vuota;