Stive

Aspecte teoretice:

Stiva este o structură de date abstractă pentru care atât operația de inserare a unui element în structură, cât și operația de extragere a unui element se realizează la un singur capăt, denumit vârful stivei. Singurul element din stivă la care avem acces direct este cel de la vârf.

Operații caracteristice:

Singurele operații ce pot fi executate cu o stivă sunt:

• crearea unei stive vide;
• inserarea unui element în stivă (operație denumită în literatura de specialitate PUSH)
• extragerea unui element din stivă (operație denumită în termeni de specialitate POP)
• accesarea elementului de la vârf  (operație denumită TOP).

Ca să ne imaginăm mai bine funcționarea unei stive, să ne gândim cum lucrăm cu un teanc de farfurii. Când dorim să punem o farfurie în teanc, o punem deasupra, când dorim să luăm o farfurie din teanc, o luăm tot pe cea de deasupra. Motivul este lesne de înțeles: nu ne-am propus să spargem farfuriile!  Acest mod de funcționare face ca ultimul element inserat în stivă să fie primul extras. Din acest motiv, stiva este definită și ca o structură de date care funcționează după  principiul LIFO (Last In First Out – Ultimul Intrat Primul Ieșit).

Implementare C++ operații cu stive:

// StivaCPP.cpp : Defines the entry point for the console application.
//
 
#include "stdafx.h"
#include<iostream>
#include<conio.h>
 
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;
	}
 }
 
void main()
{
	int n,a,i;
	cout<<"numarul initial de noduri ";
	cin>>n;
	for(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(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(i=1;i<=nre;i++)
	   pop(varf);
	cout<<endl<<"dupa eliminare"<<endl;
	n=n-nre;
	cout<<"stiva are  "<<n<<" elemente"<<endl;
	afisare(varf);
	//prelucrez varful stivei: de exemplu se poate dubla continutul:
	varf->info=2*varf->info;
	cout<<endl<<"dupa dublarea valorii varfului "<<endl;
	afisare(varf);
	system("pause");
 }