Pinud ja järjekorrad

Sissejuhatus

Pinud (Stack) ja järjekorrad (Queue) on andmestruktuurid, mida eristab see, mis järjekorras nad andmeid töötlevad.

• Järjekord töötab FIFO (First In, First Out) põhimõttel. Näiteks järjekorrad poeleti taga, esimene klient järjekorras saab esimesena oma ostude eest makstud.
• Pinu töötab LIFO (Last In, First Out) põhimõttel. Näiteks tooted müügiautomaadis - kui osta näiteks sealt šokolaadibatoon, siis sa saad kõige esimese ehk selle, mis masinasse kõige viimasena sisestati.

Javas on mõlemad realiseeritud Deque liidese kaudu ning kindla implementatsioonina reeglina kasutatakse ArrayDeque-d.

Queue ehk järjekord

Järjekord on andmestruktuur, mis töötab FIFO (First In, First Out) põhimõttel. Elemente lisatakse kogumi lõppu ning võetakse välja algusest.
Näiteks:

• Oletame et meil on järjekord, mille sees on elemendid [A, B, C]
• Kui lisada järjekorda uus element D, siis seis uueneb selliseks: [A, B, C, D]
• Kui järjekorrast nüüd eemaldada element, siis selleks osutub element A (järjekorras esimene) ning seis uueneks selliseks: [B, C, D]

Järjekordi kasutatakse (nagu nimigi ütleb) järjekordade loomiseks. Täpsemalt näiteks:

• Sõnumite järjekorrad
• Andmebaasi- ja veebipäringute läbiviimiseks
• Andmevoogude puhverdamine jne.

Stack ehk pinu

Pinu on andmestruktuur, mis töötab LIFO (Last In, First Out) põhimõttel. Elemente lisatakse kogumi lõppu ning võetakse välja ka lõpust.
Näiteks:

• Oletame, et meil on pinu, mille sees on elemendid [A, B, C]
• Kui lisada sinna uus element D, siis seis uueneb selliseks: [A, B, C, D]
• Kui nüüd pinust eemaldada element, siis selleks osutub D ning seis uueneb selliseks: [A, B, C]

Pinud tulevad kasuks kui on vaja mingitest tegevustest järge hoida, näiteks:

• Tekstiredaktorites undo/redo funktsionaalsus
• Veebibrauseri ajalugu
• Matemaatiliste tehete kontrollimine (RPN - Reverse Polish Notation)

Deque

Javas on peamiseks pinu ja järjekorra implementatsiooniks Deque ehk double-ended queue. See on liides, mis võimaldab elementide lisamist ja eemaldamist kogumikku mõlemalt poolelt (add/remove first/last meetodid).

ArrayDeque

Kõige enim levinud Deque implementatsioon on ArrayDeque.

Seda saab luua järgnevalt:

Deque<String> dq = new ArrayDeque<>();

ArrayDeque kasutamine järjekorrana

Järjekorrana kasutamiseks lisatakse elemendid lõppu ning eemaldatakse neid algusest:

Deque<String> queue = new ArrayDeque<>();

queue.offer(item);      // Add to queue
String item = queue.poll();  // Remove from queue
String next = queue.peekFirst();    // View next item without removing it

ArrayDeque kasutamine pinuna

Pinuna kasutamiseks lisatakse elemendid lõppu ning eemaldatakse ka lõpust:

Deque<String> stack = new ArrayDeque<>();

stack.push(item);         // Push onto stack
String item = stack.pop();       // Pop from stack
String top = stack.peek();       // View top item without removing it

Deque meetodite sünonüümid

Eelnevates näidetes näidati järjekorra/pinu kohta kehtivate spetsiifiliste meetodite kaudu tegutsemist. Tegelikult on nende operatsioonide jaoks erinevaid meetodeid:

Tegevus	Queue (FIFO)	Stack (LIFO)	Deque
Add	offer(e)	push(e)	addFirst(e) / addLast(e)
Remove	poll()	pop()	removeFirst() / removeLast()
Examine	peek()	peek()	peekFirst() / peekLast()

Praktikas selgema koodiloetavuse jaoks:

• Järjekorra jaoks kasuta offer(), poll() või peek() meetodeid
• Pinu jaoks kasuta push(), pop() ja peek() meetodeid

Levinumad vead

Deque-ga tegelemisel esineb reeglina kahte tüüpi vigu. Esmalt ArrayDeque ei luba null-elemente lisada. Kui selleks peaks vajadus tekkima, siis saab kasutada LinkedList-i, mis täidab sarnast eesmärki ArrayDeque-le:

Deque<String> queue = new ArrayDeque<>();
queue.add(null);  // NullPointerException!

// LinkedList allows null
Deque<String> queue = new LinkedList<>();
queue.add(null);  // OK

Teine viga mis võib tekkida on seotud elementide võtmisega pinust/järjekorrast. Kui üritada eemaldada elemente tühjast ArrayDeque-st, tekib NoSuchElementException erind. Selle vältimiseks tasuks alati eelnevalt kontrollida, kas kogumis on veel elemente või kasutada spetsiifilisi meetodeid elementide pärimiseks:

// Bad - throws exception
String item = queue.remove();  // NoSuchElementException!

// Good - returns null if empty
String item = queue.poll();
if (item != null) {
    // Process item
}

// Or check first
if (!queue.isEmpty()) {
    String item = queue.remove();
}