Universitatea Valahia din Trgovite Facultatea de Inginerie Electric Specializarea: Electrotehnic Anul I

PROIECTla Programarea Calculatoarelor i Limbaje de Programare II

Student: Crciun Radu Ioan

2010

Tema:

Structuri de date. Stiva i coada

2

Cuprins1. Stiva definitie ...................................................................................................4 2. Utilitatea stivelor ................................................................................................4 3. Implementarea unei stive ....................................................................................5 4. Coada definitie .................................................................................................7 5. Utilitatea unei cozi ..............................................................................................7 6. Implementarea unei cozi .....................................................................................8 Bibliografie ...........................................................................................................16

3

1. Stiva definitie

Stiva este o structura de date abstracta pentru care atat operatia de inserare a unui element cat si operatia de extragere a unui element se realizeaza de la un singur capat,denumit varful stivei. Elementele componente ale structurii de tip stiva sunt de acelasi tip, ceea ce inseamna ca stiva este o structura de date omogena. Singurul element din stiva la care avem acces direct este cel de la varf.

Operatii caracteristice : crearea unei stive vide inserarea unui element in stiva(operatie denumita si PUSH) extragerea unui element din stiva(operatie denumita si POP) accesarea elementului de la varf(operatie de numita si TOP) Ca sa ne imaginam mai bine functionarea unei stive,sa ne gandim cum lucram cu un teanc de carti foarte inalt.Cand dorim sa punem o carte in teanc,o punem deasupra,cand dorim sa luam o carte o luam tot pe cea de deasupra.Motivul este clar de inteles : daca am lua o carte de la mijloc am risca sa daramam tot teancul sau nu am putea ridica cartile de deasupra pentru ca ar fi prea grele. Din acest motiv,stiva este definita si ca o structura de date ce functioneaza dupa principiul LIFO ( last in first out).

2. Utilitatea stivelorStiva este necesara pentru memorarea unor informatii si regasirea acestora intr`o anumita ordine,descrisa de principiul LIFO.Stiva este folosita atunci cand programul trebuie sa amane executia unor operatii,pentru a le executa ulterior,in ordinea inversa a aparitiilor lor.Un bun exemplu de utilizare a stivelor il reprezinta evaluarea unor expresii matematice(prin aducerea unei expresii matematice la forma poloneza,spre exemplu).

4

3. Implementarea unei stiveStiva este o structura de date abstracta,ce poate fi implementata in diverse 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 admise sunt cele caracteristice stivei. Declaratiile necesare pentru implementarea unei stive de tip intreg. Code: #define MAX_N 200 // numarul maxim de element din stiva typedef int stiva[MAX_N]; 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,elementele fiind memorate de pe pozitia 0). Code: vf = -1; Inserarea unui element in stiva Pentru a insera un element in e in stiva S trebuie sa verificam in primul rand daca stiva nu este plina. Daca acest lucru este indeplinit memoram elementul,in caz contrar nu putem duce la indeplinirea sarcinii. Code: if(vf == MAX_N-1) //daca stiva este plina coutnext; delete t; return vf; } return vf;

6

4. Coada definitieCoada este o structura de date abstracta pentru care operatia de inserare a unui element se realizeaza de la un capat,in timp ce operatia de extragere a unui element se realizeaza de la celalalt.

Operatii caracteristice crearea unei cozi vide inserarea unui element in coada extragerea unui element din coada accesarea unui element Executarea acestor operatii asupra unei cozi necesita cunoasterea inceputului(inc) si a sfarsitului acesteia(sf).

Modul de functionare a unui cozi este foarte usor de intuit : cred ca toata lumea a stat la coada,macar o data.Orice situatie in care sunt mai multe cereri de acces la o resursa unica,necesita formarea unei "linii de asteptare".Cererile trebuie sa fie efectuate in ordinea sosirii. Datorita acestui lucru,putem spune ca o coada functioneaza dupa principiul FIFO(first in first out).

5. Utilitatea unei coziUtilitatea structurii de tip coada reiese din modul sau de functionare,este necesara utilizarea unei cozi atunci cand informatiile trebuie prelucrate exact in ordinea in care au fost retinute in coada. Un bun exemplu de folosire a unei cozi il reprezinta imprimanta,cand un utilizator face mai multe cereri de imprimare in acelasi timp,ele sunt memorate intr`o coada de tiparireQueue.Imprimanta le va tipari in ordinea in care vor aparea.

7

6. Implementarea unei cozi

Coada este o structura de date abstracta care poate fi implementata,ca si in cazul stivei,in diferite moduri.In exemplu de mai jos o vom implementa static,retinand elementele intr`un vector. Declaratiile necesare pentru implementarea unei cozi de tip intreg. Code: #define MAX_N 200 //numarul maxim de elemente din coada typedef int coada[MAX_N]; coada C; //coada int inc,sf; //inceputul si sfarsitul cozii Elementele cozii sunt memorate in vector de la pozitia inc pana la pozitia sf,deci numarul lor este : sf-inc+1. Crearea unei cozi vide Code: inc = 0; sf = -1; Inserarea unui element in coada Code: if(sf == MAX_N - 1) //numai avem spatiu cout