Coada este un tip de date abstracte cu disciplină de acces al elementului primul intrat, primul ieșit ( FIFO , engleză first in, first out ). Adăugarea unui element (notat de obicei prin cuvântul coadă - pus într-o coadă) este posibilă numai la sfârșitul cozii, eșantionarea - doar de la începutul cozii (care este denumit în mod obișnuit cuvântul decodare - eliminați din coadă), în timp ce elementul selectat este eliminat din coadă.
Există mai multe moduri de a implementa o coadă în limbaje de programare.
Prima modalitate reprezintă coada ca o matrice și două variabile întregi la început și la sfârșit.
De obicei startindică către capul cozii, end elementul care va fi umplut atunci când un nou element intră în coadă. Când un element este adăugat la coadă, q[end]noul element de coadă este scris și enddecrementat cu unu. Dacă valoarea end devine mai mică decât 1, atunci facem o buclă în jurul matricei, iar valoarea variabilei devine egală cu n. Extragerea unui element din coadă se face într-un mod similar: după extragerea unui element q[start]din coadă, variabila starteste redusă cu 1. Cu astfel de algoritmi, o celulă din coadă nva fi întotdeauna neocupată (deoarece o coadă cu nelemente nu poate fi distinsă ). dintr-unul gol), care este compensat de simplitatea algoritmilor.
Avantajele acestei metode: este posibilă o ușoară economisire a memoriei în comparație cu a doua metodă; mai usor de dezvoltat.
Dezavantaje: Numărul maxim de elemente din coadă este limitat de dimensiunea matricei. Când depășește, necesită realocarea memoriei și copierea tuturor elementelor într-o matrice nouă.
A doua metodă se bazează pe lucrul cu memoria dinamică. Coada este reprezentată ca o listă liniară , în care adăugarea/eliminarea elementelor provine strict de la capetele respective.
Avantajele acestei metode: dimensiunea cozii este limitată doar de cantitatea de memorie.
Dezavantaje: mai greu de dezvoltat; este nevoie de mai multă memorie; atunci când se lucrează cu o astfel de coadă, memoria este mai fragmentată; coada este ceva mai lentă.
Metodele de coadă pot fi implementate pe baza a două stive S1 și S2după cum se arată mai jos:
coada procedurii ( x ): S1.push( x ) Funcția dequeue(): dacă S2 este gol: dacă S1 este gol: raportați eroare: coada este goală până când S1 este gol: S2.push(S1.pop()) returnează S2.pop()Această metodă de implementare este cea mai convenabilă ca bază pentru construirea unei cozi persistente . .
Cozile sunt implementate în aproape toate limbajele de programare dezvoltate. CLI furnizează clasa System.Collections.Queue pentru aceasta, cu metodele Enqueue și Dequeue . STL are, de asemenea, coada de clasă<>, definită în coada de fișiere antet. Folosește aceeași terminologie (push și pop) ca și stivele .
Coada în programare este folosită, ca și în viața reală, atunci când trebuie să efectuați unele acțiuni în ordinea în care sunt primite, realizându-le secvențial. Un exemplu este organizarea de evenimente în Windows. Atunci când utilizatorul efectuează o acțiune asupra aplicației, procedura corespunzătoare nu este apelată în aplicație (la urma urmei, în acest moment aplicația poate efectua alte acțiuni), ci i se trimite un mesaj care conține informații despre acțiunea întreprinsă, acest mesaj este pus în coadă și numai atunci când mesajele care au venit mai devreme sunt procesate, aplicația va efectua acțiunea necesară.
Buffer-ul de tastatură BIOS este organizat ca o matrice inelă, de obicei cu 16 cuvinte mașină și două indicatoare: către următorul element din el și către primul element neocupat.
| Structuri de date | |
|---|---|
| Liste | |
| Copaci | |
| Contează | |
| Alte | |