Structuri de tip stiv, coad.

Structuri de tip stiv.Structura de tip stivAceast structur de date este un caz particular de list care funcioneaz pe principiul LIFO (last in first out, ultimul intrat este primul ieit). Prin urmare principalele prelucrri care se refer la aceast structur de date vor fi:creare stivalistare stiva (parcurgere n ordine invers crerii)adugare la sfrit (peste vrful stivei, operaie numitpush ( ))tergere element din vrful stivei (operaie numitpop( ))prelucrarea vrfului stivei

Ca s ne imaginm mai bine funcionarea unei stive, s ne gndim cum lucrm cu un teanc de farfurii. Cnd dorim s punem o farfurie n teanc, o punem deasupra, cnd dorim s lum o farfurie din teanc, o lum tot pe cea de deasupra. Motivul este lesne de neles: nu ne-am propus s spargem farfuriile! Acest mod de funcionare face ca ultimul element inserat n stiv s fie primul extras. Din acest motiv, stiva este definit i ca o structur de date care funcioneaz dup principiul LIFO (Last In First Out Ultimul Intrat Primul Ieit).Care este utilitatea stivelor?n informatic stiva joac un rol fundamental. Pentru a nelege mecanisme fundamentale ale programrii (de exemplu, funciile sau recursivitatea) este necesar cunoaterea noiunii de stiv. Pe scurt, stiva este util n situaii n care este necesar memorarea unor informaii i regsirea acestora ntr-o anumit ordine, descris de principiul LIFO. Stiva este utilizat atunci cnd programul trebuie s amne execuia unor operaii, pentru a le executa ulterior, n ordinea invers a apariiei lor. Operaia curent este cea corespunztoare vrfului stivei, n stiv fiind reinute toate informaiile necesare programului pentru a executa operaiile respective. Cum implementm o stiv? Stiva este o structur de date abstract, ce poate fi implementat n diferite moduri. De exemplu, putem implementa o stiv ca un vector n care reinem elementele stivei. Pentru ca acest vector s funcioneze ca o stiv, singurele operaii permise sunt operaiile caracteristice stivei. Pentru exemplificare, s prezentm declaraiile necesare pentru implementarea unei stive cu elemente de tip int: #define DimMax 100 //numarul maxim de elemente din stiva typedef int Stiva[DimMax]; //tipul Stiva implementat ca vector Stiva S; //stiva int vf; //varful stivei

Crearea unei stive videPentru a crea o stiv vid iniializm vrful stivei cu -1 (vrful stivei indic ntotdeauna poziia ultimului element introdus n stiv; elementele sunt memorate n vector ncepnd cu poziia 0): vf=-1;

Inserarea unui element n stiv Pentru a insera un element x n stiva S trebuie s verificm n primul rnd dac avem loc, deci dac stiva nu este plin. Dac stiva este plin, inserarea nu se poate face, altfel vom mri vrful stivei i vom plasa la vrf noul element. De exemplu, dac dorim s inserm elementul x = 3 n stiva din figura urmtoare, obinem:

Stiva S nainte de inserare Stiva S dup inserare if (vf == DimMax-1) //stiva este plina coutback=0; } else{ c=new nod; c->back=v; c->info=x; v=c; }}//Eliminare din stivavoid pop(nod* &v){ nod* c; if(!v) cout