Pile

di il
4 risposte

Pile

Eccomi con il secondo post.
in classe abbiamo iniziato l'argomento "liste". ha iniziato a spiegare le 2 che gli piacciono di più, la pila (LIFO) e la coda (FIFO) e poi la list vera e propria senza restrizioni
a livello teorico ho capito tutto, il problema è che ha chiesto di creare noi una classe pila, e una classe nodo
ora la classe nodo non è un problema, quello che mi esce difficile da comprendere, è appunto la classe pila
avete mica qualche esempio da mostrarmi, o qualche dritta da darmi?

4 Risposte

  • Re: Pile

    KuroKami69 ha scritto:


    in classe abbiamo iniziato l'argomento "liste". ha iniziato a spiegare le 2 che gli piacciono di più, la pila (LIFO) e la coda (FIFO) e poi la list vera e propria senza restrizioni
    a livello teorico ho capito tutto, il problema è che ha chiesto di creare noi una classe pila, e una classe nodo
    ora la classe nodo non è un problema, quello che mi esce difficile da comprendere, è appunto la classe pila
    avete mica qualche esempio da mostrarmi, o qualche dritta da darmi?
    Innanzitutto in una "pila" (stack) inserisci ed estrai i valori dallo stesso "lato" della sequenza di valori. Ora, una pila potrebbe essere implementata in diversi modi: con un array (eventualmente di lunghezza prefissata, specialmente se la pila non deve espandersi) oppure con una lista linkata di nodi. Questi sono i due principali approcci.

    Con una lista linkata, il minimo da fare è una cosa tipo:

    testa ---> Nodo1 ---> Nodo2 ---> ...... ---> NodoN

    Dove quel testa sarà una variabile di istanza di una classe es. Pila
    public class Pila {
        private Nodo testa;
    //......
    }
    Ci sono però diverse cose da valutare.

    Se devi solo inserire/rimuovere, puoi farlo dalla testa, che è BANALE. Il problema è se volessi anche iterare, perché se iteri così come si presenta, parti con l'ultimo elemento, non con il primo. Se vuoi iterare dal primo elemento (ovvero dal fondo) ci sono diverse cose che si possono fare per semplificare la cosa:
    a) usare una lista "double" linked, ovvero ogni nodo tiene anche il riferimento al precedente (e magari tieni nella Pila oltre alla testa anche il riferimento al fondo).
    b) puoi decidere di fare il contrario rispetto a prima, ovvero aggiungi/rimuovi dal fondo. Questo ti permette di iterare facilmente dal primo elemento ma per aggiungere/rimuovere dal fondo o scorri fino al fondo oppure idem usi una lista double linked.

    In sostanza: se usare una lista double-linked e/o tenere anche il riferimento al fondo dipende da quali operazioni devi permettere e se devono essere efficienti o non necessariamente.

    E' un po' più chiaro, così?
  • Re: Pile

    Si, grazie. la parte teorica era chiara, ma con l'aggiunta della lista double-linked ho avuto una visione d'insieme più chiara.
    sostanzialmente, volendo essere banali, la mia classe pila, per poter effettivamente avere una struttura di una pila, dovrà necessariamente avere un vettore, una list, o comunque un contenitore di grandezza finita oppure indefinita. dopodiché io ci inserisco i nodi e a seconda di come voglio fare io la pila, allora posso suare un doppio riferimento, mettere un riferimento sia al primo che all'ultimo elemento della lista e via dicendo.
    ma comunque DOVRA' essere presente un qualche tipo di contenitore, che sia un vector, un array, una matrice, un arraylist, una list e via dicendo giusto?
  • Re: Pile

    KuroKami69 ha scritto:


    ma comunque DOVRA' essere presente un qualche tipo di contenitore, che sia un vector, un array, una matrice, un arraylist, una list e via dicendo giusto?
    La pila dovrà certamente avere una sua struttura dati. Ma un conto è se la implementi tu da "zero" (tipicamente per ragioni "didattiche") e un altro conto è se incapsuli un'altra collezione già esistente (es. in Pila usi un java.util.LinkedList). Chiaramente così il 95% del lavoro è già fatto ... ma dal punto di vista didattico non è che impari granché ....
  • Re: Pile

    Bhe ci è stato detto che l'uso di questo tipo di pile, con restrizioni, viene usata in contesti molto specifici, anche se io non immagino nemmeno quali possano essere. quindi oltre a imparare la parte didattica credo che userò sempre list ahaha comunque grazie
Devi accedere o registrarti per scrivere nel forum
4 risposte