Scrigroup - Documente si articole

Username / Parola inexistente      

Home Documente Upload Resurse Alte limbi doc  

CATEGORII DOCUMENTE





AccessAdobe photoshopAlgoritmiAutocadBaze de dateCC sharp
CalculatoareCorel drawDot netExcelFox proFrontpageHardware
HtmlInternetJavaLinuxMatlabMs dosPascal
PhpPower pointRetele calculatoareSqlTutorialsWebdesignWindows
WordXml


Stiva - Utilitatea stivelor - Accesarea elementului de la varf

algoritmi

+ Font mai mare | - Font mai mic







DOCUMENTE SIMILARE

Trimite pe Messenger
Proiect ASDN - Algoritmul de minimizare Karnaugh
Constructia si simularea executiei unui program (in limbaj de asamblare)
Tehnici de programare structurata: Recursivitatea, Backtracking
Tipuri de limbaje de programare
Sistem informational – Sistem informatic
Stiva - Utilitatea stivelor - Accesarea elementului de la varf
Algoritmi semnatura digitala

Stiva

            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 capatm denumit varful stivei.



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

Operatii caracteristice

            Singurele operatii care pot fi executate cu o stiva sunt:

  • crearea unei stive vide;
  • inserarea unui element in stiva (operatie denumita in literatura de specialitate PUSH);
  • extragerea unui element din stiva (operatie denumita in termeni de specialitate POP);
  • accesarea elementului de la varf (operatie denumita TOP).

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. Pe scurt, 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 inversa a aparitiei lor. Operatia curenta este cea corespunzatoare varfului stivei, in stiva fiind retinute toate informatiile necesare programului pentru a executa operatiile respective.

Accesarea elementului de la varf

            Stiva este o structura de date abstracta, ce poate fi implementata in diferite moduri. De exemplu, putem implementa o stiva ca un vector in care retinem elementele stivei. Pentru ca acest vector sa functioneze ca o stiva, singurele operatii permise sunt operatiile caracteristice stivei.

            Pentru exemplificare, voi prezenta declaratiile necesare pentru implementarea unei stive cu elemente te tip int:

#define DimMax 100                           //numarul maxim de elemente din stiva

typedef int Stiva[DimMax];       //tipul de stiva implementat ca vector

Stiva S;                                                    //stiva

int vf;                                                   //varful stivei

Crearea unei stive vide

            Pentru a crea o stiva vida, initializam varful stivei cu -1 (varful stivei indica intotdeauna pozitia ultimului element introdus in stiva; elementele sunt memorate in vector incepand cu pozitia 0)




vf=-1;

Inserarea unui element in stiva

            Pentru a insera un element x in stiva S trebuie sa verificam in primul rand daca “este loc”, deci stiva nu este plina. Daca stiva este plina, inserarea nu se poate face, altfel vom mari varful stivei si vom plasa la varf noul element.

            De exemplu, daca dorim sa inseram elementul x=3 in stiva din figura urmatoare, obtinem:

                                                     

            Stiva S inainte de inserare                Stiva S dupa inserare

if (vf == DimMax-1)     //stiva este plina

     cout<<”Eroare – stiva este plina”;

       else

     S[++vf] = x;       //inseram elementul x in stiva s

Accesarea elementului de la varf

            Prin modul sau restrictiv de functionare, stiva permite numai accesarea elementului de la varf. Daca dorim sa aflam valoarea unui alt element al stivei, ar trebui sa “golim” stiva (deci sa extragem succesiv elemente) pana la elementul dorit.

            Accesarea elementului de la varf presupune determinarea valorii acestuia, valoare pe care o vom obtine intr-o variabila denumita x.

x = S[vf];

Observatii

  1. Dezavantajul implementarii unei stive ca vector alocat static consta in faptul ca indiferent de numarul de elemente existente in stiva, dimensiunea zonei de memorie alocata stivei este aceeasi (DimMax).
  2. Pentru a executa operatii cu stiva alocata static este suficient sa cunoastem varful stivei. Ca sa retinem mai usor modul de functionare al stivei, ne imaginam ca la inserare, varful stivei urca, iar la extragere, coboara.








Politica de confidentialitate

DISTRIBUIE DOCUMENTUL

Comentarii


Vizualizari: 885
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 2019 . All rights reserved

Distribuie URL

Adauga cod HTML in site