Coada - Care este utilitatea unei cozi?

Coada

Coada e tot un tip special de lista in care elementele sunt inserate la un capat ( spate ) si sunt suprimate la celalalt ( fata ); se mai numesc liste FIFO ( First In First Out ), adica de tip primul venit, primul servit.

Cele mai uzuale implementari ale cozii sunt cu ajutorul tipului pointer si al tablourilor circulare.

Coada bazata pe prioritate e strucutra de date abstracta care permite insertia unui nou element si suprimarea celui mai mare element dintre cele existente. Structura difera de coada (din care se suprima primul venit, deci elementul cel mai vechi ) si de stiva ( din care se suprima ultimul venit, deci cel mai nou ).

Asupra acestei structuri de date, ale carei elemente sunt articole cu chei ( sau prioritati ), se definesc operatiile :

GENEREAZA - o coada bazata pe prioritati, pornind de la N elemente ( succesiune de insertii )

INSEREAZA - un nou element

EXTRAGE - cel mai mare element

INLOCUIRE - a celui mai mare element cu unul nou, mai putin prioritar ( insertie + suprimare )

SCHIMBA - prioritatea unui element ( suprimare + insertie )

SUPRIMA - un element oarecare, precizat

REUNESTE - doua cozi in una singura.

Ca implementari a acestei structuri de date, sunt mai uzuale cele ce folosesc liste neordonate, liste ordonate dupa prioritate, ansamble.

Singurul element din coada la care avem acces direct este cel de la inceput.

Operatii caracteristice[1]

Singurele operatii ce pot fi executate cu o coada sunt:

crearea unei cozi vide;

inserarea unui element in coada;

extragerea unui element din coada;

accesarea unui element.

Executarea acestor operatii asupra unei cozi presupune cunoasterea inceputului cozii (notat Inc) si a sfarsitului acesteia(notat Sf).

Datorita faptului ca intotdeauna este extras ("servit") primul element din coada, iar inserarea oricarui nou element se face la sfarsit ("la coada"), coada este definita ca o strucutra de date care functioneaza dupa principiul FIFO[2].

Care este utilitatea unei cozi?

Utilitatea 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 sosit" si ele sunt retinute in coada pana cand pot fi prelucrate. In informatica, cozile sunt utilizate frecvent.

De exemplu, sa consideram ca avem o retea de calculatoare si o singura imprimanta. Cand utilizatorii retelei vor da comenzi de tiparire, imprimanta nu poate raspunde tuturor comenzilor in acelasi timp. Prin urmare, comenzile de tiparire primite sunt inregistrate intr-o coada (Print Queue - coada de tiparire). Imprimanta va tipari documentele pe rand, in ordinea in care au fost inregistrate in coada. Un alt exemplu: pentru a mari viteza de executie, microprocesoarele utilizeaza o coada de instructiuni in care sunt memorate instructiunile ce urmeaza a fi executate.

Cum implementam o coada?

Coada este o strucutra de date abstracta care poate fi implementata in diferite moduri. Un exemplu ar fi implementata statica a unei cozi, retinand elementele sale intr-un vector.

Exemplul urmator reprezinta declararea unei cozi cu elemente de tip int alocata 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 in vector de la pozitia Inc pana la pozitia Sf, deci numarul lor este Sf - Inc + 1.