Fronty, rady, zásobníky, fifá, lifá… v Jave

2012/06/29

Categories: Java programovanie Tags: dátové štruktúry front Java rad zásobník

Zásobníky a rady nie sú práve najčastejšie používanou dátovou štruktúrou Java aplikácií, ale z času na čas dôjde na i na ne. Ako ich elegantne a ľahko použiť bez toho, aby sme zabili kopu času ich reimplementáciou?

Rekapitulácia

Zrekapitulujme si terminológiu:

Implementácie v Jave

Neopovážte sa implementovať rad a zásobník po svojom! (Pokiaľ fakt neviete, čo robíte.)

K dispozícii je totiž pestrá paleta tried pre obe situácie.

Starý dobrý java.util.Stack

Rýchle prehľadanie tried odhalí triedu java.util.Stack. Táto trieda je s nami od čias Javy 1.0. (Kto neverí, nech pozrie do praJavadocu.) Z dnešného pohľadu je táto trieda, slušne povedané, svojská, ale v tých časoch vývojári azda ani netušili, čo sa z Javy vykľuje. (Našťastie existuje jej krajšia verzia.)

K dispozícii sú predovšetkým klasické metódy:

Ešte podrobnejší pohľad na java.util.Stack ukáže kúzelnú dedičnosť

public class Stack extends java.util.Vector

Rozhodne to nie je učebnicový príklad dedičnosti: Vector je prakticky ekvivalent ArrayListu a overenie starých materí „Je každý zásobník zoznamom založeným na poli?” jednoducho nefunguje. Poburovanie však je pomerne zbytočné: je to daň Javy 1.0, kde finty typu LinkedList ešte neexistovali.

Tak či onak, Stack zdedí všetky vectorovské metódy: môžete radostne pridávať doprostred zoznamu, mazať, hľadať, atď… akurát, že nie vždy to má celkom logický zmysel.

Pri vymýšľaní Java Collections Framework sa síce udiali s touto triedou niektoré pozitívne zmeny, ale veľa sa toho už zachrániť nedalo.

Jeden rozumný bočný efekt Stacku spočíva v thread-safety (vláknovej bezpečnosti) triedy. Keďže Vector je thread-safe, je takým aj zásobník… i keď i v tomto prípade už existujú oveľa lepšie a efektívnejšie kolekcie.

Vyčkajte chvíľu, rozoberieme si rad a k zásobníku sa ešte vrátime.

Rad java.util.Queue

V Javách pred verziou 5 by ste márne hľadali triedu pre rad – neostávalo vám nič iné, než zneužiť na to niektorý z klasických zoznamov. Po upratovaní v Jave päť vznikol interfejs java.util.Queue (nemenovaným známym vyslovovaným ako kveve, ale neradím vám po ňom opakovať). Ten rozširuje interfejs java.util.Collection o 6 metód. V skutočnosti ide o tri páry metód pre štandardné operácie vkladania, vyberania a nakúkania na začiatok radu. (Táto duplicita adresuje Stackovský problém pri manipulácii s prázdnym stackom.)

Ešte spomeniem drobné terminologické ujasnenie: hlava (head) radu je začiatok (z ktorého sa odoberajú prvky) a chvost (tail) je koniec, kam sa pridáva.

Pridávanie

Obe metódy však môžu vyhodiť NullPointerException pri pokuse vložiť null do radu, ktorý takéto elementy nepodporuje; a tiež môže otrieskať používateľovi o hlavu IllegalArgumentException, ak sa element nepodarí vložiť kvôli iným špecifickým obmedzeniam implementácie radu.

Odoberanie

Opäť máme dvojicu metód:

Nakúkanie

A ešte raz: ak chceme len nazrieť na hlavu radu bez jej vyhadzovania, máme:

Implementácie

Ak nahliadnete do JavaDocu, odhalíte haldu rozličných implementácií. Do tejto roly možno rovno použiť java.util.LinkedList (alias spojový zoznam), aj keď sa to zdá možno zvláštne.

Ak chcete poľovo zameraný rad, skúste java.util.ArrayDeque. A ak sa vám žiada vláknovo bezpečnej verzie, skúste napríklad ConcurrentLinkedQueue.

Bonusom sú implementácie pre zopár úloh konkurentného programovania:

Teraz však…

Naspäť k zásobníkom! (Back to the stack)

Hore sme si povedali, že Stack je nešťastná trieda s neveľkými možnosťami úprav API. V rámci kampane „do Javy 5 s úpravami” sa vymyslel jeden interfejs, ktorým sa mali zabiť dve muchy jednou ranou.

java.util.Deque (nečítajte ako dekve, ale ako „dek”) je double ended queue, teda, prepytujem, rad o dvoch koncoch. Implementácie tohto interfejsu môžu pridávať a uberať podľa potreby elementy z oboch koncov, čiže sa vedia správať buď ako zásobníky alebo ako rady.

Ekvivalentné metódy vyzerajú nasledovne:

Vkladanie

Vyberanie

Nakúkanie

Tu nastáva trošku chaos:

Sumár zásobníka

Ak sa na to pozrieme ešte raz, vieme si vymyslieť mnemotechnickú pomôcku:

  1. v prípade zásobníka pracujeme stále s hlavou deque. Hlava = vrchol = prvý prvok.
  2. metódy addFirst(), removeFirst() a getFirst() vyhadzujú výnimky
  3. metódy offerFirst(), pollFirst() a peekFirst() vracajú null, resp. false, ak sa operácia nepodarí.

Implementácie

Mnoho prípadov pokryje implementácia java.util.LinkedList. Nepatrným problémom je neexistencia implementácie konkurentného zásobníka, ale v prípade núdze môžete použiť java.util.concurrent.CopyOnWriteArrayList.

A ešte raz naspäť k radom!

„Dvojkoncový rad” deque rozširuje interface Queue a pridáva aliasy k zdedeným metódam. Zároveň poskytuje metódy na prácu s chvostom, kde platí rovnaká mnemotechnika ako pri radoch:

  1. metódy addLast(), removeLast() a getLast() vracajú prvky z chvosta a vyhadzujú výnimky
  2. metódy offerLast(), pollLast() a peekLast() vracajú null, resp. false, ak sa operácia nepodarí.

Aliasy sú nasledovné:

Implementácie

Sumár

Z praktického hľadiska je to jednoduché: vo väčšine prípadov stačí rad vyrobiť cez

Queue<String> rad = new LinkedList<String>();

a zásobník cez

Deque<String> zásobník = new LinkedList<String>();

a to stačí.

Do radu vkladáte cez offer(), vyberáte cez poll() a nakúkate cez peek() a do zásobníka pushujete cez offerFirst(), popujete cez pollFirst() a nakúkate cez peekFirst().

>> Home