Stivă (structură de date)

O stivă (engleză stack) este o structură de date ale cărei elemente sunt considerate a fi puse unul peste altul, astfel încât orice element adăugat se pune în vârful stivei, iar extragerea unui element se poate face numai din vârful acesteia, în ordinea inversă celei în care elementele au fost introduse, asemănător cu modul în care ai aranja mai multe farfurii una peste alta.

Generalități

Stiva este o structură de date larg utilizată în informatică; dintre multiplele utilizări, stiva este folosită atât la implementarea algoritmilor recursivi, cât și ca structură auxiliară la traversarea unor structuri de date mai complicate, cum sunt arborii și grafurile. Implementarea stivei se poate face pe o structură de tip vector, ce presupune cunoașterea apriori a dimensiunii maxime a stivei, sau pe o structură de date tip listă, unde dimensiunea maximă este limitată doar de capacitate memoriei RAM. Așadar, stiva este un caz particular de listă, în care adăugarea sau eliminarea elementelor se face numai în unul din capetele acesteia, iar pentru parcurgerea unei stive implementate pe o structură de tip listă este suficientă referința către primul element al listei. În cazul când stiva este implementată sub formă de tablou, punerea și eliminarea elementelor se face la capătul „din dreapta” (pe poziția din tablou cu cea mai mare valoare a indicelui). În acest fel, la efectuarea acestor operații nu este necesar să se deplaseze celelalte elemente ale tabloului. Având o dimensiune limitată, în algoritmi, această problemă se rezolvă de obicei, prin copierea stivei curente într-o nouă stivă cu dimensiuni duble.

Operații

Stiva este concepută pe principiul LIFO (last in, first out — ultimul intrat este primul ieșit). Principalele operații asupra stivei sunt cele enumerate mai jos.

Creare

Pentru a crea o stiva vidă se ințializează vârful stivei cu –1 (vârful stivei indică întotdeauna poziția ultimului element, acestea fiind memorate începând cu poziția 0).

Inserare

Pentru a insera un element e în vârful stivei S (operația push) este necesară, în primul rând, verificarea stivei pentru a stabili dacă este sau nu plină. Dacă acest lucru este îndeplinit, se memorează elementul și se incrementează dimensiunea; în caz contrar sarcina nu se poate îndeplini.

Extragere

Pentru a extrage un element din vârful stivei (operația pop) trebuie ca stiva să nu fie vidă. Dacă nu este, atunci se reține valoarea din vârful stivei într-o variabilă e și se decrementează vârful.

Vizitare

Accesarea/vizitarea elementului de la vârf stivei presupune determinarea valorii acestuia, valoare care se va reține într-o variabilă e, fără a o extrage.

Se poate observa că ultimele trei operații au complexitatea O(1), iar prima operație complexitatea O(n).