Inleiding tot de Java ArrayDeque
1. Overzicht
In deze tutorial laten we zien hoe je de Java's kunt gebruiken ArrayDeque class - wat een implementatie is van Deque koppel.
Een ArrayDeque (ook bekend als een "Array Double Ended Queue", uitgesproken als "ArrayDeck") is een speciaal soort kweekbare array waarmee we een element aan beide kanten kunnen toevoegen of verwijderen.
Een ArrayDeque implementatie kan worden gebruikt als een Stapel (Last-In-First-Out) of een Wachtrij(Als eerste erin, als eerste eruit).
2. De API in één oogopslag
Voor elke operatie hebben we in principe twee opties.
De eerste groep bestaat uit methoden die een uitzondering genereren als de bewerking mislukt. De andere groep retourneert een status of een waarde:
| Operatie | Methode | Methode gooien uitzondering |
| Inbrengen vanuit het hoofd | offerFirst (e) | addFirst (e) |
| Verwijdering van hoofd | pollFirst () | removeFirst () |
| Ophalen van hoofd | peekFirst () | getFirst () |
| Inbrengen vanaf de staart | offerLaatste (e) | addLast (e) |
| Verwijdering van de staart | pollLast () | removeLast () |
| Ophalen uit de staart | peekLast () | word laatste() |
3. Methoden gebruiken
Laten we eens kijken naar een paar eenvoudige voorbeelden van hoe we gebruik kunnen maken van de ArrayDeque.
3.1. Gebruik makend van ArrayDeque als een Stapel
We beginnen met een voorbeeld van hoe we de klas kunnen behandelen als een Stapel - en druk op een element:
@Test openbare leegte whenPush_addsAtFirst () {Deque stack = nieuwe ArrayDeque (); stack.push ("eerste"); stack.push ("tweede"); assertEquals ("second", stack.getFirst ()); } Laten we ook kijken hoe we een element uit de ArrayDeque - bij gebruik als stapel:
@Test openbare leegte whenPop_removesLast () {Deque stack = nieuwe ArrayDeque (); stack.push ("eerste"); stack.push ("tweede"); assertEquals ("second", stack.pop ()); } De knal methode gooit NoSuchElementException als een stapel leeg is.
3.2. Gebruik makend van ArrayDeque als een Wachtrij
Laten we nu beginnen met een eenvoudig voorbeeld dat laat zien hoe we een element in een ArrayDeque - bij gebruik als een simpele Wachtrij:
@Test openbare leegte whenOffer_addsAtLast () {Deque wachtrij = nieuwe ArrayDeque (); queue.offer ("eerste"); queue.offer ("tweede"); assertEquals ("second", queue.getLast ()); } En laten we eens kijken hoe we een element uit een ArrayDeque, ook bij gebruik als Wachtrij:
@Test openbare leegte whenPoll_removesFirst () {Deque wachtrij = nieuwe ArrayDeque (); queue.offer ("eerste"); queue.offer ("tweede"); assertEquals ("eerste", queue.poll ()); } De poll methode retourneert een nul waarde als een wachtrij leeg is.
4. Hoe gaat het ArrayDeque Geïmplementeerd
Onder de motorkap, de ArrayDeque wordt ondersteund door een array die de grootte verdubbelt wanneer deze wordt gevuld.
Aanvankelijk wordt de array geïnitialiseerd met een grootte van 16. Het is geïmplementeerd als een wachtrij met twee uiteinden waar het twee verwijzingen bevat, namelijk een kop en een staart.
Laten we deze logica in actie zien - op een hoog niveau.
4.1. ArrayDeque als Stack
Zoals te zien is, wanneer een gebruiker een element toevoegt met behulp van de Duwen methode, verplaatst het de hoofdwijzer met één.
Wanneer we een element poppen, stelt het het element op de koppositie in als nul dus het element kan als vuilnis worden verzameld, en beweegt dan de hoofdwijzer één keer terug.
4.2. ArrayDeque als een Wachtrij
Wanneer we een element toevoegen met de aanbod methode, verplaatst het de staartwijzer met één.
Wanneer een gebruiker een element peilt, wordt het element op de head-positie op nul gezet, zodat het element kan worden opgehaald, en wordt vervolgens de head-pointer verplaatst.
4.3. Opmerkingen over ArrayDeque
Tot slot nog een paar opmerkingen die het waard zijn om te begrijpen en te onthouden over deze specifieke implementatie:
- Het is niet draadveilig
- Null-elementen worden niet geaccepteerd
- Werkt aanzienlijk sneller dan de gesynchroniseerde Stapel
- Is een snellere wachtrij dan LinkedList vanwege de betere referentielocatie
- Bij de meeste operaties is de complexiteit in constante tijd afgeschreven
- Een Iterator geretourneerd door een ArrayDeque is faalvast
- ArrayDeque verdubbelt automatisch de grootte van een array wanneer de kop- en staartaanwijzer elkaar ontmoeten tijdens het toevoegen van een element
5. Conclusie
In dit korte artikel hebben we het gebruik van methoden in ArrayDeque.
De implementatie van al deze voorbeelden is te vinden in het GitHub-project; dit is een op Maven gebaseerd project, dus het zou gemakkelijk moeten kunnen worden geïmporteerd en uitgevoerd zoals het is.
