CATEGORII DOCUMENTE |
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:
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
Politica de confidentialitate | Termeni si conditii de utilizare |
Vizualizari: 1753
Importanta:
Termeni si conditii de utilizare | Contact
© SCRIGROUP 2024 . All rights reserved