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.)

// Joc pentru intelegerea ideii de coada

// Datele programului:

var tabla = Matrice(10, 10);
var coada = Vector(10);
var capul_cozii = 0; 	// pozitia elementului ce va fi
						//  eliminat din coada
var coada_cozii = 0;	// pozitia unde va fi inserat
						//  un nou element in coada

// Functiile ajutatoare:

function InitializeazaTabla()
{
  // parcurge toate elementele
  //  din matricea "tabla" si
  //  pune in ele valoarea 0
  var x = 0;
  while (x < 10)
  {
    var y = 0;
    while (y < 10)
    {
      tabla[x][y] = 0;
      y = y+1;
    }
    x = x+1;
  }
}

function InitializeazaCoada()
{
  // parcurge toate elementele
  //  din vectorul "coada" si
  //  pune in ele valoarea 0
  var y = 0;
  while (y < 10)
  {
    coada[y] = 0;
    y = y+1;
  }
}

function ImprastieCuburi()
{
  // plaseaza in pozitii aleatoare 
  //  pe tabla 10 cuburi de culori
  //  aleatoare
  var nr = 0;
  while (nr < 7)
  {
    // genereaza un numar aleator cuprins
    //  intre 0 si 99-nr
    var pozitie = NrAleator(99-nr);
    // apoi parcurge toate punctele de pe
    //  tabla si gaseste al "pozitie"-lea
    //  punct liber
    var contor = 0;
    var x = 0;
    while (x < 10)
    {
      var y = 0;
      while (y < 10)
      {
        if (tabla[x][y] == 0)
        {
          contor = contor+1;
          if (contor == pozitie)
          {
            // pune in al "pozitie"-lea
            //  punct liber de pe tabla
            //  o culoare aleatoare (intre
            //  1 si 7)
            tabla[x][y] = 1+NrAleator(6);
          }
        }
        y = y+1;
      }
      x = x+1;
    }
    nr = nr+1;
  }
}

function DeseneazaEcran()
{
  // parcurge fiecare punct de pe tabla
  //  si in pozitia corespunzatoare de pe
  //  ecran....
  var x = 0;
  while (x < 10)
  {
    var y = 0;
    while (y < 10)
    {
      // ....aprinde punctul folosind culoarea
      //  memorata in matricea "tabla"
      AprindeNrCul(x+1, y+1, tabla[x][y]);
      y = y+1;
    }
    x = x+1;
  }
  // parcurge fiecare element din coada
  //  de la cap spre coada si in pozitia
  //  corespunzatoare de pe ecran...
  x = 0;
  while (x < 10)
  {
    // ....aprinde punctul folosind culoarea
    //  memorata in vectorul "coada"
    AprindeNrCul(1+x, 0, coada[x]);
    x = x+1;
  }
}

function FunctieMouse(ev)
{
  var xm = XMouse(ev);
  var ym = YMouse(ev);
  if ( (xm>=1) && (xm<=10) && (ym>=1) && (ym<=10) )
  {
    // daca s-a facut click pe un punct
    //  gol de pe tabla
    if (tabla[xm-1][ym-1] == 0)
    {
      // daca coada nu era goala, scoate
      //  elementul din capul ei si pune-l
      //  in pozitia pe care s-a facut click
      if (capul_cozii != coada_cozii)
      {
        tabla[xm-1][ym-1] = coada[capul_cozii];
        // si deseneaza pe ecran
        AprindeNrCul(xm, ym, tabla[xm-1][ym-1]);
        AprindeNrCul(1+capul_cozii, 0, 0);
        capul_cozii = (capul_cozii+1) % 10;
      }
    }
    // altfel (deci daca s-a facut click
    //  pe un punct ocupat de un cub colorat)
    else
    {
      // pune cubul in stiva
      coada[coada_cozii] = tabla[xm-1][ym-1];
      tabla[xm-1][ym-1] = 0;
      // si deseneaza pe ecran
      AprindeNrCul(xm, ym, 0);
      AprindeNrCul(1+coada_cozii, 0, coada[coada_cozii]);
      coada_cozii = (coada_cozii+1) % 10;
    }
  }
}

// Programul propriu-zis:

InitializeazaTabla();
InitializeazaCoada();
ImprastieCuburi();
DeseneazaEcran();
AscultaMouse(FunctieMouse);

Ce parere ai? E amuzanta coada? 🙂

Cu drag,

Florin