Structuri de Date Dinamice și Template-uri în C++

Introducere în Structuri de Date Dinamice

Structurile de date dinamice sunt esențiale în programare deoarece permit gestionarea eficientă a datelor care se schimbă în timp. Spre deosebire de array-urile statice, acestea pot crește sau se pot micșora după necesități.

Ce vei învăța:

• Alocarea dinamică a memoriei cu new și delete
• Implementarea și utilizarea pointerilor
• Crearea structurilor de date flexibile
• Algoritmii fundamentali pentru manipularea datelor
• Template-uri (generice) pentru structuri de date reutilizabile

Liste Înlănțuite (Linked Lists)

Lista înlănțuită este o structură de date liniară unde elementele sunt stocate în noduri, fiecare nod conținând date și un pointer către următorul nod.

Structura unui Nod

struct Nod {
    int data;
    Nod* next;
};

Implementare Completă - Listă Simplu Înlănțuită

class ListaSimpluInlantuita {
private:
    Nod* head;
    
public:
    // Constructor
    ListaSimpluInlantuita() {
        head = NULL;
    }
    
    // Inserare la început
    void inserareInceput(int valoare) {
        Nod* nodNou = new Nod;
        nodNou->data = valoare;
        nodNou->next = head;
        head = nodNou;
    }
    
    // Inserare la sfârșit
    void inserareSfarsit(int valoare) {
        Nod* nodNou = new Nod;
        nodNou->data = valoare;
        nodNou->next = NULL;
        
        if (head == NULL) {
            head = nodNou;
            return;
        }
        
        Nod* temp = head;
        while (temp->next != NULL) {
            temp = temp->next;
        }
        temp->next = nodNou;
    }
    
    // Inserare la poziție
    void inserarePozitie(int valoare, int pozitie) {
        if (pozitie == 0) {
            inserareInceput(valoare);
            return;
        }
        
        Nod* nodNou = new Nod;
        nodNou->data = valoare;
        
        Nod* temp = head;
        for (int i = 0; i < pozitie - 1 && temp != NULL; i++) {
            temp = temp->next;
        }
        
        if (temp == NULL) {
            cout << "Pozitie invalida!" << endl;
            delete nodNou;
            return;
        }
        
        nodNou->next = temp->next;
        temp->next = nodNou;
    }
    
    // Ștergere după valoare
    void stergereValoare(int valoare) {
        if (head == NULL) return;
        
        if (head->data == valoare) {
            Nod* temp = head;
            head = head->next;
            delete temp;
            return;
        }
        
        Nod* curent = head;
        while (curent->next != NULL && curent->next->data != valoare) {
            curent = curent->next;
        }
        
        if (curent->next != NULL) {
            Nod* deSters = curent->next;
            curent->next = curent->next->next;
            delete deSters;
        }
    }
    
    // Căutare
    bool cautare(int valoare) {
        Nod* temp = head;
        while (temp != NULL) {
            if (temp->data == valoare)
                return true;
            temp = temp->next;
        }
        return false;
    }
    
    // Afișare
    void afisare() {
        Nod* temp = head;
        cout << "Lista: ";
        while (temp != NULL) {
            cout << temp->data << " -> ";
            temp = temp->next;
        }
        cout << "NULL" << endl;
    }
    
    // Inversare listă
    void inversare() {
        Nod* prev = NULL;
        Nod* curent = head;
        Nod* next = NULL;
        
        while (curent != NULL) {
            next = curent->next;
            curent->next = prev;
            prev = curent;
            curent = next;
        }
        head = prev;
    }
    
    // Destructor
    ~ListaSimpluInlantuita() {
        while (head != NULL) {
            Nod* temp = head;
            head = head->next;
            delete temp;
        }
    }
};

int gasesteMijloc() {
    if (head == NULL) return -1;
    
    Nod* slow = head;
    Nod* fast = head;
    
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    
    return slow->data;
}

bool detecteazaCiclu() {
    if (head == NULL) return false;
    
    Nod* slow = head;
    Nod* fast = head;
    
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
        
        if (slow == fast)
            return true;
    }
    
    return false;
}

Stive (Stacks)

Stiva este o structură de date LIFO (Last In, First Out) unde elementele sunt adăugate și eliminate doar de la vârf.

Implementare cu Array

class StivaArray {
private:
    int* arr;
    int top;
    int capacitate;
    
public:
    // Constructor
    StivaArray(int size) {
        arr = new int[size];
        capacitate = size;
        top = -1;
    }
    
    // Push - adaugă element
    void push(int x) {
        if (isFull()) {
            cout << "Stiva este plina!" << endl;
            return;
        }
        arr[++top] = x;
    }
    
    // Pop - elimină element
    int pop() {
        if (isEmpty()) {
            cout << "Stiva este goala!" << endl;
            return -1;
        }
        return arr[top--];
    }
    
    // Peek - vezi vârful
    int peek() {
        if (!isEmpty())
            return arr[top];
        return -1;
    }
    
    // Verifică dacă e goală
    bool isEmpty() {
        return top == -1;
    }
    
    // Verifică dacă e plină
    bool isFull() {
        return top == capacitate - 1;
    }
    
    // Destructor
    ~StivaArray() {
        delete[] arr;
    }
};

Implementare cu Listă Înlănțuită

class StivaLista {
private:
    struct NodStiva {
        int data;
        NodStiva* next;
    };
    NodStiva* top;
    
public:
    // Constructor
    StivaLista() {
        top = NULL;
    }
    
    // Push
    void push(int x) {
        NodStiva* nodNou = new NodStiva;
        nodNou->data = x;
        nodNou->next = top;
        top = nodNou;
    }
    
    // Pop
    int pop() {
        if (isEmpty()) {
            cout << "Stiva goala!" << endl;
            return -1;
        }
        
        int val = top->data;
        NodStiva* temp = top;
        top = top->next;
        delete temp;
        return val;
    }
    
    // Peek
    int peek() {
        if (!isEmpty())
            return top->data;
        return -1;
    }
    
    // isEmpty
    bool isEmpty() {
        return top == NULL;
    }
    
    // Destructor
    ~StivaLista() {
        while (!isEmpty()) {
            pop();
        }
    }
};

Aplicație: Verificare Paranteze Echilibrate

bool parantezeEchilibrate(char* expresie) {
    StivaLista stiva;
    
    for (int i = 0; expresie[i] != '\0'; i++) {
        char ch = expresie[i];
        
        // Dacă e paranteză deschisă, adaugă în stivă
        if (ch == '(' || ch == '[' || ch == '{') {
            stiva.push(ch);
        }
        // Dacă e paranteză închisă
        else if (ch == ')' || ch == ']' || ch == '}') {
            if (stiva.isEmpty())
                return false;
                
            char top = stiva.pop();
            
            if ((ch == ')' && top != '(') ||
                (ch == ']' && top != '[') ||
                (ch == '}' && top != '{'))
                return false;
        }
    }
    
    return stiva.isEmpty();
}

int evaluarePostfix(char* expresie) {
    StivaLista stiva;
    
    for (int i = 0; expresie[i] != '\0'; i++) {
        char ch = expresie[i];
        
        // Dacă e cifră
        if (ch >= '0' && ch <= '9') {
            stiva.push(ch - '0');
        }
        // Dacă e operator
        else {
            int val2 = stiva.pop();
            int val1 = stiva.pop();
            
            switch(ch) {
                case '+': stiva.push(val1 + val2); break;
                case '-': stiva.push(val1 - val2); break;
                case '*': stiva.push(val1 * val2); break;
                case '/': stiva.push(val1 / val2); break;
            }
        }
    }
    
    return stiva.pop();
}

Cozi (Queues)

Coada este o structură de date FIFO (First In, First Out) unde elementele sunt adăugate la sfârșit și eliminate de la început.

Implementare cu Array Circular

class CoadaArray {
private:
    int* arr;
    int front;
    int rear;
    int capacitate;
    int count;
    
public:
    // Constructor
    CoadaArray(int size) {
        arr = new int[size];
        capacitate = size;
        front = 0;
        rear = -1;
        count = 0;
    }
    
    // Enqueue - adaugă la sfârșit
    void enqueue(int x) {
        if (isFull()) {
            cout << "Coada este plina!" << endl;
            return;
        }
        
        rear = (rear + 1) % capacitate;
        arr[rear] = x;
        count++;
    }
    
    // Dequeue - elimină de la început
    int dequeue() {
        if (isEmpty()) {
            cout << "Coada este goala!" << endl;
            return -1;
        }
        
        int x = arr[front];
        front = (front + 1) % capacitate;
        count--;
        return x;
    }
    
    // Peek
    int peek() {
        if (!isEmpty())
            return arr[front];
        return -1;
    }
    
    // Verificări
    bool isEmpty() {
        return count == 0;
    }
    
    bool isFull() {
        return count == capacitate;
    }
    
    // Destructor
    ~CoadaArray() {
        delete[] arr;
    }
};

Implementare cu Listă Înlănțuită

class CoadaLista {
private:
    struct NodCoada {
        int data;
        NodCoada* next;
    };
    NodCoada* front;
    NodCoada* rear;
    
public:
    // Constructor
    CoadaLista() {
        front = rear = NULL;
    }
    
    // Enqueue
    void enqueue(int x) {
        NodCoada* nodNou = new NodCoada;
        nodNou->data = x;
        nodNou->next = NULL;
        
        if (rear == NULL) {
            front = rear = nodNou;
            return;
        }
        
        rear->next = nodNou;
        rear = nodNou;
    }
    
    // Dequeue
    int dequeue() {
        if (front == NULL) {
            cout << "Coada goala!" << endl;
            return -1;
        }
        
        int val = front->data;
        NodCoada* temp = front;
        front = front->next;
        
        if (front == NULL)
            rear = NULL;
            
        delete temp;
        return val;
    }
    
    // isEmpty
    bool isEmpty() {
        return front == NULL;
    }
    
    // Destructor
    ~CoadaLista() {
        while (!isEmpty()) {
            dequeue();
        }
    }
};

Coadă cu Prioritate

struct Element {
    int data;
    int prioritate;
};

class CoadaPrioritate {
private:
    Element* arr;
    int size;
    int capacitate;
    
public:
    CoadaPrioritate(int cap) {
        capacitate = cap;
        arr = new Element[cap];
        size = 0;
    }
    
    // Inserare cu prioritate
    void enqueue(int val, int prio) {
        if (size == capacitate) {
            cout << "Coada plina!" << endl;
            return;
        }
        
        int i = size - 1;
        while (i >= 0 && arr[i].prioritate > prio) {
            arr[i + 1] = arr[i];
            i--;
        }
        
        arr[i + 1].data = val;
        arr[i + 1].prioritate = prio;
        size++;
    }
    
    // Extrage elementul cu prioritate maximă
    int dequeue() {
        if (size == 0) {
            cout << "Coada goala!" << endl;
            return -1;
        }
        
        return arr[--size].data;
    }
};

class Deque {
private:
    struct NodDeque {
        int data;
        NodDeque* next;
        NodDeque* prev;
    };
    NodDeque* front;
    NodDeque* rear;
    
public:
    Deque() {
        front = rear = NULL;
    }
    
    void pushFront(int x) {
        NodDeque* nodNou = new NodDeque;
        nodNou->data = x;
        nodNou->next = front;
        nodNou->prev = NULL;
        
        if (front == NULL)
            rear = nodNou;
        else
            front->prev = nodNou;
            
        front = nodNou;
    }
    
    void pushRear(int x) {
        NodDeque* nodNou = new NodDeque;
        nodNou->data = x;
        nodNou->next = NULL;
        nodNou->prev = rear;
        
        if (rear == NULL)
            front = nodNou;
        else
            rear->next = nodNou;
            
        rear = nodNou;
    }
    
    int popFront() {
        if (front == NULL) return -1;
        
        int val = front->data;
        NodDeque* temp = front;
        front = front->next;
        
        if (front == NULL)
            rear = NULL;
        else
            front->prev = NULL;
            
        delete temp;
        return val;
    }
    
    int popRear() {
        if (rear == NULL) return -1;
        
        int val = rear->data;
        NodDeque* temp = rear;
        rear = rear->prev;
        
        if (rear == NULL)
            front = NULL;
        else
            rear->next = NULL;
            
        delete temp;
        return val;
    }
};

Hash Tables (Tabele de Dispersie)

Hash table-ul este o structură de date care oferă acces rapid la date folosind o funcție hash pentru a mapa chei la poziții în array.

Implementare cu Chaining (Liste Înlănțuite)

class HashTable {
private:
    static const int TABLE_SIZE = 10;
    
    struct HashNode {
        int key;
        int value;
        HashNode* next;
    };
    
    HashNode* table[TABLE_SIZE];
    
    // Funcția hash
    int hashFunction(int key) {
        return key % TABLE_SIZE;
    }
    
public:
    // Constructor
    HashTable() {
        for (int i = 0; i < TABLE_SIZE; i++)
            table[i] = NULL;
    }
    
    // Inserare
    void insert(int key, int value) {
        int hash = hashFunction(key);
        
        HashNode* nodNou = new HashNode;
        nodNou->key = key;
        nodNou->value = value;
        nodNou->next = NULL;
        
        // Dacă poziția e goală
        if (table[hash] == NULL) {
            table[hash] = nodNou;
        }
        // Dacă există coliziune
        else {
            HashNode* temp = table[hash];
            
            // Verifică dacă cheia există deja
            while (temp->next != NULL) {
                if (temp->key == key) {
                    temp->value = value;  // Actualizează valoarea
                    delete nodNou;
                    return;
                }
                temp = temp->next;
            }
            
            if (temp->key == key) {
                temp->value = value;
                delete nodNou;
            } else {
                temp->next = nodNou;
            }
        }
    }
    
    // Căutare
    int search(int key) {
        int hash = hashFunction(key);
        
        HashNode* temp = table[hash];
        while (temp != NULL) {
            if (temp->key == key)
                return temp->value;
            temp = temp->next;
        }
        
        return -1;  // Nu a fost găsit
    }
    
    // Ștergere
    void remove(int key) {
        int hash = hashFunction(key);
        
        if (table[hash] == NULL)
            return;
        
        // Dacă e primul nod
        if (table[hash]->key == key) {
            HashNode* temp = table[hash];
            table[hash] = table[hash]->next;
            delete temp;
            return;
        }
        
        // Caută în listă
        HashNode* prev = table[hash];
        HashNode* curr = prev->next;
        
        while (curr != NULL && curr->key != key) {
            prev = curr;
            curr = curr->next;
        }
        
        if (curr != NULL) {
            prev->next = curr->next;
            delete curr;
        }
    }
    
    // Afișare
    void display() {
        for (int i = 0; i < TABLE_SIZE; i++) {
            cout << i << ": ";
            HashNode* temp = table[i];
            while (temp != NULL) {
                cout << "[" << temp->key << "," << temp->value << "] ";
                temp = temp->next;
            }
            cout << endl;
        }
    }
    
    // Destructor
    ~HashTable() {
        for (int i = 0; i < TABLE_SIZE; i++) {
            HashNode* temp = table[i];
            while (temp != NULL) {
                HashNode* deSters = temp;
                temp = temp->next;
                delete deSters;
            }
        }
    }
};

Implementare cu Linear Probing

class HashTableProbing {
private:
    static const int TABLE_SIZE = 20;
    int keys[TABLE_SIZE];
    int values[TABLE_SIZE];
    bool occupied[TABLE_SIZE];
    
    int hashFunction(int key) {
        return key % TABLE_SIZE;
    }
    
public:
    HashTableProbing() {
        for (int i = 0; i < TABLE_SIZE; i++)
            occupied[i] = false;
    }
    
    void insert(int key, int value) {
        int hash = hashFunction(key);
        
        // Linear probing
        while (occupied[hash]) {
            if (keys[hash] == key) {
                values[hash] = value;  // Actualizare
                return;
            }
            hash = (hash + 1) % TABLE_SIZE;
        }
        
        keys[hash] = key;
        values[hash] = value;
        occupied[hash] = true;
    }
    
    int search(int key) {
        int hash = hashFunction(key);
        
        while (occupied[hash]) {
            if (keys[hash] == key)
                return values[hash];
            hash = (hash + 1) % TABLE_SIZE;
        }
        
        return -1;
    }
};

void insertQuadratic(int key, int value) {
    int hash = hashFunction(key);
    int i = 0;
    
    while (occupied[(hash + i*i) % TABLE_SIZE]) {
        if (keys[(hash + i*i) % TABLE_SIZE] == key) {
            values[(hash + i*i) % TABLE_SIZE] = value;
            return;
        }
        i++;
        
        // Verifică dacă am parcurs tot tabelul
        if (i >= TABLE_SIZE) {
            cout << "Tabel plin!" << endl;
            return;
        }
    }
    
    int pos = (hash + i*i) % TABLE_SIZE;
    keys[pos] = key;
    values[pos] = value;
    occupied[pos] = true;
}

Arbori Binari

Arborele binar este o structură de date ierarhică unde fiecare nod are maximum doi copii: stânga și dreapta.

Arbore Binar de Căutare (BST)

class BST {
private:
    struct NodArbore {
        int data;
        NodArbore* left;
        NodArbore* right;
    };
    NodArbore* root;
    
    // Funcții helper recursive
    NodArbore* insertHelper(NodArbore* nod, int val) {
        if (nod == NULL) {
            NodArbore* nodNou = new NodArbore;
            nodNou->data = val;
            nodNou->left = nodNou->right = NULL;
            return nodNou;
        }
        
        if (val < nod->data)
            nod->left = insertHelper(nod->left, val);
        else if (val > nod->data)
            nod->right = insertHelper(nod->right, val);
            
        return nod;
    }
    
    bool searchHelper(NodArbore* nod, int val) {
        if (nod == NULL)
            return false;
            
        if (nod->data == val)
            return true;
            
        if (val < nod->data)
            return searchHelper(nod->left, val);
        else
            return searchHelper(nod->right, val);
    }
    
    NodArbore* findMin(NodArbore* nod) {
        while (nod->left != NULL)
            nod = nod->left;
        return nod;
    }
    
    NodArbore* deleteHelper(NodArbore* nod, int val) {
        if (nod == NULL)
            return nod;
            
        if (val < nod->data)
            nod->left = deleteHelper(nod->left, val);
        else if (val > nod->data)
            nod->right = deleteHelper(nod->right, val);
        else {
            // Nod găsit - 3 cazuri
            
            // Caz 1: Fără copii
            if (nod->left == NULL && nod->right == NULL) {
                delete nod;
                return NULL;
            }
            
            // Caz 2: Un copil
            if (nod->left == NULL) {
                NodArbore* temp = nod->right;
                delete nod;
                return temp;
            }
            if (nod->right == NULL) {
                NodArbore* temp = nod->left;
                delete nod;
                return temp;
            }
            
            // Caz 3: Doi copii
            NodArbore* temp = findMin(nod->right);
            nod->data = temp->data;
            nod->right = deleteHelper(nod->right, temp->data);
        }
        
        return nod;
    }
    
    void inorderHelper(NodArbore* nod) {
        if (nod != NULL) {
            inorderHelper(nod->left);
            cout << nod->data << " ";
            inorderHelper(nod->right);
        }
    }
    
    void preorderHelper(NodArbore* nod) {
        if (nod != NULL) {
            cout << nod->data << " ";
            preorderHelper(nod->left);
            preorderHelper(nod->right);
        }
    }
    
    void postorderHelper(NodArbore* nod) {
        if (nod != NULL) {
            postorderHelper(nod->left);
            postorderHelper(nod->right);
            cout << nod->data << " ";
        }
    }
    
    int heightHelper(NodArbore* nod) {
        if (nod == NULL)
            return -1;
            
        int leftHeight = heightHelper(nod->left);
        int rightHeight = heightHelper(nod->right);
        
        return 1 + (leftHeight > rightHeight ? leftHeight : rightHeight);
    }
    
public:
    // Constructor
    BST() {
        root = NULL;
    }
    
    // Funcții publice
    void insert(int val) {
        root = insertHelper(root, val);
    }
    
    bool search(int val) {
        return searchHelper(root, val);
    }
    
    void remove(int val) {
        root = deleteHelper(root, val);
    }
    
    void inorder() {
        cout << "Inorder: ";
        inorderHelper(root);
        cout << endl;
    }
    
    void preorder() {
        cout << "Preorder: ";
        preorderHelper(root);
        cout << endl;
    }
    
    void postorder() {
        cout << "Postorder: ";
        postorderHelper(root);
        cout << endl;
    }
    
    int height() {
        return heightHelper(root);
    }
};

Parcurgere pe Nivel (Level Order)

void levelOrder() {
    if (root == NULL) return;
    
    // Folosim o coadă pentru parcurgere
    CoadaLista coada;
    coada.enqueue(root);
    
    while (!coada.isEmpty()) {
        NodArbore* curent = coada.dequeue();
        cout << curent->data << " ";
        
        if (curent->left)
            coada.enqueue(curent->left);
        if (curent->right)
            coada.enqueue(curent->right);
    }
}

bool isBSTHelper(NodArbore* nod, int min, int max) {
    if (nod == NULL)
        return true;
        
    if (nod->data <= min || nod->data >= max)
        return false;
        
    return isBSTHelper(nod->left, min, nod->data) &&
           isBSTHelper(nod->right, nod->data, max);
}

bool isBST() {
    return isBSTHelper(root, INT_MIN, INT_MAX);
}

NodArbore* findLCA(NodArbore* nod, int n1, int n2) {
    if (nod == NULL)
        return NULL;
        
    // Dacă ambele valori sunt mai mici, LCA e în stânga
    if (n1 < nod->data && n2 < nod->data)
        return findLCA(nod->left, n1, n2);
        
    // Dacă ambele valori sunt mai mari, LCA e în dreapta
    if (n1 > nod->data && n2 > nod->data)
        return findLCA(nod->right, n1, n2);
        
    // Altfel, nodul curent este LCA
    return nod;
}

Template-uri (Generice)

Template-urile permit crearea de clase și funcții generice care pot lucra cu orice tip de date, nu doar cu int.

Sintaxa de Bază

// Template pentru funcție
template <typename T>
T maxim(T a, T b) {
    return (a > b) ? a : b;
}

// Template pentru clasă
template <class T>
class Container {
    T element;
public:
    void set(T arg) { element = arg; }
    T get() { return element; }
};

Listă Înlănțuită Generică

template <typename T>
class ListaGenerica {
private:
    struct Nod {
        T data;
        Nod* next;
    };
    Nod* head;
    
public:
    // Constructor
    ListaGenerica() : head(NULL) {}
    
    // Inserare la început
    void push_front(const T& valoare) {
        Nod* nodNou = new Nod;
        nodNou->data = valoare;
        nodNou->next = head;
        head = nodNou;
    }
    
    // Inserare la sfârșit
    void push_back(const T& valoare) {
        Nod* nodNou = new Nod;
        nodNou->data = valoare;
        nodNou->next = NULL;
        
        if (head == NULL) {
            head = nodNou;
            return;
        }
        
        Nod* temp = head;
        while (temp->next != NULL) {
            temp = temp->next;
        }
        temp->next = nodNou;
    }
    
    // Afișare (necesită operator<< pentru tipul T)
    void afisare() {
        Nod* temp = head;
        cout << "Lista: ";
        while (temp != NULL) {
            cout << temp->data << " -> ";
            temp = temp->next;
        }
        cout << "NULL" << endl;
    }
    
    // Căutare
    bool contine(const T& valoare) {
        Nod* temp = head;
        while (temp != NULL) {
            if (temp->data == valoare)
                return true;
            temp = temp->next;
        }
        return false;
    }
    
    // Destructor
    ~ListaGenerica() {
        while (head != NULL) {
            Nod* temp = head;
            head = head->next;
            delete temp;
        }
    }
};

Stivă Generică

template <typename T>
class StivaGenerica {
private:
    T* arr;
    int top;
    int capacitate;
    
public:
    // Constructor
    StivaGenerica(int size = 100) {
        arr = new T[size];
        capacitate = size;
        top = -1;
    }
    
    // Copy constructor
    StivaGenerica(const StivaGenerica& alta) {
        capacitate = alta.capacitate;
        top = alta.top;
        arr = new T[capacitate];
        for (int i = 0; i <= top; i++) {
            arr[i] = alta.arr[i];
        }
    }
    
    // Push
    void push(const T& element) {
        if (top >= capacitate - 1) {
            cout << "Stiva plina!" << endl;
            return;
        }
        arr[++top] = element;
    }
    
    // Pop
    T pop() {
        if (isEmpty()) {
            throw "Stiva goala!";
        }
        return arr[top--];
    }
    
    // Peek
    T& peek() {
        if (isEmpty()) {
            throw "Stiva goala!";
        }
        return arr[top];
    }
    
    bool isEmpty() const {
        return top == -1;
    }
    
    int size() const {
        return top + 1;
    }
    
    // Destructor
    ~StivaGenerica() {
        delete[] arr;
    }
};

Pereche Generică (Pair)

template <typename T1, typename T2>
class Pereche {
public:
    T1 first;
    T2 second;
    
    // Constructori
    Pereche() {}
    
    Pereche(const T1& a, const T2& b) : first(a), second(b) {}
    
    // Operator de comparație
    bool operator==(const Pereche& alta) const {
        return first == alta.first && second == alta.second;
    }
    
    // Operator de atribuire
    Pereche& operator=(const Pereche& alta) {
        if (this != &alta) {
            first = alta.first;
            second = alta.second;
        }
        return *this;
    }
};

// Funcție helper pentru crearea de perechi
template <typename T1, typename T2>
Pereche<T1, T2> make_pereche(const T1& a, const T2& b) {
    return Pereche<T1, T2>(a, b);
}

Hash Table Generic

template <typename K, typename V>
class HashTableGeneric {
private:
    static const int TABLE_SIZE = 100;
    
    struct HashNode {
        K key;
        V value;
        HashNode* next;
    };
    
    HashNode* table[TABLE_SIZE];
    
    // Funcție hash generică
    int hashFunction(int key) {
        return key % TABLE_SIZE;
    }
    
    // Specializare pentru string
    int hashFunction(const char* key) {
        int hash = 0;
        for (int i = 0; key[i] != '\0'; i++) {
            hash = (hash * 31 + key[i]) % TABLE_SIZE;
        }
        return hash;
    }
    
public:
    HashTableGeneric() {
        for (int i = 0; i < TABLE_SIZE; i++)
            table[i] = NULL;
    }
    
    void insert(const K& key, const V& value) {
        int hash = hashFunction(key);
        
        // Verifică dacă cheia există
        HashNode* temp = table[hash];
        while (temp != NULL) {
            if (temp->key == key) {
                temp->value = value;
                return;
            }
            temp = temp->next;
        }
        
        // Inserare nouă
        HashNode* nodNou = new HashNode;
        nodNou->key = key;
        nodNou->value = value;
        nodNou->next = table[hash];
        table[hash] = nodNou;
    }
    
    bool find(const K& key, V& value) {
        int hash = hashFunction(key);
        
        HashNode* temp = table[hash];
        while (temp != NULL) {
            if (temp->key == key) {
                value = temp->value;
                return true;
            }
            temp = temp->next;
        }
        return false;
    }
    
    ~HashTableGeneric() {
        for (int i = 0; i < TABLE_SIZE; i++) {
            HashNode* temp = table[i];
            while (temp != NULL) {
                HashNode* deSters = temp;
                temp = temp->next;
                delete deSters;
            }
        }
    }
};

Arbore Binar Generic

template <typename T>
class BST_Generic {
private:
    struct NodArbore {
        T data;
        NodArbore* left;
        NodArbore* right;
        
        NodArbore(T val) : data(val), left(NULL), right(NULL) {}
    };
    
    NodArbore* root;
    
    // Funcții helper recursive
    NodArbore* insertHelper(NodArbore* nod, const T& val) {
        if (nod == NULL) {
            return new NodArbore(val);
        }
        
        if (val < nod->data)
            nod->left = insertHelper(nod->left, val);
        else if (val > nod->data)
            nod->right = insertHelper(nod->right, val);
            
        return nod;
    }
    
    void inorderHelper(NodArbore* nod) {
        if (nod != NULL) {
            inorderHelper(nod->left);
            cout << nod->data << " ";
            inorderHelper(nod->right);
        }
    }
    
    NodArbore* findMin(NodArbore* nod) {
        while (nod->left != NULL)
            nod = nod->left;
        return nod;
    }
    
    NodArbore* deleteHelper(NodArbore* nod, const T& val) {
        if (nod == NULL)
            return nod;
            
        if (val < nod->data)
            nod->left = deleteHelper(nod->left, val);
        else if (val > nod->data)
            nod->right = deleteHelper(nod->right, val);
        else {
            // Nod cu 0 sau 1 copil
            if (nod->left == NULL) {
                NodArbore* temp = nod->right;
                delete nod;
                return temp;
            }
            else if (nod->right == NULL) {
                NodArbore* temp = nod->left;
                delete nod;
                return temp;
            }
            
            // Nod cu 2 copii
            NodArbore* temp = findMin(nod->right);
            nod->data = temp->data;
            nod->right = deleteHelper(nod->right, temp->data);
        }
        return nod;
    }
    
    void destroyTree(NodArbore* nod) {
        if (nod != NULL) {
            destroyTree(nod->left);
            destroyTree(nod->right);
            delete nod;
        }
    }
    
public:
    BST_Generic() : root(NULL) {}
    
    void insert(const T& val) {
        root = insertHelper(root, val);
    }
    
    void remove(const T& val) {
        root = deleteHelper(root, val);
    }
    
    void inorder() {
        inorderHelper(root);
        cout << endl;
    }
    
    ~BST_Generic() {
        destroyTree(root);
    }
};

Exemplu de Utilizare

// Utilizare cu diferite tipuri
int main() {
    // Listă de întregi
    ListaGenerica<int> listaInt;
    listaInt.push_back(10);
    listaInt.push_back(20);
    listaInt.afisare();
    
    // Listă de caractere
    ListaGenerica<char> listaChar;
    listaChar.push_back('A');
    listaChar.push_back('B');
    listaChar.afisare();
    
    // Stivă de double
    StivaGenerica<double> stivaDouble;
    stivaDouble.push(3.14);
    stivaDouble.push(2.71);
    cout << "Top: " << stivaDouble.peek() << endl;
    
    // Hash table string->int
    HashTableGeneric<const char*, int> dictionar;
    dictionar.insert("mere", 5);
    dictionar.insert("pere", 3);
    
    int valoare;
    if (dictionar.find("mere", valoare)) {
        cout << "Mere: " << valoare << endl;
    }
    
    // Arbore de string-uri
    BST_Generic<string> arboreString;
    arboreString.insert("banana");
    arboreString.insert("apple");
    arboreString.insert("cherry");
    arboreString.inorder();  // apple banana cherry
    
    return 0;
}

Template cu Mai Mulți Parametri

template <typename T, int SIZE>
class ArrayFix {
private:
    T arr[SIZE];
    
public:
    T& operator[](int index) {
        if (index < 0 || index >= SIZE) {
            throw "Index invalid!";
        }
        return arr[index];
    }
    
    int size() const {
        return SIZE;
    }
};

// Utilizare
ArrayFix<int, 10> array10;  // Array fix de 10 elemente
ArrayFix<double, 5> array5;  // Array fix de 5 elemente

Specializare de Template

// Template general
template <typename T>
class Calculator {
public:
    T aduna(T a, T b) {
        return a + b;
    }
};

// Specializare pentru char*
template <>
class Calculator<char*> {
public:
    char* aduna(char* a, char* b) {
        char* rezultat = new char[strlen(a) + strlen(b) + 1];
        strcpy(rezultat, a);
        strcat(rezultat, b);
        return rezultat;
    }
};

template <typename T>
class CoadaCircularaGenerica {
private:
    T* arr;
    int front;
    int rear;
    int capacitate;
    int count;
    
public:
    CoadaCircularaGenerica(int size) {
        arr = new T[size];
        capacitate = size;
        front = 0;
        rear = -1;
        count = 0;
    }
    
    void enqueue(const T& item) {
        if (count == capacitate) {
            cout << "Coada plina!" << endl;
            return;
        }
        
        rear = (rear + 1) % capacitate;
        arr[rear] = item;
        count++;
    }
    
    T dequeue() {
        if (count == 0) {
            throw "Coada goala!";
        }
        
        T item = arr[front];
        front = (front + 1) % capacitate;
        count--;
        return item;
    }
    
    T& peek() {
        if (count == 0) {
            throw "Coada goala!";
        }
        return arr[front];
    }
    
    bool isEmpty() const {
        return count == 0;
    }
    
    bool isFull() const {
        return count == capacitate;
    }
    
    ~CoadaCircularaGenerica() {
        delete[] arr;
    }
};

template <typename T>
class VectorDinamic {
private:
    T* data;
    int size;
    int capacitate;
    
    void resize() {
        capacitate *= 2;
        T* temp = new T[capacitate];
        
        for (int i = 0; i < size; i++) {
            temp[i] = data[i];
        }
        
        delete[] data;
        data = temp;
    }
    
public:
    VectorDinamic() : size(0), capacitate(2) {
        data = new T[capacitate];
    }
    
    void push_back(const T& value) {
        if (size == capacitate) {
            resize();
        }
        data[size++] = value;
    }
    
    T& operator[](int index) {
        if (index < 0 || index >= size) {
            throw "Index invalid!";
        }
        return data[index];
    }
    
    int getSize() const {
        return size;
    }
    
    int getCapacitate() const {
        return capacitate;
    }
    
    ~VectorDinamic() {
        delete[] data;
    }
};

Probleme Practice cu Liste, Stive și Cozi

Colecție de probleme uzuale pentru exersarea structurilor de date fundamentale.

🔗 Probleme cu Liste Înlănțuite

void eliminaDuplicate() {
    if (head == NULL) return;
    
    Nod* curent = head;
    while (curent != NULL) {
        Nod* runner = curent;
        while (runner->next != NULL) {
            if (runner->next->data == curent->data) {
                Nod* dup = runner->next;
                runner->next = runner->next->next;
                delete dup;
            } else {
                runner = runner->next;
            }
        }
        curent = curent->next;
    }
}

int elementKDeLaSfarsit(int k) {
    if (head == NULL || k <= 0) return -1;
    
    Nod* p1 = head;
    Nod* p2 = head;
    
    // Mută p1 cu k poziții înainte
    for (int i = 0; i < k; i++) {
        if (p1 == NULL) return -1;
        p1 = p1->next;
    }
    
    // Mută ambii pointeri până p1 ajunge la final
    while (p1 != NULL) {
        p1 = p1->next;
        p2 = p2->next;
    }
    
    return p2->data;
}

Nod* gasesteIntersectie(Nod* head1, Nod* head2) {
    if (head1 == NULL || head2 == NULL) return NULL;
    
    // Calculează lungimile
    int len1 = 0, len2 = 0;
    Nod* temp1 = head1;
    Nod* temp2 = head2;
    
    while (temp1 != NULL) {
        len1++;
        temp1 = temp1->next;
    }
    
    while (temp2 != NULL) {
        len2++;
        temp2 = temp2->next;
    }
    
    // Resetează pointerii
    temp1 = head1;
    temp2 = head2;
    
    // Avansează în lista mai lungă
    int diff = abs(len1 - len2);
    if (len1 > len2) {
        for (int i = 0; i < diff; i++)
            temp1 = temp1->next;
    } else {
        for (int i = 0; i < diff; i++)
            temp2 = temp2->next;
    }
    
    // Parcurge în paralel
    while (temp1 != NULL && temp2 != NULL) {
        if (temp1 == temp2)
            return temp1;
        temp1 = temp1->next;
        temp2 = temp2->next;
    }
    
    return NULL;
}

void sorteaza012() {
    if (head == NULL) return;
    
    int count[3] = {0, 0, 0};
    Nod* temp = head;
    
    // Numără aparițiile
    while (temp != NULL) {
        count[temp->data]++;
        temp = temp->next;
    }
    
    // Reconstruiește lista
    temp = head;
    int i = 0;
    while (temp != NULL) {
        if (count[i] == 0) {
            i++;
        } else {
            temp->data = i;
            count[i]--;
            temp = temp->next;
        }
    }
}

Nod* adunaDuaNumere(Nod* l1, Nod* l2) {
    Nod* rezultat = NULL;
    Nod* prev = NULL;
    int carry = 0;
    
    while (l1 != NULL || l2 != NULL || carry) {
        int suma = carry;
        
        if (l1 != NULL) {
            suma += l1->data;
            l1 = l1->next;
        }
        
        if (l2 != NULL) {
            suma += l2->data;
            l2 = l2->next;
        }
        
        carry = suma / 10;
        
        Nod* nodNou = new Nod;
        nodNou->data = suma % 10;
        nodNou->next = NULL;
        
        if (rezultat == NULL) {
            rezultat = nodNou;
        } else {
            prev->next = nodNou;
        }
        prev = nodNou;
    }
    
    return rezultat;
}

📚 Probleme cu Stive

bool esteValidaExpresie(char* str) {
    StivaLista stiva;
    
    for (int i = 0; str[i] != '\0'; i++) {
        char c = str[i];
        
        if (c == '(' || c == '[' || c == '{') {
            stiva.push(c);
        }
        else if (c == ')' || c == ']' || c == '}') {
            if (stiva.isEmpty()) return false;
            
            char top = stiva.pop();
            
            if ((c == ')' && top != '(') ||
                (c == ']' && top != '[') ||
                (c == '}' && top != '{')) {
                return false;
            }
        }
    }
    
    return stiva.isEmpty();
}

void urmatorulMaiMare(int arr[], int n) {
    StivaLista stiva;
    int* rezultat = new int[n];
    
    // Parcurge de la dreapta la stânga
    for (int i = n - 1; i >= 0; i--) {
        // Elimină elementele mai mici
        while (!stiva.isEmpty() && stiva.peek() <= arr[i]) {
            stiva.pop();
        }
        
        if (stiva.isEmpty()) {
            rezultat[i] = -1;
        } else {
            rezultat[i] = stiva.peek();
        }
        
        stiva.push(arr[i]);
    }
    
    // Afișează rezultatul
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " -> " << rezultat[i] << endl;
    }
    
    delete[] rezultat;
}

int arieMaximaHistograma(int heights[], int n) {
    StivaLista stiva;
    int maxArie = 0;
    int index = 0;
    
    while (index < n) {
        if (stiva.isEmpty() || heights[index] >= heights[stiva.peek()]) {
            stiva.push(index++);
        } else {
            int top = stiva.pop();
            int arie = heights[top] * 
                       (stiva.isEmpty() ? index : index - stiva.peek() - 1);
            maxArie = (arie > maxArie) ? arie : maxArie;
        }
    }
    
    while (!stiva.isEmpty()) {
        int top = stiva.pop();
        int arie = heights[top] * 
                   (stiva.isEmpty() ? index : index - stiva.peek() - 1);
        maxArie = (arie > maxArie) ? arie : maxArie;
    }
    
    return maxArie;
}

class MinStack {
private:
    StivaLista mainStack;
    StivaLista minStack;
    
public:
    void push(int x) {
        mainStack.push(x);
        
        if (minStack.isEmpty() || x <= minStack.peek()) {
            minStack.push(x);
        }
    }
    
    void pop() {
        if (mainStack.isEmpty()) return;
        
        int top = mainStack.pop();
        if (top == minStack.peek()) {
            minStack.pop();
        }
    }
    
    int top() {
        return mainStack.peek();
    }
    
    int getMin() {
        return minStack.peek();
    }
};

void sorteazaStiva(StivaLista& stiva) {
    StivaLista tempStack;
    
    while (!stiva.isEmpty()) {
        int temp = stiva.pop();
        
        while (!tempStack.isEmpty() && tempStack.peek() > temp) {
            stiva.push(tempStack.pop());
        }
        
        tempStack.push(temp);
    }
    
    // Transferă înapoi în stiva originală
    while (!tempStack.isEmpty()) {
        stiva.push(tempStack.pop());
    }
}

🚶 Probleme cu Cozi

void genereazaBinare(int n) {
    CoadaString coada;  // Presupunem că avem o coadă de string-uri
    coada.enqueue("1");
    
    for (int i = 0; i < n; i++) {
        char* binar = coada.dequeue();
        cout << binar << " ";
        
        // Generează următoarele două numere
        char* next1 = new char[strlen(binar) + 2];
        char* next2 = new char[strlen(binar) + 2];
        
        strcpy(next1, binar);
        strcat(next1, "0");
        
        strcpy(next2, binar);
        strcat(next2, "1");
        
        coada.enqueue(next1);
        coada.enqueue(next2);
        
        delete[] binar;
    }
}

class FirstNonRepeating {
private:
    CoadaLista coada;
    int count[256];  // Pentru caractere ASCII
    
public:
    FirstNonRepeating() {
        for (int i = 0; i < 256; i++)
            count[i] = 0;
    }
    
    char adaugaCaracter(char ch) {
        count[ch]++;
        
        if (count[ch] == 1) {
            coada.enqueue(ch);
        }
        
        while (!coada.isEmpty() && count[coada.peek()] > 1) {
            coada.dequeue();
        }
        
        if (coada.isEmpty())
            return '#';  // Nu există caracter ne-repetat
        
        return coada.peek();
    }
};

void rotesteCuK(CoadaLista& coada, int k, int n) {
    k = k % n;  // În caz că k > n
    
    // Mută primele n-k elemente la final
    for (int i = 0; i < n - k; i++) {
        int temp = coada.dequeue();
        coada.enqueue(temp);
    }
}

void interschimbaJumatati(CoadaLista& coada, int n) {
    if (n % 2 != 0) return;  // Necesită număr par
    
    StivaLista stiva;
    
    // Pune prima jumătate în stivă
    for (int i = 0; i < n/2; i++) {
        stiva.push(coada.dequeue());
    }
    
    // Adaugă înapoi în coadă
    while (!stiva.isEmpty()) {
        coada.enqueue(stiva.pop());
    }
    
    // Mută a doua jumătate la final
    for (int i = 0; i < n/2; i++) {
        coada.enqueue(coada.dequeue());
    }
}

void maximFereastră(int arr[], int n, int k) {
    Deque deq;  // Deque care stochează indici
    
    // Procesează prima fereastră
    for (int i = 0; i < k; i++) {
        while (!deq.isEmpty() && arr[i] >= arr[deq.getRear()]) {
            deq.popRear();
        }
        deq.pushRear(i);
    }
    
    // Procesează restul
    for (int i = k; i < n; i++) {
        cout << arr[deq.getFront()] << " ";
        
        // Elimină elementele din afara ferestrei
        while (!deq.isEmpty() && deq.getFront() <= i - k) {
            deq.popFront();
        }
        
        // Elimină elementele mai mici
        while (!deq.isEmpty() && arr[i] >= arr[deq.getRear()]) {
            deq.popRear();
        }
        
        deq.pushRear(i);
    }
    
    cout << arr[deq.getFront()] << endl;
}

🔀 Probleme Combinate

class LRUCache {
private:
    struct CacheNode {
        int key;
        int value;
        CacheNode* prev;
        CacheNode* next;
    };
    
    CacheNode* head;
    CacheNode* tail;
    int capacitate;
    int size;
    HashTable<int, CacheNode*> map;
    
    void adaugaLaInceput(CacheNode* node) {
        node->next = head->next;
        node->prev = head;
        head->next->prev = node;
        head->next = node;
    }
    
    void stergeNod(CacheNode* node) {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }
    
public:
    LRUCache(int cap) : capacitate(cap), size(0) {
        head = new CacheNode;
        tail = new CacheNode;
        head->next = tail;
        tail->prev = head;
    }
    
    int get(int key) {
        CacheNode* node;
        if (map.find(key, node)) {
            stergeNod(node);
            adaugaLaInceput(node);
            return node->value;
        }
        return -1;
    }
    
    void put(int key, int value) {
        CacheNode* node;
        if (map.find(key, node)) {
            node->value = value;
            stergeNod(node);
            adaugaLaInceput(node);
        } else {
            CacheNode* newNode = new CacheNode;
            newNode->key = key;
            newNode->value = value;
            
            if (size == capacitate) {
                CacheNode* lru = tail->prev;
                stergeNod(lru);
                map.remove(lru->key);
                delete lru;
                size--;
            }
            
            adaugaLaInceput(newNode);
            map.insert(key, newNode);
            size++;
        }
    }
};

bool estePalindrom(char* str) {
    StivaLista stiva;
    CoadaLista coada;
    
    // Adaugă caracterele în ambele structuri
    for (int i = 0; str[i] != '\0'; i++) {
        if (isalnum(str[i])) {  // Doar litere și cifre
            char ch = tolower(str[i]);
            stiva.push(ch);
            coada.enqueue(ch);
        }
    }
    
    // Compară elementele
    while (!stiva.isEmpty()) {
        if (stiva.pop() != coada.dequeue()) {
            return false;
        }
    }
    
    return true;
}

bool verificaSecventa(int pushed[], int popped[], int n) {
    StivaLista stiva;
    int j = 0;
    
    for (int i = 0; i < n; i++) {
        stiva.push(pushed[i]);
        
        while (!stiva.isEmpty() && j < n && 
               stiva.peek() == popped[j]) {
            stiva.pop();
            j++;
        }
    }
    
    return stiva.isEmpty();
}

int lungimeMaximaParanteze(char* str) {
    StivaLista stiva;
    stiva.push(-1);
    int maxLen = 0;
    
    for (int i = 0; str[i] != '\0'; i++) {
        if (str[i] == '(') {
            stiva.push(i);
        } else {
            stiva.pop();
            
            if (stiva.isEmpty()) {
                stiva.push(i);
            } else {
                int len = i - stiva.peek();
                maxLen = (len > maxLen) ? len : maxLen;
            }
        }
    }
    
    return maxLen;
}

class TicketingSystem {
private:
    CoadaLista coadaUrgenta;
    CoadaLista coadaNormala;
    CoadaLista coadaJoasa;
    int ticketCounter;
    
public:
    TicketingSystem() : ticketCounter(1) {}
    
    int creazaTicket(int prioritate) {
        int ticketId = ticketCounter++;
        
        switch(prioritate) {
            case 1: coadaUrgenta.enqueue(ticketId); break;
            case 2: coadaNormala.enqueue(ticketId); break;
            case 3: coadaJoasa.enqueue(ticketId); break;
        }
        
        return ticketId;
    }
    
    int proceseazaUrmatorul() {
        if (!coadaUrgenta.isEmpty()) {
            return coadaUrgenta.dequeue();
        } else if (!coadaNormala.isEmpty()) {
            return coadaNormala.dequeue();
        } else if (!coadaJoasa.isEmpty()) {
            return coadaJoasa.dequeue();
        }
        return -1;  // Niciun ticket
    }
};

Exerciții Complexe și Aplicații

class UndoRedo {
private:
    StivaLista undoStack;
    StivaLista redoStack;
    int currentState;
    
public:
    UndoRedo() : currentState(0) {}
    
    void setState(int newState) {
        undoStack.push(currentState);
        currentState = newState;
        
        // Clear redo stack când facem o acțiune nouă
        while (!redoStack.isEmpty()) {
            redoStack.pop();
        }
    }
    
    void undo() {
        if (!undoStack.isEmpty()) {
            redoStack.push(currentState);
            currentState = undoStack.pop();
        }
    }
    
    void redo() {
        if (!redoStack.isEmpty()) {
            undoStack.push(currentState);
            currentState = redoStack.pop();
        }
    }
    
    int getState() {
        return currentState;
    }
};

class BrowserHistory {
private:
    struct Page {
        char url[100];
        Page* prev;
        Page* next;
    };
    Page* current;
    
public:
    BrowserHistory(const char* homepage) {
        current = new Page;
        strcpy(current->url, homepage);
        current->prev = current->next = NULL;
    }
    
    void visit(const char* url) {
        Page* newPage = new Page;
        strcpy(newPage->url, url);
        newPage->prev = current;
        newPage->next = NULL;
        
        // Șterge istoricul forward
        Page* temp = current->next;
        while (temp != NULL) {
            Page* deSters = temp;
            temp = temp->next;
            delete deSters;
        }
        
        current->next = newPage;
        current = newPage;
    }
    
    char* back() {
        if (current->prev != NULL)
            current = current->prev;
        return current->url;
    }
    
    char* forward() {
        if (current->next != NULL)
            current = current->next;
        return current->url;
    }
};

* La început | ** În medie | *** Pentru arbore echilibrat

template <typename T>
class Graf {
private:
    HashTableGeneric<T, ListaGenerica<T>*> listeAdiacenta;
    
public:
    void adaugaNod(const T& nod) {
        ListaGenerica<T>* lista = new ListaGenerica<T>;
        listeAdiacenta.insert(nod, lista);
    }
    
    void adaugaMuchie(const T& sursa, const T& dest) {
        ListaGenerica<T>* lista;
        if (listeAdiacenta.find(sursa, lista)) {
            lista->push_back(dest);
        }
    }
    
    void BFS(const T& start) {
        HashTableGeneric<T, bool> vizitat;
        CoadaGenerica<T> coada(100);
        
        vizitat.insert(start, true);
        coada.enqueue(start);
        
        cout << "BFS: ";
        while (!coada.isEmpty()) {
            T nod = coada.dequeue();
            cout << nod << " ";
            
            ListaGenerica<T>* vecini;
            if (listeAdiacenta.find(nod, vecini)) {
                // Parcurge vecinii
                // Implementare simplificată
            }
        }
        cout << endl;
    }
};