Java Language
Files d'attente et deques

L'utilisation de PriorityQueue

PriorityQueue est une structure de données. Comme SortedSet , PriorityQueue trie également ses éléments en fonction de leurs priorités. Les éléments, qui ont une priorité plus élevée, viennent en premier. Le type de PriorityQueue doit implémenter comparable interface comparable ou de comparator , dont les méthodes déterminent les priorités des éléments de la structure de données.

//The type of the PriorityQueue is Integer.
PriorityQueue<Integer> queue = new PriorityQueue<Integer>();

//The elements are added to the PriorityQueue
queue.addAll( Arrays.asList( 9, 2, 3, 1, 3, 8 ) );

//The PriorityQueue sorts the elements by using compareTo method of the Integer Class
//The head of this queue is the least element with respect to the specified ordering
System.out.println( queue );  //The Output: [1, 2, 3, 9, 3, 8]
queue.remove();
System.out.println( queue );  //The Output: [2, 3, 3, 9, 8]
queue.remove();
System.out.println( queue );  //The Output: [3, 8, 3, 9]
queue.remove();
System.out.println( queue );  //The Output: [3, 8, 9]
queue.remove();
System.out.println( queue );  //The Output: [8, 9]
queue.remove();
System.out.println( queue );  //The Output: [9]
queue.remove();
System.out.println( queue );  //The Output: []

LinkedList en tant que file FIFO

La classe java.util.LinkedList , lors de l'implémentation de java.util.List est une implémentation polyvalente de l'interface java.util.Queue fonctionnant également selon le principe FIFO (First In, First Out) .

Dans l'exemple ci-dessous, avec la méthode offer() , les éléments sont insérés dans la LinkedList . Cette opération d'insertion s'appelle la mise en enqueue . Dans le while en boucle ci - dessous, les éléments sont retirés de la Queue d' Queue sur la base FIFO. Cette opération s'appelle dequeue .

Queue<String> queue = new LinkedList<String>();

queue.offer( "first element" );
queue.offer( "second element" );
queue.offer( "third element" );
queue.offer( "fourth. element" );
queue.offer( "fifth. element" );

while ( !queue.isEmpty() ) {
  System.out.println( queue.poll() );
}

La sortie de ce code est

first element
second element
third element
fourth element
fifth element

Comme on le voit dans la sortie, le premier élément inséré "premier élément" est supprimé en premier lieu, "deuxième élément" est supprimé à la deuxième place, etc.

Piles

Qu'est-ce qu'un Stack?

En Java, Stacks est une structure de données LIFO (Last In, First Out) pour les objets.

API de pile

Java contient une API Stack avec les méthodes suivantes

Stack()            //Creates an empty Stack
isEmpty()          //Is the Stack Empty?             Return Type: Boolean
push(Item item)    //push an item onto the stack
pop()              //removes item from top of stack  Return Type: Item
size()             //returns # of items in stack     Return Type: Int

Exemple

import java.util.*;

public class StackExample {

   public static void main(String args[]) {
      Stack st = new Stack();
      System.out.println("stack: " + st);
      
      st.push(10);
      System.out.println("10 was pushed to the stack");
      System.out.println("stack: " + st);
      
      st.push(15);
      System.out.println("15 was pushed to the stack");
      System.out.println("stack: " + st);
      
      st.push(80);
      System.out.println("80 was pushed to the stack");
      System.out.println("stack: " + st);
      
      st.pop();
      System.out.println("80 was popped from the stack");
      System.out.println("stack: " + st);
      
      st.pop();
      System.out.println("15 was popped from the stack");
      System.out.println("stack: " + st);
      
      st.pop();
      System.out.println("10 was popped from the stack");
      System.out.println("stack: " + st);
      
     if(st.isEmpty())
      {
         System.out.println("empty stack");
      }
   }
}

Ce retourne:

stack: []
10 was pushed to the stack
stack: [10]
15 was pushed to the stack
stack: [10, 15]
80 was pushed to the stack
stack: [10, 15, 80]
80 was popped from the stack
stack: [10, 15]
15 was popped from the stack
stack: [10]
10 was popped from the stack
stack: []
empty stack

BlockingQueue

Une BlockingQueue est une interface, qui est une file d'attente qui se bloque lorsque vous essayez de retirer la file d'attente de celle-ci et que la file d'attente est vide ou si vous essayez de mettre les éléments en file d'attente et que la file d'attente est déjà pleine. Un thread essayant de se libérer de la file d'attente vide est bloqué jusqu'à ce qu'un autre thread insère un élément dans la file d'attente. Un thread qui tente de mettre en file d'attente un élément dans une file d'attente complète est bloqué jusqu'à ce qu'un autre thread crée de l'espace dans la file d'attente, soit en retirant un ou plusieurs éléments ou en effaçant complètement la file d'attente.

Les méthodes de BlockingQueue se présentent sous quatre formes, avec différentes manières de gérer les opérations qui ne peuvent pas être satisfaites immédiatement, mais qui peuvent être satisfaites à l’avenir: on jette une exception, la seconde renvoie une valeur spéciale (nulle ou fausse selon opération), le troisième bloque indéfiniment le thread en cours jusqu’à ce que l’opération réussisse, et le quatrième ne bloque qu’une limite de temps maximale donnée avant d’abandonner.

Un BlockingQueue peut être limité ou non . Un BlockingQueue borné est un qui est initialisé avec une capacité initiale.

BlockingQueue<String> bQueue = new ArrayBlockingQueue<String>(2);

Tout appel à une méthode put () sera bloqué si la taille de la file d'attente est égale à la capacité initiale définie.

Une file d'attente illimitée est une file qui est initialisée sans capacité, en fait, par défaut, elle est initialisée avec Integer.MAX_VALUE.

Les implémentations courantes de BlockingQueue sont les suivantes:

1. ArrayBlockingQueue
2. LinkedBlockingQueue
3. PriorityBlockingQueue

Regardons maintenant un exemple de ArrayBlockingQueue :

BlockingQueue<String> bQueue = new ArrayBlockingQueue<>(2);
bQueue.put("This is entry 1");
System.out.println("Entry one done");
bQueue.put("This is entry 2");
System.out.println("Entry two done");
bQueue.put("This is entry 3");
System.out.println("Entry three done");

Cela va imprimer:

Entry one done
Entry two done

Et le thread sera bloqué après la deuxième sortie.

Interface de file d'attente

Les bases

Une Queue est une collection pour contenir des éléments avant le traitement. Les files d'attente ordonnent généralement, mais pas nécessairement, les éléments d'une manière FIFO (premier entré, premier sorti).

Head of the queue est l'élément qui serait supprimé par un appel à supprimer ou à interroger. Dans une file d'attente FIFO, tous les nouveaux éléments sont insérés en queue de file.

L'interface de file d'attente

public interface Queue<E> extends Collection<E> {
    boolean add(E e);

    boolean offer(E e);

    E remove();

    E poll();

    E element();

    E peek();
}

Chaque méthode de Queue existe sous deux formes:

• on lève une exception si l'opération échoue;
• other renvoie une valeur spéciale si l'opération échoue ( null ou false selon l'opération).

Deque

Un Deque est une "file d'attente double", ce qui signifie que des éléments peuvent être ajoutés au début ou à la fin de la file. La file d'attente seulement peut ajouter des éléments à la queue d'une file d'attente.

Le Deque hérite de l'interface Queue , ce qui signifie que les méthodes habituelles restent, mais l'interface Deque offre des méthodes supplémentaires pour être plus flexible avec une file d'attente. Les méthodes supplémentaires parlent d'elles-mêmes si vous savez comment fonctionne une file d'attente, puisque ces méthodes sont destinées à ajouter plus de flexibilité:

Bien entendu, les mêmes options pour les offer , les poll et les peek sont disponibles, mais elles ne fonctionnent pas avec des exceptions, mais plutôt avec des valeurs spéciales. Il ne sert à rien de montrer ce qu’ils font ici.

Ajouter et accéder aux éléments

Pour ajouter des éléments à la queue d'un Deque, vous appelez sa méthode add() . Vous pouvez également utiliser les addFirst() et addLast() , qui ajoutent des éléments à la tête et à la queue de deque.

Deque<String> dequeA = new LinkedList<>();

dequeA.add("element 1");      //add element at tail
dequeA.addFirst("element 2"); //add element at head
dequeA.addLast("element 3");  //add element at tail

Vous pouvez jeter un coup d’œil à l’élément en tête de la file sans retirer l’élément de la file d’attente. Cela se fait via la méthode element() . Vous pouvez également utiliser les getFirst() et getLast() , qui renvoient le premier et le dernier élément de Deque . Voici à quoi cela ressemble:

String firstElement0 = dequeA.element();
String firstElement1 = dequeA.getFirst();
String lastElement = dequeA.getLast();

Suppression d'éléments

Pour supprimer des éléments d'un duque, appelez les méthodes remove() , removeFirst() et removeLast() . Voici quelques exemples:

String firstElement = dequeA.remove();
String firstElement = dequeA.removeFirst();
String lastElement  = dequeA.removeLast();