Probleme Rezolvate

Scrieţi un program care să afişeze , în ordine inversă, o listă liniară înlănţuită (o listă de caractere, o listă de cifre, o listă de numere sau o listă de cuvinte). Implementați aceşti algoritmi folosind:
a) stiva;
b) recursivitatea.
Comparaţi cei doi algoritmi din punct de vedere al eficienței.
a) Implementare cu stivă:

# include < iostream >
using namespace std ;
struct Node {
int data;
Node * next ;
Node ( int d) : data (d), next ( nullptr ) {}
};
void afisareInversaStiva ( Node * head ) {
int n = 0 ;
Node * p = head ;
while (p) {
n++;
p = p-> next ;
}
int * v = new int [n];
int i = 0 ;
p = head ;
while (p) {
v[i++] = p->data;
p = p-> next ;
}
for ( int j = n - 1 ; j >= 0 ; j--) {
cout << v[j] << " " ;
}
cout << endl ;
delete [] v;
}
int main () {
Node * head = new Node ( 1 );
head -> next = new Node ( 2 );
head -> next -> next = new Node ( 3 );
afisareInversaStiva ( head );
return 0 ;
}
b) Implementare recursivă:
# include < iostream >
using namespace std ;
struct Node {
int data;
Node * next ;
Node ( int d) : data (d), next ( nullptr ) {}
};
void afisareInversaRecursiva ( Node * head ) {
if ( head == nullptr ) {
return ;
}
afisareInversaRecursiva ( head -> next );
cout << head ->data << " " ;
}
int main () {
Node * head = new Node ( 1 );
head -> next = new Node ( 2 );
head -> next -> next = new Node ( 3 );
afisareInversaRecursiva ( head );
return 0 ;
}

Pentru a compara eficiența celor doi algoritmi, trebuie să luăm în considerare complexitatea acestora. Implementarea cu stivă are o complexitate spațială de O(n), deoarece este nevoie să alocăm un vector de dimensiunea listei. Complexitatea temporală este de O(n), deoarece parcurgem lista de două ori. Implementarea recursivă are o complexitate spațială de O(n), deoarece apelăm funcția recursivă pentru fiecare element din listă. Complexitatea temporală este de O(n), deoarece parcurgem lista o singură dată, dar apelăm funcția recursivă pentru fiecare element din listă.
În general, implementarea recursivă poate fi mai simplă și mai ușor de înțeles, dar poate duce la probleme de depășire a stivei ( stack overflow ) pentru liste foarte lungi. Implementarea cu stivă poate fi mai eficientă pentru liste mari, dar necesită o alocare suplimentară de memorie.