Stivă (structură de date)

De la Wikipedia, enciclopedia liberă
Salt la: Navigare, căutare
Stivă implementată prin listă

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.

Generalități[modificare | modificare sursă]

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[modificare | modificare sursă]

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[modificare | modificare sursă]

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[modificare | modificare sursă]

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[modificare | modificare sursă]

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[modificare | modificare sursă]

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).

Structuri de date simple[modificare | modificare sursă]

Bibliografie[modificare | modificare sursă]

  • Severin Bumbaru, Universitatea „Dunărea de Jos” Galați, Structuri de date și tehnici de proiectarea a algoritmilor

Legături externe[modificare | modificare sursă]

Commons
Wikimedia Commons conține materiale multimedia legate de Stivă (structură de date)