Uvod u Java ArrayDeque

1. Pregled

U ovom uputstvu pokazat ćemo kako koristiti Javu ArrayDeque klasa - što je provedba Deque sučelje.

An ArrayDeque (poznat i kao "Array Double Ended Queue", izgovara se kao "ArrayDeck") je posebna vrsta polja za uzgoj koji nam omogućuje dodavanje ili uklanjanje elementa s obje strane.

An ArrayDeque implementacija se može koristiti kao a Stog (Last-In-First-Out) ili a Red(Prvo-prvo-izašlo).

2. API ukratko

Za svaku operaciju u osnovi imamo dvije mogućnosti.

Prvu skupinu čine metode koje izuzimaju iznimku ako operacija ne uspije. Druga grupa vraća status ili vrijednost:

OperacijaMetodaMetoda bacanja Izuzetak
Umetak iz glaveponudaPrvi (e)addFirst (e)
Uklanjanje s glaveanketaPrvo ()removeFirst ()
Dohvat od HeadpeekFirst ()getFirst ()
Umetak iz repaponudaPosljednja (e)addLast (e)
Uklanjanje s repapollLast ()removeLast ()
Dohvat iz RepapeekLast ()getLast ()

3. Korištenje metoda

Pogledajmo nekoliko jednostavnih primjera kako možemo koristiti ArrayDeque.

3.1. Koristeći ArrayDeque kao Stog

Počet ćemo s primjerom kako se prema razredu možemo ponašati kao prema Stog - i pritisnite element:

@Test public void whenPush_addsAtFirst () {Deque stog = novi ArrayDeque (); stack.push ("prvi"); stack.push ("drugi"); assertEquals ("drugi", stack.getFirst ()); } 

Pogledajmo i kako možemo izbaciti element iz ArrayDeque - kada se koristi kao stog:

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

The pop metoda baca NoSuchElementException kad je stog prazan.

3.2. Koristeći ArrayDeque kao Red

Krenimo sada s jednostavnim primjerom koji pokazuje kako možemo ponuditi element u ArrayDeque - kada se koristi kao jednostavan Red:

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

Ajmo vidjeti kako možemo anketirati element iz ArrayDeque, također kada se koristi kao a Red:

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

The anketa metoda vraća a null vrijednost ako je red prazan.

4. Kako ArrayDeque Provedeno

Ispod poklopca motora ArrayDeque je poduprt nizom koji udvostručuje svoju veličinu kad se napuni.

U početku se niz inicijalizira veličinom 16. Implementiran je kao dvostruki red gdje održava dva pokazivača, a to su glava i rep.

Pogledajmo ovu logiku na djelu - na visokoj razini.

4.1. ArrayDeque kao Stack

Kao što se može vidjeti, kada korisnik doda element pomoću gurnuti metodom pomiče pokazivač glave za jedan.

Kada stavimo element, postavlja ga na položaj glave kao null tako da se element može sakupljati smeće, a zatim pomiče pokazivač glave jedan za drugim.

4.2. ArrayDeque kao Red

Kada dodamo element pomoću ponuda metodom pomiče repni pokazivač za jedan.

Dok kada korisnik anketira element, on postavlja element na poziciji glave na nulu, tako da element može biti sakupljeno smeće, a zatim pomiče pokazivač glave.

4.3. Napomene o ArrayDeque

Na kraju, još nekoliko napomena koje vrijedi razumjeti i zapamtiti o ovoj konkretnoj provedbi:

  • Nije sigurno na niti
  • Ništavni elementi nisu prihvaćeni
  • Djeluje znatno brže od sinkroniziranog Stog
  • Je li brži red od LinkedList zbog boljeg lokaliteta reference
  • Većina operacija amortizira stalnu vremensku složenost
  • An Iterator vratio ArrayDeque je brz
  • ArrayDeque automatski udvostručuje veličinu niza kad se pokazivač glave i repa susretnu jedni s drugima tijekom dodavanja elementa

5. Zaključak

U ovom kratkom članku ilustrirali smo upotrebu metoda u ArrayDeque.

Provedba svih ovih primjera može se naći u projektu GitHub; ovo je projekt zasnovan na Mavenu, pa bi ga trebalo biti lako uvesti i pokrenuti takav kakav jest.