Introduktion til Java ArrayDeque

1. Oversigt

I denne vejledning viser vi, hvordan du bruger Java'erne ArrayDeque klasse - som er en implementering af Deque interface.

En ArrayDeque (også kendt som en "Array Double Ended Queue", udtalt som "ArrayDeck") er en speciel slags et dyrkbart array, der giver os mulighed for at tilføje eller fjerne et element fra begge sider.

En ArrayDeque implementering kan bruges som en Stak (Last-In-First-Out) eller a (Først ind først ud).

2. Overblik over API'en

For hver operation har vi stort set to muligheder.

Den første gruppe består af metoder, der kaster undtagelse, hvis operationen mislykkes. Den anden gruppe returnerer en status eller en værdi:

OperationMetodeMetode til at kaste Undtagelse
Indsættelse fra hovedetofferFirst (e)addFirst (e)
Fjernelse fra hovedetpollFirst ()removeFirst ()
Hentning fra hovedetpeekFirst ()getFirst ()
Indsættelse fra halenofferLast (e)addLast (e)
Fjernelse fra halenpollLast ()removeLast ()
Hentning fra halenpeekLast ()getLast ()

3. Brug af metoder

Lad os se på et par enkle eksempler på, hvordan vi kan gøre brug af ArrayDeque.

3.1. Ved brug af ArrayDeque som en Stak

Vi starter med et eksempel på, hvordan vi kan behandle klassen som en Stak - og skub et element:

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

Lad os også se, hvordan vi kan poppe et element fra ArrayDeque - når den bruges som en stak:

@Test offentlig ugyldig nårPop_removesLast () {Deque stack = ny ArrayDeque (); stack.push ("første"); stack.push ("anden"); assertEquals ("anden", stack.pop ()); } 

Det pop metoden kaster NoSuchElementException når en stak er tom.

3.2. Ved brug af ArrayDeque som en

Lad os nu starte med et simpelt eksempel, der viser, hvordan vi kan tilbyde et element i et ArrayDeque - når det bruges som en simpel :

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

Og lad os se, hvordan vi kan afstemme et element fra en ArrayDeque, også når det bruges som en :

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

Det afstemning metode returnerer a nul værdi, hvis en kø er tom.

4. Hvordan er det? ArrayDeque Implementeret

Under hætten, den ArrayDeque er bakket op af en matrix, der fordobler dens størrelse, når den bliver fyldt.

Oprindeligt initialiseres arrayet med en størrelse på 16. Det implementeres som en kø med dobbelt ende, hvor den opretholder to markører, nemlig et hoved og en hale.

Lad os se denne logik i aktion - på et højt niveau.

4.1. ArrayDeque som stak

Som det kan ses, når en bruger tilføjer et element ved hjælp af skubbe metode flytter den hovedmarkøren en.

Når vi popper et element, indstiller det elementet i hovedpositionen som nul så elementet kunne blive indsamlet skrald, og derefter flytte hovedmarkøren tilbage en.

4.2. ArrayDeque som en

Når vi tilføjer et element ved hjælp af tilbud metode, flytter den halemarkøren en.

Mens brugeren afstemmer et element, indstiller det elementet i hovedpositionen til null, så elementet kan blive indsamlet skrald, og derefter flytter hovedmarkøren.

4.3. Bemærkninger om ArrayDeque

Endelig et par flere noter, der er værd at forstå og huske på denne særlige implementering:

  • Det er ikke trådsikkert
  • Nul elementer accepteres ikke
  • Fungerer betydeligt hurtigere end den synkroniserede Stak
  • Er en hurtigere kø end LinkedList på grund af den bedre referencelokalitet
  • De fleste operationer har afskrevet konstant tidskompleksitet
  • En Iterator returneret af en ArrayDeque er fail-fast
  • ArrayDeque fordobler automatisk størrelsen på en matrix, når hoved- og halemarkøren møder hinanden, mens der tilføjes et element

5. Konklusion

I denne korte artikel illustrerede vi brugen af ​​metoder i ArrayDeque.

Implementeringen af ​​alle disse eksempler findes i GitHub-projektet; dette er et Maven-baseret projekt, så det skal være let at importere og køre som det er.