Stiva - Utilitatea stivelor - Accesarea elementului de la varf

Stiva

Stiva este o structura de date abstracta pentru care atat operatia de inserare a unui element in structura, cat si operatia de extragere a unui element se realizeaza la un singur capatm denumit varful stivei.

Singurul element din stiva la care avem acces direct este cel de la varf.

Operatii caracteristice

Singurele operatii care pot fi executate cu o stiva sunt:

• crearea unei stive vide;
• inserarea unui element in stiva (operatie denumita in literatura de specialitate PUSH);
• extragerea unui element din stiva (operatie denumita in termeni de specialitate POP);
• accesarea elementului de la varf (operatie denumita TOP).

Utilitatea stivelor

In informatica, stiva joaca un rol fundamental. Pentru a intelege mecanismele fundamentale ale programarii (de exemplu, functiile sau recursivitatea) este necesara cunoasterea notiunii de stiva. Pe scurt, stiva este utila in situatii in care este necesara memorarea unor informatii si regasirea acestora intr-o anumita ordine, descrisa de principiul LIFO. Stiva este utilizata atunci cand programul trebuie sa amane executia unor operatii, pentru a le executa ulterior, in ordinea inversa a aparitiei lor. Operatia curenta este cea corespunzatoare varfului stivei, in stiva fiind retinute toate informatiile necesare programului pentru a executa operatiile respective.

Accesarea elementului de la varf

Stiva este o structura de date abstracta, ce poate fi implementata in diferite moduri. De exemplu, putem implementa o stiva ca un vector in care retinem elementele stivei. Pentru ca acest vector sa functioneze ca o stiva, singurele operatii permise sunt operatiile caracteristice stivei.

Pentru exemplificare, voi prezenta declaratiile necesare pentru implementarea unei stive cu elemente te tip int:

#define DimMax 100 //numarul maxim de elemente din stiva

typedef int Stiva[DimMax]; //tipul de stiva implementat ca vector

Stiva S; //stiva

int vf; //varful stivei

Crearea unei stive vide

Pentru a crea o stiva vida, initializam varful stivei cu (varful stivei indica intotdeauna pozitia ultimului element introdus in stiva; elementele sunt memorate in vector incepand cu pozitia

vf

Inserarea unui element in stiva

Pentru a insera un element x in stiva S trebuie sa verificam in primul rand daca "este loc", deci stiva nu este plina. Daca stiva este plina, inserarea nu se poate face, altfel vom mari varful stivei si vom plasa la varf noul element.

De exemplu, daca dorim sa inseram elementul x=3 in stiva din figura urmatoare, obtinem:

   

Stiva S inainte de inserare Stiva S dupa inserare

if (vf == DimMax-1) //stiva este plina

cout<<"Eroare - stiva este plina";

else

S[++vf] = x; //inseram elementul x in stiva s

Accesarea elementului de la varf

Prin modul sau restrictiv de functionare, stiva permite numai accesarea elementului de la varf. Daca dorim sa aflam valoarea unui alt element al stivei, ar trebui sa "golim" stiva (deci sa extragem succesiv elemente) pana la elementul dorit.

Accesarea elementului de la varf presupune determinarea valorii acestuia, valoare pe care o vom obtine intr-o variabila denumita x.

x = S[vf];

Observatii

1. Dezavantajul implementarii unei stive ca vector alocat static consta in faptul ca indiferent de numarul de elemente existente in stiva, dimensiunea zonei de memorie alocata stivei este aceeasi (DimMax).
2. Pentru a executa operatii cu stiva alocata static este suficient sa cunoastem varful stivei. Ca sa retinem mai usor modul de functionare al stivei, ne imaginam ca la inserare, varful stivei urca, iar la extragere, coboara.