COZI
Coada este o structură de date abstractă, pentru care operaţia de inserare a unui element se realizează la un capăt, în timp ce operaţia de extragere a unui element se realizează la celălalt capăt. Singurul element din coadă la care avem acces direct este cel de la început.
Operaţii caracteristice
Singurele operaţii ce pot fi executate cu o coadă sunt:
- crearea unei cozi vide;
- inserarea unui element în coadă;
- extragerea unui element din coadă;
- accesarea unui element.
Executarea acestor operaţii asupra unei cozi presupune cunoaşterea începutului cozii (să-l notăm Inc) şi a sfârşitului acesteia (să-l notăm Sf).
Modul de funcţionare a unei cozi este foarte uşor de intuit: toată lumea a „stat la coadă”, măcar o dată. Orice situaţie în care sunt mai multe cereri de acces la o resursă unică (de exemplu, mai mulţi clienţi şi o singură vânzătoare; o singură pompă de benzină şi mai multe maşini, un singur pod şi mai multe capre, etc) necesită formarea unei „linii de aşteptare”. Dacă nu apar alte priorităţi, cererile sunt satisfăcute în ordinea sosirii.
Datorită faptului că întotdeauna este extras („servit”) primul element din coadă, iar inserarea oricărui nou element se face la sfârşit („la coadă”), coada este definită ca o structură de date care funcţionează după principiul FIFO (First In First Out – Primul Intrat Primul Ieşit).
Care este utilitatea unei cozi?
Utilitatea structurii de tip coadă reiese din modul său de funcţionare – este necesară utilizarea unei cozi atunci când informaţiile trebuie prelucrate exact în ordinea în care „au sosit” şi ele sunt reţinute în coadă până când pot fi prelucrate. În informatică, cozile sunt utilizate frecvent. De exemplu, să considerăm că avem o reţea de calculatoare şi o singură imprimantă. Când utilizatorii reţelei vor da comenzi de tipărire, imprimanta nu poate răspunde tuturor comenzilor în acelaşi timp (imaginaţi-vă ce-ar ieşi!). Prin urmare comenzile de tipărire primite sunt înregistrate într-o coadă (Print Queue – Coadă de Tipărire). Imprimanta va tipări documentele pe rând, în ordinea în care au fost înregistrate în coadă. Un alt exemplu: pentru a mări viteza de execuţie, microprocesoarele Intel utilizează o coadă de instrucţiuni în care sunt memorate instrucţiunile care urmează a fi executate.
Cum implementăm o coadă?
Coada este o structură de date abstractă, care poate fi implementată în diferite moduri. Ca şi în cazul stivei, coada poate fi implementată static, reţinând elementele sale într-un vector.
Să considerăm următoarele declaraţii care reprezintă o coadă cu elemente de tip int alocată static:
#define DimMax 100 // numarul maxim de elemente din coada
typedef int Coada[DimMax]; // tipul Coada implementat ca vector
Coada C; //coada
int Inc, Sf; //inceputul si sfarsitul cozii
Elementele cozii sunt memorate în vector de la poziţia Inc până la poziţia Sf, deci numărul lor este Sf – Inc + 1.
Crearea unei cozi vide
Pentru a crea o coadă vidă, trebuie să iniţializăm variabilele Inc şi Sf astfel:
Inc = 0;
Sf = -1;
Observaţi că numărul de elemente din coadă este 0, iar poziţia pe care va fi plasat primul element din coadă este 0.
Inserarea unui element în coadă
Pentru a insera un element x în coada C trebuie să verificăm în primul rând dacă „avem loc”, deci dacă variabila Sf nu depăşeşte dimensiunea maximă a vectorului. Dacă inserarea se poate face, vom mări valoarea variabilei Sf cu o unitate (coada „creşte”) şi vom plasa la sfârşit noul element.
De exemplu, să inserăm elementul x = 3 în coada din figura următoare:
if (Sf = = DimMax - 1) //nu mai avem loc in coada
cout << “Eroare” << endl;
else //inseram elementul x in coada C
C[++Sf] = x;
Extragerea unui element din coadă
Pentru a extrage un element dintr-o coadă C, trebuie să verificăm în primul rând dacă numărul de elemente din coadă este diferit de 0 (coada nu este vidă). Dacă da, reţinem elementul de la începutul cozii într-o variabilă (să o notăm x), după care mărim cu o unitate începutul cozii.
De exemplu, să extragem un element din coada din figura următoare:
if (Inc > Sf) //coada este vidă
cout << “Eroare” << endl;
else //extragem primul element
x = C[Inc++];
Accesarea unui element
Singurul element al unei cozi care poate fi accesat direct este primul. Dacă dorim să aflăm valoarea unui alt element, va trebui să extragem succesiv elemente până la cel dorit.
Accesarea primului element are ca scop determinarea valorii acestuia, valoare pe care o vom reţine într-o variabilă denumită x.
x = C[Inc];
Observaţie
În acest mod de alocare statică a unei cozi observaţi că, pe măsură ce inserăm şi extragem elemente, atât sfârşitul, cât şi începutul cozii „migrează” către limita maximă a vectorului. Dezavantajul este că în vector rămân poziţii neutilizate (de la 0 până la Inc-1).
De exemplu, ar putea să apară o situaţie în care coada conţine un element, dar operaţia de inserare să nu fie posibilă, pentru că Inc = Sf = DimMax - 1.
O soluţie mai bună ar fi de a reutiliza circular spaţiul de memorie alocat cozii. Pentru aceasta, următoarea poziţie, după poziţia i, poate fi:
i+1, dacă i < DimMax - 1
0, dacă i = DimMax - 1
EXEMPLU DE APLICATIE PENTRU EXPLOATAREA COZILOR