Pile e code

di
steppox
il
2 risposte
S
steppox
Pochi posts
Iscritto da
apr, 2016
Messaggi:
35

Pile e code

Ciao a tutti!!
Ho una domanda abbastanza banale da fare, o almeno credo lo sia
In pratica ho studiato le liste ed ho implementato le funzioni per l'inserimento in una lista ordinata, cancellazione e ricerca. Teoricamente ho studiato anche le pile e le code ma non le ho mai trattate in C++ quindi vorrei implementare qualche funzione a riguardo. Dunque so che nelle pile si inserisce/estrae dalla testa (LIFO), mentre nelle code si inserisce il coda e si estrae dalla testa ( rear e front se volete)(FIFO).
Quindi, giusto per vedere se ho ben capito il concetto... per inserire un elemento in una pila basta solo allocare un nuovo nodo e poi 
nuovo->next=head;
head=nuovo;
per la ricerca e la cancellazione invece parto dalla head e scorro la pila come farei con una lista, giusto? (anche se in fin dei conti credo che una lista altro non è che una pila senza vincolo di inserimento in testa, sbaglio?)
Per quanto riguarda le code invece:
per la ricerca e la cancellazione parto dalla head(front) e scorro fin dove mi interessa come faccio per la pila.
Per l'inserimento invece alloco un nuovo nodo e lo piazzo in coda con: 
nuovo->next=NULL;
rear->next=nuovo;
E' giusto quello che ho scritto oppure ho preso fischi per fiaschi?!?!
Grazie per l'attenzione

2 Risposte

  • S
    SVNiko
    Molto attivo
    Iscritto da
    set, 2014
    Messaggi:
    535

    Re: Pile e code

    Quello che dici è corretto. Però, se hai bisogno di stack (LIFO) o code (FIFO), non serve fare ricerche (in teoria puoi farle, ma ci sono strutture più addette allo scopo).
    Per quanto riguarda lo stack puoi inserire in testa e estrarre dalla testa. Fine del discorso, costo O(1).
    Per le code invece, per inserire puoi inserire in testa costo O(1), ma per estrarre dovresti scorrere tutta la lista costo O(n), per avere anche in questo caso O(1) puoi costruirti un nodo con due puntatori uno alla testa e l'altro alla coda e tenerli aggiornati, così quando estrai hai il puntatore alla coda e il costo è O(1), senza la necessità di scorrere tutta la coda.
  • S
    steppox
    Pochi posts
    Iscritto da
    apr, 2016
    Messaggi:
    35

    Re: Pile e code

    SVNiko ha scritto:

    Quello che dici è corretto. Però, se hai bisogno di stack (LIFO) o code (FIFO), non serve fare ricerche (in teoria puoi farle, ma ci sono strutture più addette allo scopo).
    Per quanto riguarda lo stack puoi inserire in testa e estrarre dalla testa. Fine del discorso, costo O(1).
    Per le code invece, per inserire puoi inserire in testa costo O(1), ma per estrarre dovresti scorrere tutta la lista costo O(n), per avere anche in questo caso O(1) puoi costruirti un nodo con due puntatori uno alla testa e l'altro alla coda e tenerli aggiornati, così quando estrai hai il puntatore alla coda e il costo è O(1), senza la necessità di scorrere tutta la coda.
    Grazie mille
Devi accedere o registrarti per scrivere nel forum
2 risposte