Le strutture dati sono le strutture utilizzate per memorizzare e organizzare i dati

Le strutture dati dinamiche sono quelle la cui organizzazione evolve dinamicamente durante l'esecuzione del programma: pile, code, insiemi, liste, alberi, ...

La scelta della struttura dati dipende principalmente dalle operazioni che dovranno essere effettuate

Pila (stack)

• Struttura LIFO (Last if First Out): è possibile aggiungere o eliminare elementi solo in cima alla pila
  • Operazioni:
    • push: per aggiungere un elemento in cima alla pila
    • pop: per prelevare ed eliminare l'elemento in cima alla pila
    • empty: per verificare se la pila è vuota

Implementazione di Stack<E>

public Stack() //costruttore

public void push(E o) //aggiunge in cima alla pila l'oggetto fornito tramite parametro

public E pop() //restituisce un riferimento all'oggetto che si trova in cima alla pila eliminandolo dalla pila stessa. Se la pila è vuota il metodo solleva l'eccezione non controllata EmptyStackException

public boolean empty() //restituisce true se e solo se la pila è vuotastac

Anzichè creare subito lo spazio per la pila (come x gli array), viene creato dinamiamente, man mano che risulta necessario

Coda

• Struttura FIFO (First in First Out): il primo elemento che può essere prelevato è quello inserito per primo.
  • Una coda può essere realizzata con una lista in cui gli inserimenti vengono effettuati alla fine della lista, e gli elementi vengono prelevati dalla testa della lista

Alberi binari

Un albero binario è

• La struttura vuota, oppure
• un nodo (radice), cui sono associate due alberi binari (sottoalbero sinistro e sottoalbero destro)