Introduction à Java ArrayDeque

1. Vue d'ensemble

Dans ce didacticiel, nous montrerons comment utiliser la classe ArrayDeque de Java - qui est une implémentation de l' interface Deque .

Un ArrayDeque (également connu sous le nom de «Array Double Ended Queue», prononcé comme «ArrayDeck») est un type spécial de tableau évolutif qui nous permet d'ajouter ou de supprimer un élément des deux côtés.

Une implémentation ArrayDeque peut être utilisée comme une pile (dernier entré, premier sorti) ou une file d'attente (premier entré, premier sorti).

2. L'API en un coup d'œil

Pour chaque opération, nous avons essentiellement deux options.

Le premier groupe se compose de méthodes qui lèvent une exception si l'opération échoue. L'autre groupe renvoie un statut ou une valeur:

Opération Méthode Exception de lancement de méthode
Insertion depuis la tête offerFirst (e) addFirst (e)
Retrait de la tête pollFirst () removeFirst ()
Récupération de la tête peekFirst () getFirst ()
Insertion depuis la queue offerLast (e) addLast (e)
Retrait de la queue pollLast () removeLast ()
Récupération de la queue peekLast () getLast ()

3. Utilisation de méthodes

Examinons quelques exemples simples de la façon dont nous pouvons utiliser ArrayDeque .

3.1. Utilisation d' ArrayDeque comme pile

Nous allons commencer par un exemple de la façon dont nous pouvons traiter la classe comme une pile - et pousser un élément:

@Test public void whenPush_addsAtFirst() { Deque stack = new ArrayDeque(); stack.push("first"); stack.push("second"); assertEquals("second", stack.getFirst()); } 

Voyons également comment nous pouvons faire apparaître un élément de ArrayDeque - lorsqu'il est utilisé comme pile:

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

La méthode pop lève NoSuchElementException lorsqu'une pile est vide.

3.2. Utiliser ArrayDeque comme file d'attente

Commençons maintenant par un exemple simple montrant comment nous pouvons offrir un élément dans un ArrayDeque - lorsqu'il est utilisé comme une simple file d'attente :

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

Et voyons comment nous pouvons interroger un élément d'un ArrayDeque , également lorsqu'il est utilisé comme file d'attente :

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

La méthode poll renvoie une valeur nulle si une file d'attente est vide.

4. Comment ArrayDeque est-il implémenté?

Sous le capot, le ArrayDeque est soutenu par un tableau qui double sa taille lorsqu'il est rempli.

Initialement, le tableau est initialisé avec une taille de 16. Il est implémenté comme une file d'attente à deux extrémités où il maintient deux pointeurs à savoir une tête et une queue.

Voyons cette logique en action - à un niveau élevé.

4.1. ArrayDeque en tant que pile

Comme on peut le voir, lorsqu'un utilisateur ajoute un élément à l'aide de la méthode push , il déplace le pointeur de tête d'une unité.

Lorsque nous sautons un élément, il définit l'élément à la position de la tête comme nul afin que l'élément puisse être récupéré, puis recule le pointeur de tête de un.

4.2. ArrayDeque en tant que file d'attente

Lorsque nous ajoutons un élément à l'aide de la méthode offer , il déplace le pointeur de queue d'une unité.

Alors que lorsque l'utilisateur interroge un élément, il définit l'élément à la position de la tête sur null afin que l'élément puisse être récupéré, puis déplace le pointeur de la tête.

4.3. Remarques sur ArrayDeque

Enfin, quelques notes supplémentaires à comprendre et à retenir sur cette implémentation particulière:

  • Ce n'est pas thread-safe
  • Les éléments nuls ne sont pas acceptés
  • Fonctionne beaucoup plus rapidement que la pile synchronisée
  • Est une file d'attente plus rapide que LinkedList en raison de la meilleure localité de référence
  • La plupart des opérations ont amorti la complexité en temps constant
  • Un Iterator renvoyé par un ArrayDeque est rapide
  • ArrayDeque double automatiquement la taille d'un tableau lorsque le pointeur de tête et de queue se rencontre lors de l'ajout d'un élément

5. Conclusion

Dans ce court article, nous avons illustré l'utilisation des méthodes dans ArrayDeque .

L'implémentation de tous ces exemples peut être trouvée dans le projet GitHub; il s'agit d'un projet basé sur Maven, il devrait donc être facile à importer et à exécuter tel quel.