Introduksjon til Java ArrayDeque

1. Oversikt

I denne veiledningen viser vi hvordan du bruker Java-ene ArrayDeque klasse - som er en implementering av Deque grensesnitt.

An ArrayDeque (også kjent som en "Array Double Ended Queue", uttalt som "ArrayDeck") er en spesiell type dyrkbar matrise som lar oss legge til eller fjerne et element fra begge sider.

An ArrayDeque implementering kan brukes som en Stable (Last-In-First-Out) eller a (Først inn først ut).

2. API på et øyeblikk

For hver operasjon har vi i utgangspunktet to alternativer.

Den første gruppen består av metoder som kaster unntak hvis operasjonen mislykkes. Den andre gruppen returnerer en status eller en verdi:

OperasjonMetodeMetodekasting Unntak
Innsetting fra hodetofferFirst (e)addFirst (e)
Fjerning fra hodetpollFirst ()removeFirst ()
Henting fra hodetpeekFirst ()getFirst ()
Innsetting fra haleofferLast (e)addLast (e)
Fjerning fra halenpollLast ()removeLast ()
Henting fra halenpeekLast ()getLast ()

3. Bruke metoder

La oss se på noen få enkle eksempler på hvordan vi kan bruke ArrayDeque.

3.1. Ved hjelp av ArrayDeque som en Stable

Vi begynner med et eksempel på hvordan vi kan behandle klassen som en Stable - og skyv et element:

@Test offentlig ugyldig nårPush_addsAtFirst () {Deque stack = new ArrayDeque (); stack.push ("første"); stack.push ("andre"); assertEquals ("andre", stack.getFirst ()); } 

La oss også se hvordan vi kan poppe et element fra ArrayDeque - når den brukes som en stabel:

@Test public void whenPop_removesLast () {Deque stack = new ArrayDeque (); stack.push ("første"); stack.push ("andre"); assertEquals ("andre", stack.pop ()); } 

De pop metoden kaster NoSuchElementException når en bunke er tom.

3.2. Ved hjelp av ArrayDeque som en

La oss nå starte med et enkelt eksempel som viser hvordan vi kan tilby et element i en ArrayDeque - når det brukes som en enkel :

@Test offentlig ugyldig nårOffer_addsAtLast () {Deque kø = ny ArrayDeque (); kø.offer ("første"); kø.offer ("andre"); assertEquals ("andre", queue.getLast ()); } 

Og la oss se hvordan vi kan avstemme et element fra en ArrayDeque, også når den brukes som en :

@Test offentlig ugyldig nårPoll_removesFirst () {Deque kø = ny ArrayDeque (); kø.offer ("første"); kø.offer ("andre"); assertEquals ("første", queue.poll ()); } 

De avstemming metoden returnerer a null verdi hvis en kø er tom.

4. Hvordan er det? ArrayDeque Implementert

Under panseret, den ArrayDeque støttes av en matrise som dobler størrelsen når den blir fylt.

Opprinnelig initialiseres matrisen med størrelsen 16. Den er implementert som en kø med to ender der den har to pekere, nemlig et hode og en hale.

La oss se denne logikken i aksjon - på et høyt nivå.

4.1. ArrayDeque som Stack

Som det kan sees, når en bruker legger til et element ved hjelp av trykk metode, beveger den hodepekeren en.

Når vi spretter et element, setter det elementet i hodeposisjonen som null slik at elementet kan samles opp søppel, og deretter beveger hodepekeren en etter.

4.2. ArrayDeque som en

Når vi legger til et element ved hjelp av by på metode, beveger den halepekeren en.

Mens brukeren undersøker et element, setter det elementet i hodeposisjonen til null slik at elementet kan samles opp, og deretter flytter hodepekeren.

4.3. Merknader om ArrayDeque

Til slutt, noen flere notater som er verdt å forstå og huske på denne spesielle implementeringen:

  • Det er ikke trådsikkert
  • Nullelementer aksepteres ikke
  • Fungerer betydelig raskere enn den synkroniserte Stable
  • Er en raskere kø enn LinkedList på grunn av bedre referanselokalitet
  • De fleste operasjoner har avskrevet konstant tidskompleksitet
  • An Iterator returnert av en ArrayDeque er feilrask
  • ArrayDeque dobler automatisk størrelsen på en matrise når hodet og halen peker møter hverandre mens du legger til et element

5. Konklusjon

I denne korte artikkelen illustrerte vi bruken av metoder i ArrayDeque.

Implementeringen av alle disse eksemplene finnes i GitHub-prosjektet; dette er et Maven-basert prosjekt, så det skal være enkelt å importere og kjøre som det er.


$config[zx-auto] not found$config[zx-overlay] not found