start     Articole     Despre mine     Contact     Cursul ABCprog    

Cum implementezi o stiva folosind un vector

Un aspect al programarii care nu este deloc clar celor care sunt la inceput este acela ca programarea nu inseamna doar instructiuni prin care ii spui calculatorului ce actiuni sa efectueze.

Bineinteles ca acesta este aspectul cel mai important si care e resonsabil de rezultatele pe care le vezi atunci cand executi un program.

Dar asta nu e totul.
Programarea mai inseamna si altceva. Un altceva foarte important, fara de care actiunile de care vorbim nu ar avea putere.

Acel altceva sunt structurile de date.

Daca ar fi sa scriu intr-un soi de formula matematica simpla ce inseamna un program, ar iesi ceva de genul:

       Program = Date + Instructiuni

(Am vorbit despre asta si in explicatiile de la jocul de labirint.)

 

Deja ai lucrat cu structuri de date. Vectorii sunt cele mai simple structuri de date. (Iar matricile reprezinta de fapt generalizarea vectorilor pentru cazul bidimensional (adica in doua dimensiuni: linii si coloane).)

In articolul asta o sa te joci cu o structura de date putin mai restrictiva decat un vector, dar care poate fi implementata cu mare usurinta folosind un vector si o variabila (simpla).

Stiva

Cu siguranta stii ce e o stiva. Daca nu, ia o cutie de carton si pune in ea o carte. Apoi mai pune o carte peste prima carte. Si inca o carte peste a doua.

OK?

Acum ai trei carti (situate una peste alta) in stiva.

Scoate o carte.

Evident, vei scoate ultima carte pusa (adica cea care e situata in varful stivei).

 

Te-ai prins cum functioneaza o stiva?

(1) Poti pune elemente in ea doar in varf (peste ultimul element pus).

(2) Si poti scoate elemente din ea doar de la varf.

Ultimul element introdus in stiva este primul care va fi scos (atunci cand va fi cazul sa scoti un element din ea). In limba engleza la treaba asta ii zice LIFO (Last In, First Out).

Cum se implementeaza o stiva

Cel mai simplu poti implementa o stiva folosind un vector S (cu un numar de elemtne suficient de mare pentru a incapea in el toate elementele caer se vor adauga in stiva la vreun moment dat) si o variabila v (in care se va memora indicele pozitiei din vector de deasupra ultimului element din stiva).

Desenul urmator vrea sa explice cele spuse in paragraful anterior.

Prin urmare, atunci cand vrei sa adaugi un element in stiva faci asa:

       S[v] = element_nou;
       v = v+1;

Iar atunci cand vrei sa scoti un element din stiva, faci asa:

       v = v-1;
       element_scos = S[v];

 

Initial, cand stiva e goala, v va avea valoarea 0. (Adica varful stivei va indica baza stivei.)

Valoarea lui v poate fi interpretata si ca fiind numarul de elemente existente in stiva.

 

Cel mai bine inveti facand, asa ca iata mai jos simulatorul nostru. Apasa “Reseteaza…” si apoi “Executa…”. Vei vedea pe ecran 10 puncte colorate dispuse aleator. Prin click pe un punct colorat, acel punct se va adauga in stiva din dreapta (pe coloana cu coordonata x egala cu 11, deci imediat in afara ecranului de 10×10 puncte). (In felul acesta vei putea vedea la lucru operatiunea de adaugare in stiva.) Prin click pe un punct alb, acel punct se va completa cu un element din stiva. (Vei vedea astfel cum lucreaza operatiunea de scoatere din stiva.)

(Browserul tau nu suporta Canvas!…)

 

E amuzanta stiva, nu-i asa? 🙂 Am o veste buna: stiva nu e singura structura de date amuzanta, asa ca te asteapta un drum foarte interesant in continuare.

Alatura-te celor peste 1000 de oameni din armata noastra de creiere cu muschi si vei primi testul care iti va spune daca ai sau nu minte de programator:

(nu trimit spam; te tin la curent cu noutatile)


 

Cu drag,

Florin





Loading Facebook Comments ...