Declararea si utilizarea stivelor in ingineria programarii in C/C++

Declararea si utilizarea stivelor in ingineria programarii in C/C++

O stiva este o lista particulara in care accesul la elementele listei se face numai pe la un capat, si anume pe la sfarsitul acesteia. Singurele operatii admise asupra elementelor unei stive sunt adaugarea unui element in stiva pe la sfarsitul acesteia si stergerea unui element, echivalenta cu extragerea acestuia, din stiva pe la sfarsitul acesteia. Pentru a ne imagina o stiva ne vom referi la un vraf de farfurii aflate pe o masa. Prima farfurie din vraf va fi ultima folosita, iar prima farfurie folosita va fi ultima asezata in vraf. Un alt exemplu de stiva o constituie vagoanele aflate pe o linie moarta (blocata la un capat), in triaj. Ultimul vagon trimis in triaj va fi si primul vagon care va putea fi scos din triaj pentru folosire. Adaugarea sau scoaterea unui vagon in sau din triaj se va face pe la un singur capat si anume pe la sfarsit. Generalizand, o stiva este o lista de elemente cu acces pe la un capat (sfarsit), care foloseste metoda de acces cunoscuta sub numele “ultimul adaugat primul extras (sau sters)” sau “ultimul intrat primul iesit (sau scos)” iar in literatura de specialitate este cunoscuta sub denumirea de “Last In, First Out=LIFO”. In prelucrarea elementelor unei stive se cunosc doua operatii de baza: adaugarea sau memorarea  si stergerea sau extragerea sau cu alte cuvinte, scrierea si citirea unui element din stiva pe la sfarsitul acesteia, numite in mod traditional push (a pune) si pop (a scoate). Pentru a implementa o stiva in Limbajul C este nevoie de alocarea unei zone de memorie pentru stocarea elementelor stivei, de o functie de adaugare (introducere sau scriere) a unui element in stiva, numita traditional push() si de o functie de stergere (extragere sau citire) a unui element din stiva numita traditional pop(). Pentru zona de memorie a stivei se poate folosi un tablou de tipul elementelor stivei sau se poate folosi o functie de alocare dinamica (malloc()). Operatia de citire a stivei nu face altceva decat extrage un element din varful stivei si-l distruge (sterge), daca nu este stocat in alta parte. Stivele sunt foarte des utilizate in programele sistemului de operare, incvlusiv in programele traducatoare si in compilatoare.

Mai jos este dat un tabel care simuleaza introducerea si extragerea de numere intr-o stiva

Functia	Continutul stivei
Push(X)	X
Push(Y)	Y X
Push(Z)	Z Y X
Push(W)	W Z Y X
pop() citeste W	Z Y X Lucrare: Descompuneri in factori Proiect: Media aritmetica si media aritmetica ponderata
Push(A)	A Z Y X
pop() citeste A	Z Y X
pop() citeste Z	Y X
pop() citeste Y	X
pop() citeste X	stiva goala, vida
Push(Q)	Q

Exemplul 2:

Se considera o stiva de containere cu caracteristicile:cod container un numar cuprins intre 1 si 99, continut un camp alfanumeri de 20 caractere, data ambalarii (zi, luna si an) si greutatea in kg. Sa se simuleze activitatile de stivuire si de incarcare intr-un mijloc de transport a containerelor din stiva.

Evenimentele care pot avea loc cu aceasta stiva de containere sunt: sosirea unuinou container pentru stivuire simulata prin apasarea tastei S si incarcarea intr-un mijloc de transport a unui container simulata prin apasarea tastei I. Pentru un container sosit pentru stivuire se vor cere:codul, continutul, data ambalarii si greutatea iar la incarcarea sa intr-un mijloc de transport pentru plecare se afisaza aceleasi informatii. Stiva containerelor se va implementa ca o lista simplu inlantuita, identificata prin variabila varf care arata containerul vizibil din varful stivei, adica primul element din lista de containere (ultimul asezat in stiva). Intrucat toate operatiile asupra unei stive se fac pe la capatul de inceput al listei, nu este necesara memorarea adresei ultimului element din lista (care a fost asezat primul in stiva). Functia push() va simula asezarea unui nou container in stiva si va returna valoarea 0 in cazul in care nu s-a reusit alocarea dinamica a spatiului de memorie necesar pentru introducerea unui nou element (informatiile containerului) in stiva de containere si valoarea 1 in caz contrar. Functia pop() va oferi informatii, prin intermediul parametrilor sai, despre containerul scos din stiva pentru expediere si va returna valoarea 1 daca in stiva nu mai sunt containere si valoarea 0 in caz contrar.

#include<stdio.h>

#include<string.h>

#include<alloc.h>

#include<conio.h>

struct tipdata

;

struct tipstiva

;

struct tipstiva *varf;

/* descrierea functiei push() */

int push(int *wcc,char *wcontinut,struct tipdata *wdata,int *wgreutate)

ptrcontainer->cc=*wcc;

strcpy(ptrcontainer->continut,wcontinut);

ptrcontainer->data.zi=wdata->zi;

ptrcontainer->data.luna=wdata->luna;

ptrcontainer->data.an=wdata->an;

ptrcontainer->greutate=*wgreutate;

ptrcontainer->urm=varf;

varf=ptrcontainer;

return 1;

}

/* descrierea functiei de extragere din stiva */

int pop(int *ptrcc,char *ptrcontinut,struct tipdata *ptrdata,int *ptrgreutate)

void main(void)

printf('n Apasati o tasta pentru continuare:');

getch();

}

}