Structurile de date Stiva si Coada in C++

2 comments - This post in english

Stiva este o structura de date logica, implementarea sa din punct de vedere fizic fiind realizata prin utilizarea altor structuri de date.
Elementele componente ale structurii de tip stiva sunt de acelasi tip, ceea ce inseamna ca stiva este o structura de date omogena.
Exista doua operatii de baza cu structura de tip stiva: adaugarea si extragerea unui element. Modalitatea de implementare a operatiilor este data de disciplina de acces: LIFO – Last In First Out. Toate inserarile (push) si extragerile (pop) sunt realizate la acelasi capat al structurii de implementare, denumit varful stivei.

In exemplul de mai jos, sunt prezentate implementari ale operatiilor push si pop, utilizand ca structura de implementare lista simpla [...]. Structura elementelor stivei este formata dintr-o valoare de tip int si adresa urmatorului element din structura.

struct Nod{
	int val;
	Nod* next;
};
 
Nod* push(Nod* vf, int v){
	Nod* nou=new Nod;
	nou->val=v;
	nou->next=vf;
	return nou;
}
 
Nod* pop(Nod* vf, int *v){
	if(vf){
		*v=vf->val;
		Nod* t=vf;
		vf=vf->next;
		delete t;
		return vf;
	}
	return vf;
}

Coada pastreaza caracteristicile structurii de tip stiva, mai putin aspectele de implementare a operatiilor de inserare si extragere. Astfel, modalitatea de implementare a operatiilor este data de disciplina de acces: FIFO – First In First Out. Toate inserarile (put) sunt efectuate la un capat al structurii de implementare fizica, iar extragerile din coada (get) sunt realizate la celalalt capat al structurii.
In exemplul de mai jos sunt prezentate implementari ale operatiilor put si get, utilizand ca structura suport lista simpla [...]. Structura unui element al cozii este formata dintr-o valoare de tip int si adresa nodului succesor din structura de tip coada.

struct Nod{
	int val;
	Nod* next;
};
 
Nod* put(Nod* c,int v){
	Nod* nou=new Nod;
	nou->val=v;
	nou->next=NULL;
	if(!c)
		return nou;
	else{
		Nod* t=c;
		while(t->next)
			t=t->next;
		t->next=nou;
		return c;
	}
}
 
Nod* get(Nod* c,int *v){
	if(c){
		*v=c->val;
		Nod* t=c;
		c=c->next;
		delete t;
		return c;
	}
	return c;
}

, , , ,