O coadă cu două stive

Să presupunem că avem la dispoziție o structură de date de tip stivă. Dorim să o folosim pentru a simula o structură de date de tip coadă. Cu o singură stivă e mai greu, dar putem folosi două.

Așadar, dorim să putem extrage elementele în ordinea în care acestea au fost introduse având la dispoziție o structură din care le putem extrage în ordine inversă.

Interfața

Pentru început vom defini o interfață foarte simplă pentru coada noastră. Operațiile pe care le vom permite vor fi adăugarea unui element, eliminarea unui element și verificare faptului dacă avem sau nu o coadă vidă. Așadar, interfața noastră este:

Verificarea

Vom scrie pentru început un mic test să vedem dacă implementarea este corectă. Vom insera în structura noastră numere consecutive începând cu 1 și le vom extrage. La fiecare pas vom decide aleator dacă inserăm sau extragem; în cazul în care structura noastră nu conține niciun element nu vom putea extrage. La sfârșit, vom extrage toate elementele rămase.

Vom lucra doar cu interfața. Singurul loc în care va apărea implementarea propriu-zisă va fi inițializarea cozii. Testul nostru ar putea arăta așa:

O implementare greșită

Să vedem ce se întâmplă dacă nu implementăm corect coada. Testul nostru adaugă numerele cuprinse între 0 și 9 și apoi le extrage. Ne-am aștepta ca la ieșire să avem acest numere, în ordinea corectă.

O implementare greșită ar fi să folosim o stivă în loc de o coadă:

Dacă rulăm testul nu obținem rezultatul corect decât cu un mare noroc (trebuie să fi adăugat câte un element și apoi să-l fi extras imediat). Iată rezultatul unei rulări:

Să mai încercăm odată:

O implementare corectă

Dacă folosim o simplă listă înlănțuită, avem o implementare corectă:

Dacă rulăm testul, obținem ordinea corectă de fiecare dată:

O implementare "exotică"

Acum că suntem oarecum siguri că putem testa implementările, putem încerca și una interesantă: simularea comportamentului cozii folosind două stive.

Când adăugăm elemente le vom pune în prima stivă. Când extragem elemente, nu putem să extragem din această stivă fiindcă am avea prima implementare din articol (cea greșită). Dar, dacă mutăm toate elementele din prima stivă în cea de-a doua, ordinea se schimbă din nou, ajungând să fie cea inițială și acum, am putea extrage elemente din a doua stivă. Mutăm elemente în a doua stivă doar atunci când e vidă; dacă nu e vidă, putem furniza elemente și ordinea este corectă.

Trebuie să fim atenți când verificăm dacă avem sau nu o coadă vidă. Coada este vidă dacă și numai dacă ambele stive sunt vide. Iată și implementarea:

Încheiere

Am văzut că putem verifica destul de ușor dacă am implementat corect ceva în cazul în care avem pregătite câteva teste. Putem testa în diverse moduri; sunt disponibile diverse biblioteci care să ne ajute. Dar, pentru problemele simple, un test ca cel de față este de obicei suficient.

Te-ar putea interesa și:

  • gpanther

    Posibile imbunatatiri:

    - folosirea unui framework de unittest (JUnit, TestNG, etc) ca sa nu fim nevoiti sa inspectam manual rezultatul (si poate nu observam greseala)

    - folosirea atat a "seed"-urilor predefinite cat si aleatoare pentru Random ca testele sa pot fi repetate (nu prea te ajuta un test care nu-i reproductibil - iti zice doar "undeva este o greseala in cod")

    - poate folosirea unei librarii care implementeaza Quickcheck (un algoritm popular pentru testare aleatoare)

    • Mihai Scorţaru

      Mulțumim pentru idei. Le vom pune în practică într-o serie de articole dedicate testării.
      Deocamdată, dorim doar să arătăm că scrierea testelor este utilă.