De ce contează?
Imaginează-ți un teanc de farfurii curate pe blatul din bucătărie. Când speli o farfurie, o pui deasupra. Când ai nevoie de una, o iei tot de deasupra — nu te apuci să tragi una din mijloc, că se prăbușește tot. Ultima farfurie pusă e prima pe care o iei. Exact așa funcționează o stivă.
Ce este
O stivă (engl. stack) este o structură de date în care adaugi și scoți elemente doar la un singur capăt, numit vârf. Regula ei se numește LIFO — Last In, First Out: ultimul element intrat este primul care iese.
std::stack din STL este un adaptor: nu e o structură nouă scrisă de la
zero, ci o „cochilie" peste un container (implicit deque) care îți expune doar
operațiile de stivă. Are exact cinci operații, toate în timp constant O(1):
push(x)— punexdeasuprapop()— scoate elementul din vârf (nu îl returnează)top()— îți arată vârful, fără să-l scoatăempty()— spune dacă stiva e goalăsize()— câte elemente sunt în stivă
Singurul element pe care îl poți vedea sau atinge este vârful. Nu există
indexare (st[2] nu compilează) și nu poți parcurge stiva cu iteratori. Dacă vrei
al treilea element de jos, trebuie să scoți tot ce e deasupra lui — restricția
asta e tocmai puterea stivei: te forțează să gândești „ultimul intrat".