Stiva

Stiva

O stiva (stack) este o lista liniara cu proprietatea ca operatiile de inserare / extragere a nodurilor se fac in/din coada listei. Daca nodurile A, B, C, D sunt inserate intr-o stiva in aceasta ordine, atunci primul nod care poate fi extras este D.

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

Operatii caracteristice (singurele care pot fi executate)

crearea unei stive vide;

inserarea unui element in stiva (PUSH[1]);

extragerea unui element din stiva (POP[2]);

accesarea elementului de la varf (TOP[3]).

Acest mod de functionare face ca ultimul element inserat in stiva sa fie primul extras, motiv pentru care stiva este definita si ca o structura de date care functioneaza dupa principiul LIFO (ultimul intrat primul iesit)

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. 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 inverse a aparitiei lor. Operatia curenta este cea corespunzatoare varfului stivei, in stiva fiind retinute toate informatiile necesare programului pentru a executa operatiile respective

Implementarea unei stive

Stiva este o strucutra de date abstracta, ce poate fi implementata in diferite moduri. De exemplu, cu un vector in care retinem elementele stivei. Pentru ca acest vector sa functioneze ca o stiva, singurele operatii premise sunt operatii caracteristice stivei. Cele mai avantajoase implementari ale structurii de date stiva sunt cele cu ajutorul tipului pointer si al tipului tablou

Asupra tipului abstract de date stiva sunt definiti urmatorii cinci operatori:

1.INITIALIZARE(S) - face stiva S vida ( initializeaza lista corespunzatoare )

2.VIRFST(S) - furnizeaza elementul din varful stivei ( deci primul nod al listei )

3.POP(S) - suprima elementul din varful stivei

4.PUSH(x,S) - insereaza elementul x in varful stivei pe care il actualizeaza

5.STIVID(S) - functie booleana ce e adevarata daca stiva este vida.

Pentru exemplificare, sa prezentam declaratiile necesare pentru implementarea unei stive cu elemente de tip int:

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

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

stiva S; //stiva

int vf; //varful stivei

troduse.