Curs C++ | Sectiunea 31 – Implementare Procedurala Stack

❓ Ce legatura are un “stack” cu programarea orientata pe obiecte? Ei bine, nu are nicio legatura, cel putin nu una evidenta, inca 🙂 . Aveti putina rabdare si vom afla impreuna toate raspunsurile.

Ce este un Stack?

📚 Un stack(stiva) este o structura construita pentru a stoca date intr-un mod specific si unic. Incercati sa va imaginati un teanc de carti, una pusa peste alta. Daca dorim sa adaugam o carte va trebui sa o punem deasupra si daca dorim sa extragem una, va trebui sa le extragem pe toate pana ajungem la cea dorita.

💡 Numele alternativ pentru un stack, in cazul lumii IT, este LIFO (Last In First Out). Conform traducerii noastre, “primul venit ultimul servit“, sau conform exemplului anterior, folosind cartile, prima carte adaugata va fi extrasa ultima.

Aceasta structura de date poate executa doua operatii elementare:

• push – adauga un nou element in varf
• pop – elimina primul element din varf

Dorim sa implementan aceasta structura folosind doua abordari diferite. Prima va fi cea procedurala iar apoi vom incerca sa folosim noile concepte invatate, de programare pe obiecte.

Declarare

❓ Trebuie sa ne decidem mai intai cum sa stocam valorile intregi in interior. Putem alege cea mai simpla metoda, folosind un vector. Sa presupunem, desi nu este presupunere tocmai corecta, ca nu vom avea mai mult de 1000 de valori in acelasi timp.

De asemenea, facem si presupunerea ca elementul de la pozitia 0 se afla la fundul stivei. Declararea va arata astfel:

int stack[1000];

Stack Pointer

Vectorul nostru nu este suficient pentru implementare, fiind nevoie de cateva lucruri aditionale. Avem nevoie spre exemplu de o variabila ce salveaza numarul elementelor stocate in prezent in stiva.

#️⃣ Acesta variabila este in general numita stack pointer, sau pe scurt, SP. Initial, stiva noastra este goala, deci si stack pointer va avea valoarea 0.

int SP = 0;

Push

Suntem pregatiti sa definim o functie ce are rolul de a adauga noi elemente in stiva. Avem urmatoarele cerinte de indeplinit.

• numele functiei este push
• primeste un singur parametru de tip int, reprezentand valoara ce va fi adaugata
• nu returneaza nimic, deci va fi o functie void
• elementul va fi adaugat pe primul loc liber urmand ca apoi sa incrementeze SP

void push(int value) {
	stack[SP++] = value;
}

❗ Bineinteles, nu este o functie perfecta, spre exemplu nu verificam daca exista loc pentru un nou element, sau am atins capacitatea maxima a stivei. Dar sa omitem aceste detalii momentan.

Pop

Mai departe implementam si functia ce are rolul de a extrage un element din stiva.

• numele functiei este pop
• nu are nevoie de niciun parametru
• returneaza valoarea ce va fi extrasa din stiva
• citeste valoarea extrasa din stiva si decrementeaza SP

int pop(void) {
	return stack[--SP]
}

Si in acest caz, functia nu este perfecta. Nu verificam spre exemplu daca exista vreun element in stiva, putand fi goala.

Rezultatul final

Odata ce am definit toate functionalitatile putem sa le asamblam si sa facem un test. Codul va arata astfel.

int stack[1000];
int SP = 0;

void push(int value) {
	stack[SP++] = value;
}

int pop(void) {
	return stack[--SP];
}

int main(void) {
	push(30);
	push(20);
	push(10);
	cout << pop() << endl; //10
	cout << pop() << endl; //20
	cout << pop() << endl; //30
	return 0;
}

Pros & Cons

Acum ca am finalizat implementarea noastra procedurala, chiar si trecand peste anumite lucruri pe care nu le verificam dar care se pot rezolva, tot prezinta foarte multe dezavantaje.

• variabilele noastre esentiale, stack si SP sunt complet vulnerabile, oricine le poate modifica si altera, iar acest lucru nu in mod constient cel mai probabil
• este foarte posibil sa avem nevoie de mai mult de un stack, in functie de context, imaginati-va ca va trebui sa duplicam tot ce am scris, functii, variabile
• se poate intampla sa avem nevoie de mai multe functii decat pop si push, adaugand aceasta nevoie si la posibilitatea de a avea nevoie de mai multe stive, va fi foarte confuz si greu de urmarit codul
• am folosit elemente de tip int pentru stocare, dar daca am dori sa stocam elemente de tip float, sau chiar string?

💡 Programarea orientata pe obiecte ne ofera o solutie pentru fiecare din probleme mentionate anterior.

• posibilitatea de a ascunde (proteja) anumite date, variabile impotriva accesului neautorizat, purtand numele de incapsulare (encapsulation)
• odata ce am definit o clasa ce implementeaza caracteristicile si comportamentul unei stive, putem crea oricate stive avem nevoie, fara a duplica ce am scris deja
• abilitatea de a adauga o noua functionalitate este realizata de conceptul de mostenire (inheritance); avem posibiltatea sa cream o sub-clasa ce va mosteni trasaturile si functionalitatile super-clasei si chiar sa adauge unele noi
• putem crea un template, ce reprezinta in general, o clasa parametrizata; acest lucru ne permite spre exemplu sa avem o clasa ce se va modifica in functie de tipul de date pe care il folosim

Aici se termina si aceasta sectiune. In urmatoarea vom realiza si implementarea orientata pe obiecte a stivei noastre. Pentru intrebari suplimentare puteti folosi informatiile de aici 🙂 .

➡ Sectiunea anterioara:Curs C++ | Sectiunea 30 – Concepte de baza POO

➡ Sectiunea urmatoare:Curs C++ | Sectiunea 32 – Implementare POO Stack