Declararea si utilizarea cozilor in ingineria programarii in C/C++

Declararea si utilizarea cozilor in ingineria programarii in C/C++

O stiva este o lista liniara particulara de date in care accesul la elementele listei se face numai pe la un capat, si anume pe la inceputul acesteia. Singurele operatii admise asupra elementelor unei cozi sunt adaugarea unui element in coada pe la sfarsitul acesteia si stergerea unui element, echivalenta cu extragerea acestuia, din coada pe la inceputul acesteia. Pentru a ne imagina o coada ne vom referi la un sir de oameni care asteapta sa execute operatii financiare la o banca, la un convoi de vagoane cisterna care asteapta sa fie incarcate cu petrol, la un sir de masini care asteapta sa se alimenteze cu benzina, etc. Coada de masini care asteapta sa se alimenteze cu benzina functioneaza dupa metoda “primul care intra la alimentare este primul care iese din coada” sau in cazul general “primul intrat, primul iesit din coada” iar in literatura de specialitate metoda este cunoscuta sub numele “First In, First Out=FIFO”. In prelucrarea elementelor unei cozi se cunosc doua operatii de baza: adaugarea sau memorarea si stergerea sau extragerea sau cu alte cuvinte, scrierea si citirea unui element din stiva pe la sfarsitul acesteia, numite in mod traditional push (a pune) si pop (a scoate). Pentru a implementa o stiva in Limbajul C este nevoie de alocarea unei zone de memorie pentru stocarea elementelor stivei, de o functie de adaugare (introducere sau scriere) a unui element in coada, numita traditional qstore() si de o functie de stergere (eliminare sau citire) a primului element din coada, returnand valoarea sa, numita traditional qretrive(). Pentru zona de memorie a cozii se poate folosi un tablou de tipul elementelor cozii sau se poate folosi o functie de alocare dinamica (malloc()). Operatia de citire a cozii nu face altceva decat sa extraga primul element din coada si sa-l distruga daca acesta nu este stocat in alta parte. In acest mod este posibil ca o coada sa devina vida, goala, deoarece toate elementele sale au fost extrase (citite) si eliminate prin inceputul cozii. Cozile sunt foarte des utilizate in foarte multe operatiuni de programare, cum ar fi simularile, planificarile unui sistemului de operare, incvlusiv pentru gestionarea zonelor de memorie tampon ale dispozitivelor de intrare/iesire (Buffering Input/Output).

Mai jos este dat un tabel care simuleaza introducerea si extragerea de date dintr-o coada

Functia	Continutul scozii
qstore(X)	X
qstore(Y)	X Y
qstore(Z)	X Y Z
qstore(W)	X Y Z W
qretrive() returneaza X	Y Z W
qstore(A)	Y Z W A
qretrive() returneaza Y	Z W A
qretrive() returneaza Z	W A
qretrive() returneaza W	A Lucrare: Descompuneri in factori Proiect: Media aritmetica si media aritmetica ponderata
qretrive() returneaza A	Coad goala, vida
Qstore(Q)	Q

Pentru a vedea un exemplu de functionare al unei cozi in actiune se va folosi un program simplu pentru planificarea intalnirilor. Acest program permite introducerea intr-o coada a unui numar de intalniri, apoi, pe masura ce intalnirile au avut loc, acestea sunt eliminate (sterse) din lista. Se va considera un numar maxim de intalniri egal cu 100. Functiile qstore() si qretrive() vor stoca pointeri catre sirurile care descriu intalnirile.

#define MAX 100 /* declararea numarului maxim de intalniri */

declararea tabloului de pointeri catre sirurile ce descriu intalnirile planificate */

char *ptrintalniri[MAX];

int freepos = 0; /* memoreaza pozitia urmatoarei locatii libere de memorie */

int recupos = 0; /* memoreaza pozitia urmatorului articol care va fi citit, recuperat */

/* functia de memorare (adaugare) a unei intalniri in coada */

void qstore(char *q) /* q este pointer catre descrierea unei intalniri */

ptrintalniri[freepos] = q; /* q memoreaza adresa textului unei intalniri */

freepos++; /* incrementarea urmatoarei pozitii a locatiei libere de memorie */

}

/* functia de eliminare (recuperare) a unei intalniri in coada */

void *qretrive()

ptrintalniri[freepos] = q; /* q memoreaza adresa textului unei intalniri */

recupos++; /* incrementarea urmatoarei intaniri de recuperat */

return ptrintalniri[recupos-1]; /*returneaza urmatoarea intalnire de recuperat */

}

Functiile qstore() si qretrive() necesita doua variabile globale: freepos, care memoreaza pozitia urmatoarei locatii libere de memorie, si recupos, care memoreaza pozitia urmatorului text al intanirii care va fi recuperat. Functiile de mai sus pot fi utilizate pentru a gestiona orice coada de elemente de diverse tipuri de date prin simpla modificare a tipului de baza al tabloului cu care opereaza aceste functii. Functia qstore() amplaseaza pointerii urmatoarelor intalniri la sfarsitul cozii si verifica daca lista este plina iar functia qretrive() preia intalnirile din capul cozii pe parcursul desfasurarii unor evenimente. La fiecare noua intalnire programata variabila freepos este incrementata iar la fiecare intalnire desfasurata variabila recupos este incrementata. De fapt, recupos este mereu pe urmele lui freepos pe tot parcursul cozii. Cand freepos si recupos sunt egale se concluzioneaza ca nu mai sunt intalniri de programat.

Exemplul 3

Se considera o coada de masini, la o statie de alimentare cu benzina, cu caracteristicile: numarul de inmatriculare un camp alfanumeric de 10 caractere, tipul masinii un camp alfanumeric de 15 caractere, culoarea un camp alfanumeric de 10 caractere. Sa se simuleze activitatile de alimentare cu benzina ale masinilor din coada: adaugarea unei masini la coada, eliminarea din capul cozii a masinii alimentate si listarea tuturor masinilor din coada folosindu-se cate o functie adecvat definite.

Evenimentele care pot avea loc cu aceasta coada sunt: adaugarea unei noi masini la coada, simulata prin apasarea tastei a, eliminarea din coada a masinii alimentate simulata prin apasarea tastei e si listarea masinilor din coada simulata prin apasarea tastei l. Pentru o masina sosita la coada se vor cere:numarul de inmatriculare, tipul, culoarea si capacitatea rezervorului iar la plecarea masinii dupa ce a fost alimentata se vor afisa aceleasi informatii. Listarea masinilor din coada presupune afisarea acelorasi informatii pentru toate masinile care sunt la coada si urmeaza sa se alimenteze cu benzina. Coada masinilor se va implementa ca un tablou de pointeri spre articole de tip structura care se initializeaza cu valoarea NULL. Toate operatiile asupr unei cozi se fac pe la ambele capate ale listei si constau fie din adaugarea unei structuri de tip masina la sfarsitul cozii fie din extragerea (stergera) unei structuri de tip masina la inceputul cozii. Functia qstore() va simula asezarea unei noi masini la coada si verifica daca lista este completa. Functia qretrieve() simuleaza eliberarea unei masini din coada si va returna NULL daca nu mai sunt masini in coada si va returna pozitia urmatoarei masini care va fi eliberata, permitand in acest mod afisarea informatiilor despre masina care va fi eliberata.

#include<stdio.h>

#include<string.h>

#include<alloc.h>

#include<conio.h>

#include<process.h>

#define MAX 20

struct tipmasina

;

struct tipmasina *ptrmasina[MAX],*qretrive(void);

int freepos=0;

int recupos=0;

/* descrierea functiei de adaugare masina la coada, adaugare() */

void qstore(struct tipmasina *q)

ptrmasina[freepos]=q;

freepos++;

}

/* descrierea functiei de extragere masina din coada */

struct tipmasina *qretrieve(void)

recupos++;

return ptrmasina[recupos-1];

}

void adaugare()

printf('n numarul de inmatriculare al masinii:');

scanf('%s',&ptrmasina->numar);

printf('n tipul masinii:');

scanf('%s',&ptrmasina->tip);

printf('n culoarea masinii:');

scanf('%s',&ptrmasina->culoare);

printf('n capacitatea rezervorului:');

scanf('%d',&ptrmasina->capacitate);

qstore(ptrmasina);

}

while ((r!='d')&&(r!='D'));

}

/* descrierea functiei de extragere (stergere) din stiva */

void stergere()

void listare()

/* descrierea functiei de stocare a unei masini */

void main(void)

}

}