Structuri de date: Coada (FIFO)

• Structuri de date și algoritmi, curs IS – Anul II, prezintă structura de date de tip coadă.

Tipul Abstract de Date (TAD) Coadă

• Coada este o listă specială, organizată pe principiul FIFO (First In - First Out, primul sosit - primul servit) sau LILO (Last In - Last Out)
• Inserarea se realizează numai la sfârșitul listei
• Elementul șters este cel de la începutul listei

Operații pe Structuri de Tipul Coadă

• Put: Inserarea unui atom (nod) la sfârșitul cozii (echivalent Insert, Enqueue).
• Get: Îndepărtarea primului atom (nod) al cozii (echivalent Delete, Dequeue).
• Front: Returnarea informației primului atom (nod) al cozii fără a-l șterge (echivalent Top, Peak).
• Init: Inițializarea cozii (coadă vidă).
• IsEmpty: Returnează 1 (true) dacă coada este goală și 0 (false) dacă coada conține atomi.

Exemple de Utilizare a Cozilor

• Playlist-urile

• Cozi de mesaje într-o rețea de comunicații

• Comenzile de tipărire în coada de așteptare a imprimantei

• Comenzile clienților pe un portal web.

• Există situații speciale în care principiul FIFO este încălcat, cum ar fi cererile de întreruperi către sistemul de operare sau modelarea cazului în care o persoană cu nevoi speciale "sare" peste coadă, rezultând o coadă de priorități.

Implementare

• Implementarea cozilor este similară cu cea a listelor sau stivelor și poate fi dinamică sau statică

Coada - Implementare Dinamică

• Pentru implementarea dinamică, este nevoie de doi pointeri spre primul și ultimul atom (nod) din structură, deoarece operațiile de inserare (put), ștergere (get) și consultare sunt permise doar la unul din cele două capete ale cozii:
• head (primul nod inserat): Permite obținerea primului element din coadă (get, front).
• tail (ultimul nod inserat): Permite inserarea unui nou element în coadă (put).

Structura de date și funcțiile de baza in C

• typedef int atom; - Definirea tipului de date pentru atom

• struct Element - Structura unui element al cozii, conținând informația (info) și un pointer către elementul următor (*succ)

• struct Queue - Structura cozii, conținând pointeri către primul (*head) și ultimul element (*tail)

• Funcții:

  • Queue InitQ(void); - Inițializează coada
  • int IsEmptyQ(Queue q); - Verifică dacă coada este goală
  • void Put (Queue &q, Atom x); - Adaugă un element în coadă
  • Atom Get(Queue &q); - Extrage un elemt din coada
  • Atom Front(Queue q); - Returnează primul element din coada

• InitQ(void) inițializează o coadă cu ambii pointeri (head și tail) nuli

• IsEmptyQ(Queue q) verifică dacă ambii pointeri (head și tail) sunt nuli, indicând o coadă goală

• "Put" inserează un nod nou în coadă si aloca memorie

• Get: Se extrage (șterge) un nod din coada, se obține pointer către primul nod care urmează a fi șters, se salvează valoarea ce va fi returnată, se actualizează head-ul cozii și se dealocă memoria

Coada – Implementare Statică

• O coadă statică este implementată pe un spațiu de memorare de tip tablou (vector).
• Pentru păstrarea timpului de execuție constant O(1) atât pentru operația Put cat si pentru Get, nu trebuiesc mutate elementele cozii în vector.
• Se utilizează doi indici pe vector: unul pe începutul cozii (head) şi unul pe sfârşitul ei (tail).
• Tail va indica prima poziție liberă în care se poate insera un element și NU poziția pe care s-a inserat ultimul element.
• Astfel, o poziție rămâne neocupată când coada va fi plină!