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:
|
1 2 3 4 5 6 7 |
interface QueueInterface<T> { void enqueue(T item); T dequeue(); boolean isEmpty(); } |
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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
public class Test { public static void main(String[] args) { Random random = new Random(); QueueInterface<Integer> queue = new GInfoQueue<>(); for (int k = 0; k < 10; ) { if (random.nextBoolean() || queue.isEmpty()) { queue.enqueue(k++); } else { System.out.println(queue.dequeue()); } } while (!queue.isEmpty()) { System.out.println(queue.dequeue()); } } } |
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ă:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
class GInfoQueue<T> implements QueueInterface<T> { private Stack<T> stack; public GInfoQueue() { stack = new Stack<>(); } public void enqueue(T item) { stack.push(item); } public T dequeue() { return stack.pop(); } public boolean isEmpty() { return stack.isEmpty(); } } |
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:
|
1 2 3 4 5 6 7 8 9 10 |
4 7 6 8 5 9 3 2 1 0 |
Să mai încercăm odată:
|
1 2 3 4 5 6 7 8 9 10 |
1 0 2 3 5 4 6 9 8 7 |
O implementare corectă
Dacă folosim o simplă listă înlănțuită, avem o implementare corectă:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
class GInfoQueue<T> implements QueueInterface<T> { private LinkedList<T> list; public GInfoQueue() { list = new LinkedList<>(); } public void enqueue(T item) { list.add(item); } public T dequeue() { return list.poll(); } public boolean isEmpty() { return list.isEmpty(); } } |
Dacă rulăm testul, obținem ordinea corectă de fiecare dată:
|
1 2 3 4 5 6 7 8 9 10 |
0 1 2 3 4 5 6 7 8 9 |
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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
class GInfoQueue<T> implements QueueInterface<T> { private Stack<T> first, second; public GInfoQueue() { first = new Stack<>(); second = new Stack<>(); } public void enqueue(T item) { first.push(item); } public T dequeue() { if (second.isEmpty()) { while (!first.isEmpty()) { second.push(first.pop()); } } return second.pop(); } public boolean isEmpty() { return first.isEmpty() && second.isEmpty(); } } |
Î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.
