- Publicat în
Structuri de Date Fundamentale: Stacks (Stive)
- Autori
- Name
- Gabriel Nechita
- Citeste articolul in:
- /4 min read
Despre acest articol
Ce conține acest articol?
Ce este un stack
Un stack este o structura de date de tip "first in, last out" (FILO), adica primul intrat, ultimul iesit.
Pentru ca ideea asta de FILO poate fi exprimata si in alte feluri, vei gasi prin articole ideea ca stack-ul este o structura de date de tip "last in, first out" (LIFO), adica ultimul intrat primul iesit.
Daca lucrezi cu JavaScript, poate ai auzit foarte des despre un mecanism numit "call stack". Ei bine, acest articol o sa lamureasca cum functioneaza un general un stack, inclusiv pe cel din JavaScript.
In general nu imi place sa traduc termeni din computer science in limba romana, pentru ca imi place sa scriu cum vorbesc in viata reala si pentru ca stiu ca asa vorbesc toti programatorii cu care am lucrat.
De asemenea, pentru ca vreau ca articolele mele sa fie citite de cat mai multe persoane, o sa ma tot vezi ca folosesc intersanjabil cuvintele lista si array din cand in cand pentru a putea optimiza continutul pentru motoarele de cautare.
Ce poti sa faci cu un stack
Intr-o stiva (stack), poti sa faci urmatoarele operatiuni:
- poti sa adaugi (insert sau push)
- poti sa vezi care este item-ul de la capatul de sus al stivei (peek ultimul element care nu a fost inca sters din stack)
- poti sa stergi ultimul element din stack (pop)
Daca vrei sa-ti imaginezi un obiect care seamana cu un stack, imagineaza-ti ca iti faci o lista cu lucrurile pe care trebuie sa le duci la capat intr-o zi de munca.
Sa zicem ca ai adunat 10 lucruri. Fiecare "task" il vei scrie pe un post-it note si le vei aseza intr-o stiva.
Primul element din stiva ta, va fi primul element la care te-ai gandit, dar va fi si ultimul element care va fi inlaturat din stack-ul de post-it notes, pentru ca va trebui sa te ocupi mereu de ce e la capatul superior al stivei tale.
Pe masura ce duci la indeplinire planurile tale pe astazi, s-ar putea sa mai intervina lucruri neprevazute si sa mai adaugi post-it notes la stiva ta.
Un stack este o structura de date atat de elementara, incat o vom intalni in mai toate limbajele de programare care sunt inspirate din C (Go, JavaScript, Swift, C#, Python, Java, Perl, PHP etc).
Cand vei citi despre cum functioneaza un stack, foarte des vei vedea acest subiect combinat cu ideea de recursivitate (recursion), pentru ca ele merg mana in mana.
Daca ai o functie care se apeleaza in continuu pe sine, vei da peste ceea ce se numeste "stack overflow" - practic functia ta va consuma toata memoria alocata stack-ului. Practic, stack-ul tau va da pe dinafara :).
Odată la 1-2 săptămâni îți voi trimite un rezumat cu cele mai interesante lucruri pe care le-am descoperit și cu articolele pe care le-am publicat pe acest blog.
0 spam. Te poți dezabona oricând. Nu voi folosi adresa ta de email în alte scopuri promoționale.
Cum functioneaza un stack de fapt
Mai sus am vorbit foarte sumar despre ideea de "stack overflow", cand stiva ta da efectiv pe dinafara si nu mai poate accepta new items.
Ei bine, situatia asta depinde foarte mult de la un limbaj de programare la altul, in functie de cum functioneaza stack-ul respectiv.
De exemplu, "call stack"-ul din JavaScript va fi suspectibil la un "stack overflow" atunci cand ai un "endless loop" sau ai o functie recursiva care nu are nicio conditie pentru a fi da skip la cazul recursiv.
La fel cum o stiva poate da pe din-afara, aceasta poate sa dea si pe "dinauntru" si anume sa incerci sa faci pop intr-un stack care nu mai are niciun element.
Pentru a evita situatia aceasta, trebuie doar sa verific daca stack-ul este gol inainte de a face pop.
Asadar, daca implementezi un stack, ar fi bine sa ai cele 2 situatii in minte (underflow si overflow) sau macar sa le mentionezi ca potentiale situatii problematice daca intervine discutia intr-un interviu.
Complexitatea (Big O) unui stack
| Operatiune | Stack |
|---|---|
| (Peek) Accesarea ultimul element | O(1) |
| (Push) Inserarea a unui nou element la final | O(1) |
| (Pop) Indepartarea ultimului element | O(1) |
| (Cautare) Gasirea elementului X | O(n) |