start     Articole     Despre mine    

Cum sta un vector la coada

Stiu ca titlul asta suna ca inceputul unui banc, dar te asigur ca ce discut aici sunt treburi serioase :-). Am inceput cu articolul trecut o incursiune interesanta in lumea structurilor de date. Ai vazut acolo cum poti implementa o stiva folosindu-te de un vector si o variabila. Iti voi arata in articolul acesta cum poti implementa o coada folosind un vector si doua variabile.

 

Coada

Cand te gandesti la structura de date numita coada nu te gandi la coada vreunui animal. Gandeste-te la coada care se formeaza la casa unui supermarket.

Adica un sir de oameni in care pe la un capat se intra si pe la celalalt capat se iese.

Capatul pe la care se intra se numeste coada cozii, iar capatul pe la care se iese se numeste capul cozii.

Daca la stiva ultimul element introdus era primul ce urma a fi scos, la coada primul element introdus este primul ce va fi scos. (In engleza la treaba asta ii zice FIFO (First In, First Out).)

Altfel spus, la stiva elementele sunt scoase in ordine inversa fata de cum au fost introduse, iar la coada elementele sunt scoase in aceeasi ordine in care au fost introduse.

 

Cum se implementeaza o coada

Cel mai simplu poti implementa o coada folosind un vector (numit, de exemplu, coada) (cu un numar de elemente suficient de mare pentru a incapea in el toate elementele care se vor adauga in coada la vreun moment dat) si doua variabile — capul_cozii si coada_cozii (in care se vor memora pozitia din care va fi scos urmatorul element si, respectiv, pozitia in care se va insera urmatorul element in vectorul coada).

Desenul urmator vrea sa explice cele spuse in paragraful anterior.

Prin urmare, atunci cand vrei sa adaugi un element in coada faci asa:

       coada[coada_cozii] = element_nou;
       coada_cozii = coada_cozii+1;

Pare OK, nu? Adica adaugi noul element in vectorul coada in pozitia specificata prin valoarea memorata in variabila coada_cozii, iar apoi muti coada cozii cu o pozitia mai la dreapata.

Dar ce se intampla atunci cand valoarea din variabila coada_cozii ajunge sa depaseasca numarul de elemente disponibile din vector? Se va produce o eroare atunci cand voi incerca sa adaug un nou element in coada.

 

Problema se poate rezolva transformand vectorul coada intr-un vector circular. Astfel, daca de exemplu vectorul coada are 10 elemente, se va considera ca elementul coada[0] il are in stanga lui pe elementul coada[9] (si ca elementul coada[9] il are in dreapta lui pe elementul coada[0]).

Practic, lucrurile s-ar scrie asa:

       coada[coada_cozii] = element_nou;
       coada_cozii = (coada_cozii+1) % 10;

Rezultatul operatiei 10 % 10 (adica restul impartirii lui 10 la 10) este 0, ceea ce inseamna ca dupa 9 nu va urma 10, ci 0.

 

Similar, cand vrei sa scoti un element din coada, faci asa:

       element_scos = coada[capul_cozii];
       capul_cozii = (capul_cozii+1) % 10;

 

Initial, cand coada e goala, atat capul_cozii cat si coada_cozii vor avea aceeasi valoare. (Nu conteaza care valoare, caci vectorul e circular.)

Numarul de elemente existente in coada este egal cu:

       nr_elemente = coada_cozii-capul_cozii;

Pare corect, nu?

Ups! Dar ce te faci cand valoarea din capul_cozii e mai mare decat valoarea din coada_cozii (ceea ce e posibil sa se intample, caci vectorul e circular, remember?)?

Problema poate fi remediata astfel (in ideea ca vectorul coada are 10 elemente):

       nr_elemente = coada_cozii-capul_cozii;
       if (nr_elemente < 0)
       {
              nr_elemente = 10-capul_cozii + coada_cozii;
       }

 

Ca si pana acum, cel mai bine inveti facand -- asa ca iata mai jos simulatorul nostru. Apasa "Reseteaza..." si apoi "Executa...". Vei vedea pe ecran 10 puncte colorate dispuse aleator. Prin click pe un punct colorat, acel punct se va adauga in coada de jos (pe linia cu coordonata y egala cu 0, deci imediat in afara ecranului de 10x10 puncte). (In felul acesta vei putea vedea la lucru operatiunea de adaugare in coada.) Prin click pe un punct alb, acel punct se va completa cu un element din coada. (Vei vedea astfel cum lucreaza operatiunea de scoatere din coada.)

(Browserul tau nu suporta Canvas!...)

 

Ce parere ai? E amuzanta coada? 🙂

Alatura-te celor peste 1000 de oameni din armata noastra de creiere cu muschi si vei primi testul care iti va spune daca ai sau nu minte de programator:

(nu trimit spam; te tin la curent cu noutatile)


 

Cu drag,

Florin





Loading Facebook Comments ...