Stiva este o structură de date abstractă, pentru care atât operaţia de inserare a unui element în structură, cât şi operaţia de extragere a unui element, se realizează la un singur capăt, denumit vârful stivei. Singurul element din stivă la care avem acces direct este cel de la vârf.

Operaţii caracteristice

Singurele operaţii ce pot fi executate cu o stivă sunt:

• crearea unei stive vide;
• inserarea unui element în stivă (operaţie denumită PUSH).
• extragerea unui element din stivă (operaţie denumită POP).
• accesarea elementului de la vârf (operaţie denumită TOP ).

Notaţii:

• În traducere exactă, PUSH înseamnă „a împinge”. Termenul sugerează o imagine plastică: imaginându-ne stiva ca un sac, PUSH ar însemna că împingem înăuntru un element, prin capătul superior (nu prin mijloc sau pe la fundul sacului).
• În traducere, POP înseamnă „a scoate cu zgomot (de exemplu dopul, etc), a descărca (pistolul, etc), a ieşi repede sau pe neaşteptate” . Imaginea este de asemeni sugestivă: POP este operaţia prin care primul element, cel de deasupra, „sare” din structură (sau din sac, ca să păstrăm analogia).
• În traducere, TOP înseamnă „vârf”.

Up Home Structura Site 

Ca să ne imaginăm mai bine funcţionarea unei stive, să ne gândim cum lucrăm cu un teanc de farfurii. Când dorim să punem o farfurie în teanc, o punem deasupra, când dorim să luăm o farfurie din teanc, o luăm tot pe cea de deasupra. Motivul este lesne de înţeles: nu ne-am propus să spargem farfuriile!

Acest mod de funcţionare face ca ultimul element inserat în stivă să fie primul extras. Din acest motiv, stiva este definită şi ca o structură de date care funcţionează după  principiul LIFO (Last In First Out – Ultimul Intrat Primul Ieşit).

 Up Home Structura Site

 

Care este utilitatea stivelor?

În informatică, stiva joacă un rol fundamental. Pentru a înţelege mecanisme fundamentale ale programării (de exemplu, funcţiile sau recursivitatea) este necesară cunoaşterea noţiunii de stivă. Pe scurt, stiva este utilă în situaţii în care este  necesară  memorarea  unor  informaţii  şi  regăsirea  acestora  într-o  anumită ordine, descrisă de principiul LIFO. Stiva este utilizată atunci când programul trebuie să amâne execuţia unor operaţii, pentru a le executa ulterior, în ordinea inversă a apariţiei lor.

Operaţia curentă este cea corespunzătoare vârfului stivei, în stivă fiind reţinute toate informaţiile necesare programului pentru a executa operaţiile respective.

Up Home Structura Site

 

Cum implementăm o stivă?

Stiva este o structură de date abstractă, ce poate fi implementată în diferite moduri. De exemplu, putem implementa o stivă ca un vector în care reţinem elementele stivei. Pentru ca acest vector să funcţioneze ca o stivă, singurele operaţii permise sunt operaţiile caracteristice stivei.

Pentru exemplificare, să prezentăm declaraţiile 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

Up Home Structura Site

 

Crearea unei stive vide

Pentru a crea o stivă vidă iniţializăm vârful stivei cu -1 (vârful stivei indică întotdeauna poziţia ultimului element introdus în stivă; elementele sunt memorate în vector începând cu poziţia 0):

vf = -1;

Up Home Structura Site

 

Inserarea unui element în stivă

Pentru a insera un element x  în stiva S,  trebuie să verificăm în primul rând dacă „avem loc”, deci dacă stiva nu este plină. Dacă stiva este plină, inserarea nu se poate face, altfel vom mări vârful stivei şi vom plasa la vârf noul element.

De  exemplu,  dacă  dorim  să  inserăm  elementul  x =  3  în  stiva  din  figura următoare, obţinem:

if (vf = = DimMax - 1)                        //  stiva este plina
cout << “Eroare – stiva este plina”<<endl;
else                                                      //  inseram elementul x in stiva S
S[++vf] = x;

Up Home Structura Site

 

Extragerea unui element din stivă

Pentru a extrage un element dintr-o stivă S,  trebuie să verificăm în primul rând dacă există elemente în stivă (deci dacă stiva nu este vidă). Dacă da, reţinem elementul de la vârful stivei într-o variabilă (să o notăm x), după care micşorăm cu o unitate vârful stivei. De exemplu, dacă extragem un element din stiva din figura următoare, obţinem:

Stiva S înainte de extragere                Stiva S după de extragere
if (vf < 0)                    //  stiva este vida
cout << “Eroare – stiva este vida”<<endl;
else                                                      //  extragem elementul de la varf
x = S[vf--] ;

 Up Home Structura Site

 

Accesarea elementului de la vârf

Prin modul său restrictiv de funcţionare, stiva permite numai accesarea elementului de la vârf. Dacă dorim să aflăm valoarea unui alt element al stivei, ar trebui să „golim”  stiva  (deci  să  extragem  succesiv  elemente)  până  la  elementul  dorit.
Accesarea elementului de la vârf presupune determinarea valorii acestuia, valoare pe care noi o vom reţine într-o variabilă denumită x.

x = s[vf];

Observaţii:

• Dezavantajul implementării unei stive ca vector alocat static constă în faptul că, indiferent de numărul de elemente existente în stivă, dimensiunea zonei de memorie alocată stivei este aceeaşi (DimMax).

 

• Pentru a executa operaţii cu stiva alocată static, este suficient să cunoaştem vârful stivei. Ca să reţinem mai uşor modul de funcţionare a stivei, ne imaginăm că la inserare vârful stivei urcă, iar la extragere vârful coboară.

  Up Home Structura Site

 

 

 

A. Ceva - eventual

Up Home Structura Site