fbpx

Ce este stiva in C++ ? Cum functioneaza?

0

Ce este stiva ?

Stiva (sau „stack” in limba engleza) este o structură de date liniara ce lucreaza cu o colectie de date avand doua operatii principale:

  • push(int numar) – adauga numar in stiva
  • pop() – sterge ultimul element adaugat in lista (peek() – returneaza valoarea acestui element – deseori functia pop() contine si functia peek() integrata).

Modul in care acesta prelucreaza elementele i-a dat denumirea de LIFO ( Last In First Out=  ultimul venit-primul servit ).

Cum functioneaza stiva?

Avand in vedere ca este o structura de date secventiala, operatiile push si pop se intampla numai la capatul structurii (acest „capat” este numit top). Acest detaliu permite stivei sa fie implementata ca o lista simpla inlantuita. De mentionat este faptul ca stiva este o structura de date cu un numar total de elemente flexibil.

Stiva functioneaza pe principiul LIFO, imginati-va de exemplu mai multe farfurii expuse pe raft intr-un IKEA.

Stiva - farfurii

In mod normal cand faceti cumparaturile puneti in cos prima farfurie. Pe baza acestui principiu functioneaza si stiva – orice element adaugat în ea va fi pus in varful (capatul / top-ul) stivei, iar atunci când dorim sa accesam o anumita farfurie, incepem sa o parcurgem de la varf către baza (nu invers – le-ai sparge pe toate daca ai face invers).

La ce este folosita stiva?

  • Backtracking – in momentul cand vrei sa parcurgi un labirint si te blochezi, pentru a retine pasii ce i-ai facut, ii memorezi intr-o stiva. Daca doresti sa te intorci inapoi un anumit numar de pasi, scoti pe rand coordonatele geografice din stiva.
  • Inversarea unui string – Daca doresti sa construiesti imaginea in oglinda a unui string (de exemplu din „mere” sa faci „erem” – vei folosii o stiva). Pe masura ce citesti cuvantul, pui fiecare litera in stiva, iar in momentul cand construiesti cuvantul nou, scoti cate o litera pe rand din stiva.
  • Multe alte exemple (evaluarea unei expresii, etc)

Cum implementam stiva?

Inainte de a implementa stiva vom traduce denumirile functiilor in engleza (pentru a te familiariza cu libraria STL).

  • push(int numar) – adauga un element in stiva
  • pop() – sterge ultimul element din stiva
  • peek() – afiseaza ultimul element din stiva
  • isEmpty() – verifica daca stiva este goala

Nota: Uneori functia pop() vine „la pachet cu functia peek()”

Există două feluri prin care o putem implementa: fie printr-un array, fie printr-o lista simpla inlantuita. La clasa veti aborda prima metoda, pentru ca listele nu mai intra in programa de Bacalaureat (din cate stiu, poate s-a schimbat intre-timp).

Probabil va intrebati: „de ce trebuie sa implementam noi ceva ce este gata scris in STL?„. Raspunsul este foarte simplu: inveti mult mai bine principiile cu care functioneaza si te forteaza sa intelegi programarea mai bine.

Varianta 1 – Utilizarea unui array (multimi)

Aceasta varianta incalca una din principiile fundamentale ale stivei. Este restrictionata de un numar maxim de elemente. Stiva este o structura de date flexibila.

Varianta 2 – Utilizarea listelor simpu inlantuite

Probleme ce utilizeaza stivele

Pentru a va familiariza cu stivele, puteti sa rezolvati problemele

Comentarii
Se incarca comentariile...

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More