streamalism.org

1. Prehľad

V tomto výučbe si ukážeme, ako používať Java ArrayDeque triedy - čo je implementácia Deque rozhranie.

An ArrayDeque (tiež známy ako „Array Double Ended Queue“, vyslovovaný ako „ArrayDeck“) je špeciálny druh pestovateľného poľa, ktoré nám umožňuje pridať alebo odobrať prvok z oboch strán.

An ArrayDeque implementáciu je možné použiť ako a Stoh (Last-In-First-Out) alebo a Fronta(Prvý dnu prvý von).

2. Stručný prehľad API

Pre každú operáciu máme v zásade dve možnosti.

Prvú skupinu tvoria metódy, ktoré v prípade zlyhania operácie vyvolajú výnimku. Druhá skupina vráti stav alebo hodnotu:

3. Používanie metód

Pozrime sa na niekoľko jednoduchých príkladov toho, ako môžeme využiť ArrayDeque.

3.1. Použitím ArrayDeque ako Stoh

Začneme príkladom, ako môžeme s triedou zaobchádzať ako s Stoh - a stlačte prvok:

@Test public void whenPush_addsAtFirst () {Deque stack = new ArrayDeque (); stack.push ("prvý"); stack.push ("druhý"); assertEquals ("druhý", stack.getFirst ()); } 

Pozrime sa tiež, ako môžeme vysunúť prvok z ArrayDeque - pri použití ako zásobník:

@Test public void whenPop_removesLast () {Deque stack = new ArrayDeque (); stack.push ("prvý"); stack.push ("druhý"); assertEquals ("druhý", stack.pop ()); } 

The pop metóda hodí NoSuchElementException keď je stoh prázdny.

3.2. Použitím ArrayDeque ako Fronta

Začnime teraz jednoduchým príkladom, ktorý ukazuje, ako môžeme ponúknuť prvok v ArrayDeque - keď sa používa ako jednoduchý Fronta:

@Test public void whenOffer_addsAtLast () {Deque queue = new ArrayDeque (); queue.offer ("prvý"); queue.offer ("druhý"); assertEquals ("druhý", queue.getLast ()); } 

A pozrime sa, ako môžeme dopytovať prvok z ArrayDeque, tiež ak sa používa ako Fronta:

@Test public void whenPoll_removesFirst () {Deque queue = new ArrayDeque (); queue.offer ("prvý"); queue.offer ("druhý"); assertEquals ("prvý", queue.poll ()); } 

The anketa metóda vracia a nulový hodnota, ak je rad prázdny.

4. Ako sa má ArrayDeque Implementovaná

Pod kapotou je ArrayDeque je kryté poľom, ktoré pri vyplnení zdvojnásobí svoju veľkosť.

Spočiatku je pole inicializované s veľkosťou 16. Je implementované ako obojstranný front, kde zachováva dva ukazovatele, a to hlavu a chvost.

Pozrime sa na túto logiku v praxi - na vysokej úrovni.

4.1. ArrayDeque ako Stack

Ako je zrejmé, keď používateľ pridá prvok pomocou znaku tam metódou, posúva hlavný ukazovateľ o jednu.

Keď vysunieme prvok, nastaví ho na pozíciu hlavy ako nulový takže prvok mohol byť zhromažďovaný odpadkami a potom posúva hlavný ukazovateľ o jeden dozadu.

4.2. ArrayDeque ako Fronta

Keď pridáme prvok pomocou ponuka metódou, posúva chvostový ukazovateľ o jednu.

Zatiaľ čo keď používateľ hlasuje o prvok, nastaví prvok v polohe hlavy na hodnotu null, aby bolo možné prvok zbierať, a potom posúva ukazovateľ hlavy.

4.3. Poznámky k ArrayDeque

Na záver ešte niekoľko poznámok, ktoré stoja za pochopenie a zapamätanie si tejto konkrétnej implementácie:

• Nie je to bezpečné pre vlákna
• Nulové prvky nie sú akceptované
• Funguje výrazne rýchlejšie ako synchronizované Stoh
• Je rýchlejšia fronta ako LinkedList z dôvodu lepšej referenčnej lokality
• Väčšina operácií má amortizovanú konštantnú časovú zložitosť
• An Iterátor vrátený ArrayDeque je rýchle zlyhanie
• ArrayDeque automaticky zdvojnásobí veľkosť poľa, keď sa ukazovateľ hlavy a chvosta stretne pri pridávaní prvku

5. Záver

V tomto krátkom článku sme ilustrovali použitie metód v ArrayDeque.

Implementáciu všetkých týchto príkladov možno nájsť v projekte GitHub; toto je projekt založený na Maven, takže by malo byť ľahké ho importovať a spustiť tak, ako je.