Bevezetés a Java ArrayDeque-be

1. Áttekintés

Ebben az oktatóanyagban bemutatjuk a Java használatát ArrayDeque osztály - ami a Deque felület.

An ArrayDeque (más néven „Array Double Ended Queue”, kiejtve „ArrayDeck” néven) egy speciális fajta növekvő tömb, amely lehetővé teszi számunkra, hogy mindkét oldalról hozzáadjunk vagy eltávolítsunk egy elemet.

An ArrayDeque megvalósítás használható a Kazal (Last-In-First-Out) vagy a Sor(Első-be-első-kimenet).

2. Az API áttekintése

Minden művelethez alapvetően két lehetőségünk van.

Az első csoport olyan módszerekből áll, amelyek kivételt jelentenek, ha a művelet nem sikerül. A másik csoport állapotot vagy értéket ad vissza:

MűveletMódszerMódszer dobás Kivétel
Beszúrás a fejbőlofferFirst (e)addFirst (e)
Eltávolítás a fejbőlpollFirst ()removeFirst ()
Visszaállítás a fejbőlpeekFirst ()getFirst ()
Beszúrás a farokbólofferLast (e)addLast (e)
Eltávolítás a farokbólpollLast ()removeLast ()
Visszaállítás a farokbólpeekLast ()getLast ()

3. A módszerek használata

Nézzünk meg néhány egyszerű példát arra, hogyan használhatjuk a ArrayDeque.

3.1. Használata ArrayDeque mint a Kazal

Kezdjük egy példával arra, hogyan kezelhetjük az osztályt a-ként Kazal - és nyomjon egy elemet:

@Test public void whenPush_addsAtFirst () {Deque stack = new ArrayDeque (); verem.push ("első"); verem.push ("második"); assertEquals ("második", stack.getFirst ()); } 

Lássuk azt is, hogyan tudunk egy elemet kibontani a ArrayDeque - veremként használva:

@Test public void whenPop_removesLast () {Deque stack = new ArrayDeque (); stack.push ("első"); verem.push ("második"); assertEquals ("második", stack.pop ()); } 

A pop módszer dob NoSuchElementException amikor a verem üres.

3.2. Használata ArrayDeque mint a Sor

Kezdjük egy egyszerű példával, amely bemutatja, hogyan kínálhatunk egy elemet egy ArrayDeque - egyszerűként használva Sor:

@Test public void whenOffer_addsAtLast () {Deque queue = new ArrayDeque (); queue.ferfer ("első"); queue.ferfer ("második"); assertEquals ("második", queue.getLast ()); } 

És nézzük meg, hogyan kérdezhetünk le egy elemet egy ArrayDeque, akkor is, ha a Sor:

@Test public void whenPoll_removesFirst () {Deque queue = new ArrayDeque (); queue.ferfer ("első"); queue.ferfer ("második"); assertEquals ("első", queue.poll ()); } 

A közvélemény kutatás metódus a nulla érték, ha egy sor üres.

4. Hogy van ArrayDeque Megvalósult

A motorháztető alatt a ArrayDeque egy tömb támogatja, amely megduplázza a méretét, amikor kitöltődik.

Kezdetben a tömböt 16-os méretben inicializálják. Kétvégű sorként valósítják meg, ahol két mutatót tart fenn, nevezetesen egy fejet és egy farokot.

Lássuk ezt a logikát működésben - magas szinten.

4.1. ArrayDeque mint Verem

Amint látható, amikor a felhasználó hozzáad egy elemet a nyom módszerrel eggyel mozgatja a fejmutatót.

Amikor felpattanunk egy elemet, akkor az elemet a fej helyzetében as értékként állítja be nulla így az elem szemétgyűjtés lehet, majd eggyel visszahúzza a fejmutatót.

4.2. ArrayDeque mint a Sor

Amikor hozzáadunk egy elemet a ajánlat módszerrel eggyel mozgatja a farokmutatót.

Míg amikor a felhasználó megkérdez egy elemet, akkor az elemet a fej helyzetében nullára állítja, így az elem szemetet gyűjthet, majd elmozdítja a fej mutatóját.

4.3. Megjegyzések ArrayDeque

Végül még néhány megjegyzés, amelyet érdemes megérteni és emlékezni erre a konkrét megvalósításra:

  • Ez nem szálkás
  • Semmi elemet nem fogadunk el
  • Jelentősen gyorsabban működik, mint a szinkronizált Kazal
  • Gyorsabb a sor, mint LinkedList a jobb referencia lokalitás miatt
  • A legtöbb művelet állandó időbeli bonyolultságot amortizált
  • An Iterátor visszaadta egy ArrayDeque hibátlan
  • ArrayDeque automatikusan megduplázza a tömb méretét, ha a fej és a farokmutató találkozik egymással, miközben hozzáad egy elemet

5. Következtetés

Ebben a rövid cikkben bemutattuk a módszerek használatát a ArrayDeque.

Mindezen példák megvalósítása megtalálható a GitHub projektben; ez egy Maven-alapú projekt, ezért könnyen importálhatónak és futtathatónak kell lennie.