Scrigroup - Documente si articole

Username / Parola inexistente      

Home Documente Upload Resurse Alte limbi doc  
AccessAdobe photoshopAlgoritmiAutocadBaze de dateCC sharp
CalculatoareCorel drawDot netExcelFox proFrontpageHardware
HtmlInternetJavaLinuxMatlabMs dosPascal
PhpPower pointRetele calculatoareSqlTutorialsWebdesignWindows
WordXml


Stiva

c



+ Font mai mare | - Font mai mic



Stiva

Aspecte teoretice



O stiva (stack) este o lista liniara cu proprietatea ca operatiile de inserare / extragere a nodurilor se fac in/din coada listei. Daca nodurile A, B, C, D sunt inserate intr-o stiva in aceasta ordine, atunci primul nod care poate fi extras este D.

Stiva este o structura de date abstracta pentru care atat operatia de inserare a unui element in structura, cat si operatia de extragere a unui element se realizeaza la un singur capat, denumit varful stivei.

Singurul element din stiva la care avem acces direct este cel de la varf.

Operatii caracteristice (singurele care pot fi executate)

crearea unei stive vide;

inserarea unui element in stiva (PUSH[1]);

extragerea unui element din stiva (POP[2]);

accesarea elementului de la varf (TOP[3]).

Acest mod de functionare face ca ultimul element inserat in stiva sa fie primul extras, motiv pentru care stiva este definita si ca o structura de date care functioneaza dupa principiul LIFO (ultimul intrat primul iesit)

Utilitatea stivelor

In informatica, stiva joaca un rol fundamental. Pentru a intelege mecanismele fundamentale ale programarii (de exemplu, functiile sau recursivitatea) este necesara cunoasterea notiunii de stiva. Stiva este utila in situatii in care este necesara memorarea unor informatii si regasirea acestora intr-o anumita ordine, descrisa de principiul LIFO. Stiva este utilizata atunci cand programul trebuie sa amane executia unor operatii, pentru a le executa ulterior, in ordinea inverse a aparitiei lor. Operatia curenta este cea corespunzatoare varfului stivei, in stiva fiind retinute toate informatiile necesare programului pentru a executa operatiile respective



Implementarea unei stive

Stiva este o strucutra de date abstracta, ce poate fi implementata in diferite moduri. De exemplu, cu un vector in care retinem elementele stivei. Pentru ca acest vector sa functioneze ca o stiva, singurele operatii premise sunt operatii caracteristice stivei. Cele mai avantajoase implementari ale structurii de date stiva sunt cele cu ajutorul tipului pointer si al tipului tablou

Asupra tipului abstract de date stiva sunt definiti urmatorii cinci operatori:

1.INITIALIZARE(S) - face stiva S vida ( initializeaza lista corespunzatoare )

2.VIRFST(S) - furnizeaza elementul din varful stivei ( deci primul nod al listei )

3.POP(S) - suprima elementul din varful stivei

4.PUSH(x,S) - insereaza elementul x in varful stivei pe care il actualizeaza

5.STIVID(S) - functie booleana ce e adevarata daca stiva este vida.

Pentru exemplificare, sa prezentam declaratiile 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

troduse.



PUSH ("a impinge") = termenul din literatura de specialitate care desemneaza operatia de inserare a unui element in stiva; conform acestui termen ne imaginam stiva ca pe un sac iar PUSH ar insemna ca impingem inauntru un element, prin capatul superior(nu prin mijloc sau )

POP ("a scoate cu zgomot") = operatia prin care primul element, cel de deasupra, "sare" din sac (din structura)

TOP = varf





Politica de confidentialitate | Termeni si conditii de utilizare



DISTRIBUIE DOCUMENTUL

Comentarii


Vizualizari: 998
Importanta: rank

Comenteaza documentul:

Te rugam sa te autentifici sau sa iti faci cont pentru a putea comenta

Creaza cont nou

Termeni si conditii de utilizare | Contact
© SCRIGROUP 2024 . All rights reserved