2.2 (esercitazione 2 esercizio 2)

char * lastin(Queue q){
    char * x;
    char * ris;
    x=dequeue(q);
    if(queueEmpty(q)){enqueue(q,x); return x;}
    else {
        ris=lastin(q);
        enqueue(q,x);
        return ris;
    }
}

void inverti(Queue q){ if(!queueEmpty(q))lastin(q); }


/*

Mia spiegazione della complessità:

Ammettiamo che tutte le funzioni sulle code siano di complessità costante (come da esercizio 1).
La funzione "inverti" ha la complessità della funzione ausiliaria "lastin".
In caso la coda q abbia uno e un solo elemento, questa funzione ha complessità costante: T(1)=k.
Se invece ha n elementi (n>1) ricadiamo nel secondo if-branch in cui si invoca ricorsivamente lastin su q. Il numero di elementi di q è stato decrementato di 1, inoltre vengono fatte delle operazioni costanti.
Per cui la complessità ricorsiva della funzione è T(n)=T(n-1)+k.

Risolvo tale ricorsione mediante la tecnica dello srotolamento:
T(n)=T(n-1)+k
T(n-1)=T(n-2)+k
...
T(2)=T(1)+k
T(1)=k

Da cui, sostituendo ricorsivamente, possiamo affermare che:
T(n) = T(1)+(n-1)k = nk = θ(n).

*/