Implementarea Stivei.docx

Algoritmi de implementare a stivelor ( prin vector sau listă simplă înlănțuită)

Autor: Matei Alexandru-Petruț Grupa: 313AC Prezentarea algoritmilor O stivă este o instanță a unui tip de date abstract ce formalizează conceptul de colecţie cu acces restricționat. Restricția respectă regula LIFO (Last In, First Out). Accesul la elementele stivei se face doar prin vârful acesteia. Operații care se pot aplica unei stive: push – adaugă un element (entitate) în stivă. Adăugarea se poate face doar la vârful stivei.  pop – șterge un element din stivă și îl returnează. Ștergerea se poate face doar la vârful stivei.  peek – consultă (întoarce) elementul din vârful stivei fără a efectua nicio modificare 

asupra acesteia.  isEmpty – întoarce 1 dacă stiva este goală; 0 dacă are cel puțin un element O structură de date definește un set de operații și funcționalitatea acestora. Implementarea efectivă a unei structuri de date poate fi realizată în diverse moduri, cât timp funcționalitatea este păstrată. O stivă poate fi implementată cu ajutorul unui vector sau cu liste înlănțuite. Reprezentare internă cu vector La nivel de implementare, stiva este reprezentată printr-o clasă ce folosește (pe lângă operațile ce pot fi efectuate asupra ei) un vector de stocare (stackArray) de o dimensiune maximă dată (NMAX) și un indice ce indică vârful stivei(topLevel). Reprezentare internă cu listă simplă înlănțuită Fiecare nod este format din informaţiile utile şi o legătură către elementul următor. Tipul informaţiilor stocate în stivă este indicat de utilizator prin definirea tipului TipStiva. Stiva vidă este reprezentată printr-un pointer nul. Elementele sunt adăugate înaintea primului element (cu deplasarea vârfului stivei). Extragerea se face tot din vârful stivei. Concluzii

Stivele şi cozile pot fi implementate în mai multe moduri. Cele mai utilizate implementări sunt cele folosind vectori şi liste. Se întocmește următorul tabel cu avantajele și dezavantajele implementării stivelor cu ajutorul vectorilor sau a listelor simple înlănțuite:

AVANTAJE

Vector

-

Listă simplă înlănțuită

DEZAVANTAJE

implementare simplă consum redus de memorie viteză mare pentru operații

-

număr oarecare elemente

-

de

-

numărul de elemente este limitat risipă de memorie în cazul în care dimensiunea alocată este mult mai mare decât numărul efectiv de elemente consum mare de memorie pentru memorarea legăturilor