O coada este o lista liniara in care stergerea si accesarea unui element se pot face numai pe la un capat al cozii, numit front, iar inserarea se face la celalalt capat al cozii, numit rear. Se poate face o analogie intre o coada folosita in programar 939j95j e si, de exemplu, o coada pentru tiparirea mai multor fisiere text. Pentru tiparirea unui nou fisier va trebui sa asteptam pana cand toate fisierele sunt tiparite in ordinea in care comenzile de tiparire au fost efectuate.
|
|
|
front
|
Cozile se mai numesc si liste FIFO (first in/first out) deoarece primul element care este extras din coada este primul introdus.
Vom nota inserarea unui element a intr-o coada C: a C, iar stergerea unui element a dintr-o coada C: C a.
In alocarea secventiala, presupunand ca avem o coada definita
T x[N];
unde N este o constanta suficient de mare, T este un tip de date definit anterior (eventual printr-o definitie de tipul typedef), iar elementele cozii sunt in ordine x[R], x[R+1], ..., x[F], cu indicii 0 R F N - 1
x[R] x[R+1] x[F]
atunci operatia de inserare elem_nou C se poate descrie astfel:
if R = 0 and F = N - 1 then OVERFLOW
else if R > 0 then x[R - 1] = elem_nou
R = R -1
else for i = F, R, -1
x[i+1] = x[i]
endfor
x[0] = elem_nou
F = F +1
endif
endif
iar operatia de stergere C elem_sters se poate descrie astfel:
if R > F then UNDERFLOW
else elem_sters = x[F]
F = F -1
endif
In alocarea inlantuita, folosim aceeasi structura ca si in cazul listei liniare
struct nod
typedef struct nod NOD;
unde T este presupus definit anterior (eventual printr-o definitie typedef) si notam cu front, si respectiv rear, pointerul la primul nod al cozii, si respectiv la ultimul nod.
NOD *front, rear;
Cu aceste notatii, operatiile cu cozi se pot descrie astfel:
|
inserarea unui nod nou: Algoritm: Folosim variabilele info_nou ce contine valoarea informatiei nodului ce trebuie introdus in lista si p pointer la un nod. Aloca memorie pentru un nod nou. Returneaza p, un pointer la noul nod. if p NULL then p -> link = NULL p -> info = info_nou rear -> link = p rear = p else OVERFLOW endif |
front
 |
...........
 |
rear
|
|
stergerea/accesarea unui nod:
Algoritm:
if front = NULL then UNDERFLOW
else elem_sters = front -> info
front = front -> link
endif
info
front
|
.............
rear
Scrieti
un program care implementeaza algoritmii de mai sus pentru o coada.
|
