Stiva in Cpp

 Stiva (engleza stack) este o structura de date abstractă pentru care atat operația de inserare a unui element in structura, cat si operatia de extragere a unui element se realizeaza la un singur capat, denumit vârful stivei.

 

Stiva este o structura care suportă urmatoarele operatii:

  • push(ob): adauga un obiect in varful stivei.
  • pop(): elimina obiectul din varful stivei.
  • top(): returneaza o referinta catre varful stivei fara a elimina obiectul.
  • size(): returneaza numarul obiectelor din stiva.
  • isEmpty(): returneaza true daca stiva este vida, altfel false.

 

In informatica,  stiva joaca un rol important. Pentru a intelege mecanismele fundamentale ale programarii (de exemplu, functiile si recursivitatea) este necesara cunoasterea notiunii de stiva.

 

#include <iostream>

using namespace std;

struct nod{

int info;

nod *back;

};

nod *varf;

void push(nod* &v, int x){

nod *c;

if(!v){

v = new nod;

v->info = x;

v->back=0;

} else {

c = new nod;

c->back = v;

c->info = x;

v=c;

}

}

void afisare(nod* v){

nod *c;

c=v;

while(c) {

cout<< c->info <<” „;

c=c->back;

}

}

void pop(nod* &v){

nod* c;

if(!v) cout<<„Stiva este vida si nu mai ai ce elimina!!!”;

else {

c=v;

v=v->back;

delete c;

}

}

int main()

{

cout << „Hello world!” << endl;

int n, a;

cout<<„Numarul initial de noduri: „;

cin >> n;

for(int i=1; i<=n; i++){

cout<<„Valoarea de adaugat in stiva: „;

cin >> a;

push(varf, a);

}

cout<< endl;

afisare(varf);

int nre, nra;

cout<<endl<<„cate adaugari?” ;

cin >> nra;

for(int i=1; i<=nra; i++){

cout << „valoarea de adaugat „;

cin >> a;

push(varf, a);

}

cout << endl <<” dupa adaugare” << endl;

n = n+nra;

cout <<„stiva are „<<n<<” elemente”<<endl;

afisare(varf);

cout<<endl<<” cate eliminari?”;

cin >>nre;

for( int i=1; i<=nre; i++){

pop(varf);

}

cout << endl << ” dupa eliminare” <<endl;

afisare(varf);

varf->info = 2*varf->info;

cout<<endl<<” dupa dublarea valorii varfului ” <<endl;

afisare(varf);

return 0;

}

 

O stiva poate fi implementata in diferite moduri. Aceasta se poate imlementa si ca un vector in care retinem elementele stivei. In urmatoarele randuri implementam o stiva cu elemente de tip int.

 

#define DimMax 100

typedef int Stiva{DimMax];

Stiva s;

int vf;

Pentru a crea o stiva vida initializam varful stivei cu -1( varful stivei indica intotdeauna pozitia ultimului element introdus in stiva; elementele sunt memorate in vector incepand cu pozitia 0):

vf = -1;

 

Pentru a insera un element  x in stiva S trebuie sa verificam in primul rand daca exista loc, deci daca stiva nu este plina. Daca stiva este plina, inserarea nu se poate face, astfel vom mari varful stivei si vom plasa la varf noul element.

if(vf == DimMax-1) // stiva este plina

cout<<„Eroare – stiva este plina \n”;

else

S[++vf] = x;

Extragerea unui element din stiva S necesită verificarea existenței elementelor in stiva (deci daca stiva nu este vidă). Daca da, retinem elementul de la varful stivei intr-o variabila (să o notam x), dupa care micșoram cu o unitate varful stivei.

if(vf<0)

cout<<„Eroare – stiva este vida\n”;

else

x=S[vf–];

Stiva permite numai accesarea elementului de la varf. Dacă dorim sa aflam valoarea unui alt element al stivei, ar trebui sa golim stiva (extragem succesiv elementele) până la elementul dorit. Accesarea elementului de la varf presupune determinarea valorii acestuia, valoare pe care noi o vom retine intr-o variabila x.

x = S[vf];

 

Trebuie sa stiți ca Standard Template Library (STL) implementează o structură de tip stivă in clasa Stack, ce se găsește in headerul stack. Aceasta suportă urmatoarele operații:

  • constructor

explicit stack ( const container_type& ctnr = container_type());

 

  • empty
  • size
  • top
  • push
  • emplace
  • pop
  • swap

Acest document este disponibil la: //docs.google.com/document/d/1YBTqbV9j7y0mVwVuBh4f3jREbyhJ6M-nWuiUWEz1_V0/edit

Lasă un răspuns

Adresa ta de email nu va fi publicată. Câmpurile obligatorii sunt marcate cu *