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.
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)
#include <iostream>
using namespace std;
const int LIM = 100;
bool isEmpty(int k) {
if(k == 0)
return true;
return false;
}
void push(int stiva[], int &k, int numar) {
k = k + 1;
stiva[k] = numar;
}
int peek(int stiva[], int k) {
return stiva[k];
}
int pop(int stiva[], int &k) {
int rezultat = peek(stiva, k);
k = k - 1;
return rezultat;
}
int size(int k) {
return k;
}
int main() {
int stiva[LIM], k = 0;
push(stiva, k, 2);
push(stiva, k, 4);
push(stiva, k, 6);
push(stiva, k, 7);
push(stiva, k, 8);
cout << pop(stiva, k);
cout << pop(stiva, k);
cout << pop(stiva, k);
return 0;
}
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
#include <iostream>
using namespace std;
struct Nod {
int data;
Nod* next;
};
Nod* newNode(int data) {
Nod* nodNou = new Nod();
nodNou -> data = data;
nodNou -> next = NULL;
return nodNou;
}
bool isEmpty(Nod* top) {
return top == NULL;
}
void push(Nod* &top, int data) {
Nod* nodNou = newNode(data);
nodNou -> next = top;
top = nodNou;
}
int pop(Nod* &top) {
if(isEmpty(top))
return 0;
Nod* tmp = top;
top = top -> next;
int rezultat = tmp -> data;
delete tmp;
return rezultat;
}
int peek(Nod* top) {
if(isEmpty(top))
return 0;
return top -> data;
}
int main() {
Nod* top = NULL;
push(top, 2);
push(top, 4);
push(top, 6);
push(top, 7);
push(top, 8);
cout << pop(top);
cout << pop(top);
cout << pop(top);
return 0;
}
Probleme ce utilizeaza stivele
Pentru a va familiariza cu stivele, puteti sa rezolvati problemele
