RSS

Coada

07 Oct

Coada

Definitie

Coada este o structura la care adaugarea elementelor se realizeaza la sfarsit (PUSH) iar eliminarea unui element se realizeaza de la inceput.

OBS: conform definitiei se pate afirma ca o coada este de tip FIFO (first input, first output = primul venit, primul servit). Evident, modelul unui sir la un ghiseu este cea mai nimerita reprezentare pentru o coada.

Implementare 1

Ca si la stiva, putem folosi vectorul in reprezentarea unei cozi.

Declarare:

int C[100], sc;  //sc este sfarsitul cozii

Coada vida

sc=0; //nu exista nici un element in coada

PUSH – adaugarea unui element (la sfarsit)

sc++; cin>>c[sc]; //facem loc unui noi valori si citim valoarea dorita

POP – eliminarea primului element

Urmand modelul real (al unei cozi la un ghiseu), toate elementele, incepand cu pozitia a 2-a, vor fi mutate la stanga. Coada va avea acum un element in minus.

for(I=2;i<=sc;i++) c[I-1]=c[I];

sc–;

Practic, oricare operatie tip POP este de complexitate N (numarul de elemente din coada), ceea ce este destul de mult. O alternativa ar fi sa nu respectam modelul real, in care se muta cei care stau la rand, ci sa il punem pe functionar sa se miste cu biroul lui.

Avem nevoie de un indice IC care sa arate cine este persoana/elementul din fata functionarului.

Implementare 2

Declarare:

int C[100], sc, ic;  //sc este sfarsitul cozii; ic este inceputul cozii

Coada vida

Initial: sc=0; ic =0//nu exista nici un element in coada

Pe parcurs coada va fi vida cand ic>sc

PUSH – adaugarea unui element (la sfarsit)

if(sc==0) ic++; //marchez inceputul cozii
sc++; cin>>c[sc]; //facem loc unui noi valori si citim valoarea dorita

POP – eliminarea primului element

Eliminarea primului element se reduce la deplasarea inceputului cozii la dreapta.

if(ic<=sc) ic++;

Se observa ca operatia se rezolva intr-un pas, nu in N ca in cazul anterior

 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
%d bloggers like this: