Queue et deque

L'ordre de traitement dans les queues

Ce site ne sera plus alimenté de contenu après août 2014. Tous les nouveaux articles seront redigés pour www.waitingforcode.com

Quotidiennement on est confrontés à des queues. On fait la queue à la poste pour réceptionner un colis. On attend dans la queue avant de payer nos courses au supermarché. Cette notion a été transporté dans le monde informatique.

Queue en informatique

Queue (file en français) est une structure de données. Comme dans chaque file d'attente, les premiers éléments entrants sont traités d'abord. Ce principe est appelé First In, First Out (FIFO - en français premier arrivé, premier sorti).

Un autre principe pouvant être appliqué aux queues s'appelle Last In, First Out (LIFO - en français dernier arrivé, premier sorti). Les derniers éléments rajoutés à la file sont traités en premier.

Les files peuvent subir des opérations de validation (si contient d'éléments), d'ajout ou de suppression d'éléments.

Queue en Java

Les queues sont définis en Java avec l'interface java.util.Queue. Ses méthodes permettent d'effectuer toutes les opérations définies au premier paragraphe. On peut donc :
- ajouter un élément dans la queue : add(), offer()
- supprimer un élément de la queue : remove(), poll()
- récupérer le premier élément de la queue : peek()
- vérifier si la queue est vide : isEmpty()

Il est important de noter que les deux méthodes de suppression retournent également l'élément à supprimer.

Plusieurs classes non abstraites implémentent cette interface :
- java.util.concurrent.ArrayBlockingQueue<E> : la classe implémentant le tableau selon le principe FIFO. La capacité de cette queue est définie au moment de son initialisation. Elle ne peut pas croitre dynamiquement.
- java.util.ArrayDeque<E> :
- java.util.concurrent.ConcurrentLinkedQueue<E> : la classe implémente le principe FIFO. Sa capacité n'est pas fixée. Elle est thread-safe ce qui veut dire qu'elle est idéale pour des situations où plusieurs threads vont partager l'accès à cette collection.
- java.util.concurrent.DelayQueue<E extends Delayed> : la queue qui contient les éléments qui implémentent l'interface java.util.concurrent.Delayed. Les éléments périmés sont supprimés en ordre d'expiration descendant (des expirations plus ancienness aux plus récentes).
- java.util.concurrent.LinkedBlockingDeque<E> :
- java.util.LinkedList<E> : l'implémentation non thread-safe selon le principe FIFO.
- java.util.PriorityQueue<E> : la queue permettant de manipuler les éléments en fonctions de leurs priorités de traitement. La détection des priorités se fait avec les implémentations de l'interface java.lang.Comparable<T> ou java.util.Comparator<T>. L'instance de cette dernière peut être fournie dans un des constructeurs.
- java.util.concurrent.PriorityBlockingQueue<E> : tout comme PriorityQueue, cette queue se base sur la priorisation des traitements. En plus de cela, elle prend les fonctions spécifiques à BlockingQueue. Elle attend que la queue ne soit pas vide au moment de récupération d'un élément. Elle attend également qu'il y ait suffisament d'espace disponible pour rajouter un élément.
- java.util.concurrent.SynchronousQueue<E> : il s'agit de la queue qui permet l'accès concurrentiel aux plusieurs threads. Si un thread tente de supprimer un élément de la queue, un autre thread ne peut pas récupérer le premier élément de la queue tant que la suppression n'est pas terminée. Et inversement, la suppression ne peut pas être effectuée tant que l'ajout d'un élément ne soit pas terminée.

Passons maintenant à quelques exemples d'implémentations des queues.

ConcurrentLinkedQueue en Java

Comme on a déjà mentionné, ConcurrentLinedQueue est thread safe. Elle possède donc des mécanismes internes qui parmettent de gérer l'accès concurrentiel. Dans notre exemple on utilisera donc plusieurs threads qui vonte tenter de manipuler la queue. Certains threads seront des lecteurs (récupération des données) tandis que d'autres s'occuperont de rajouter des éléments à la queue :

afficher le code

Sur l'écran on verra alors :

afficher le code

LinkedList en Java

L'exemple va utiliser les méthodes de l'interface java.util.Deque qui permet de retrouver soit les premiers (pollFirst()), soit les derniers (pollLast()) éléments de la queue :

afficher le code

Et voici le résultat :

First element is (peek) A
First element is (pool) A
First element is (poll) B
Last element is (poll) F
Last element is (poll) E

Dans cet exemple on a vu l'utilisation de l'interface Deque. En la traduisant, on peut dire qu'il s'agit d'une queue à deux bouts (double-ended queue, à prononcer deck). Cela veut dire que l'on peut effectuer les opérations aussi bien au début qu'à la fin de la queue. On pouvait voir cela dans l'exemple avec les méthodes pollLast() pour la fin ou poll() pour le début.

PriorityQueue en Java

Pour illustrer la queue des priorités (PriorityQueue) on utilisera la même formule que dans le paragraphe précédent. Cependant, les lettres ne seront pas rajoutés en ordre alphabétique. Malgré cela, la méthode poll() retournera toujours le premier élément en ordre naturel (alphabétique). L'exemple utilisera donc le tri selon l'interface Comparable :

afficher le code

Et voici le résultat sur l'écran :

First element is (peek) A
First element is (poll) A
First element is (poll) B
First element is (poll) C
First element is (poll) D
Bartosz KONIECZNY Concurrence

Une question ? Une remarque ?

*

*

Moi

Développeur d'applications Internet et journaliste passionné par l'adjectif français. Un aigle polonais orienté vers la progression, volant très haut et écoutant du zouk après les matches du foot français.

Vous appréciez mon travail ?

Pour contribuer au développement de ce site, ou pour remercier pour des articles rédigés, vous pouvez faire un don.

Un conseil CSS

Comment centrer verticalement les inputs type radio et checkbox ?

L'alignement vertical des inputs radio et checkbox peut se faire avec la propriété CSS, vertical-align. Par exemple :

<input type="radio" name="typeUser" id="pro-1" style="vertical-align:top;"/><label for="pro-1">Professionnel</label>