Une file d'attente est un autre type de structure de données linéaire utilisée pour stocker des éléments comme n'importe quelle autre structure de données, mais d'une manière particulière. En termes simples, nous pouvons dire que la file d'attente est un type de structure de données dans le langage de programmation Java qui stocke des éléments du même type. Les composants d'une file d'attente sont stockés selon un comportement FIFO (First In, First Out). Il y a deux extrémités dans la file d'attente, c'est-à-dire avant et arrière. La file d'attente a deux extrémités : avant et arrière.

La figure suivante décrit parfaitement la propriété FIFO (First In, First Out) de la file d'attente Java.

Comme expliqué dans l'image précédente, nous pouvons voir que la file d'attente est une structure de données linéaire avec deux terminaux, c'est-à-dire le début (avant) et la fin (arrière). Les composants sont ajoutés à l’intérieur de la file d’attente depuis l’extrémité arrière de la file d’attente et les composants sont extraits depuis l’extrémité avant de la file d’attente.

La file d'attente est une interface dans le Java qui appartient au package Java.util. Il étend également l'interface Collection.

La représentation générique de l'interface Java Queue est présentée ci-dessous :

while boucle java

 public interface Queue extends Collection 

Comme nous l'avons expliqué ci-dessus, la file d'attente est une interface, nous pouvons donc également dire que la file d'attente ne peut pas être instanciée car les interfaces ne peuvent pas être instanciées. Si un utilisateur souhaite implémenter la fonctionnalité de l'interface Queue en Java, il est alors obligatoire de disposer de classes solides qui implémentent l'interface Queue.

Dans le langage de programmation Java, deux classes différentes sont utilisées pour implémenter l'interface Queue. Ces cours sont :

exemple de code Java

• Liste liée
• File d'attente de priorité

Caractéristiques de la file d'attente Java

La file d'attente Java peut être considérée comme l'une des structures de données les plus importantes dans le monde de la programmation. Java Queue est attrayant en raison de ses propriétés. Les propriétés importantes de la structure de données Java Queue sont indiquées comme suit :

• Java Queue obéit à la méthode FIFO (First In, First Out). Il indique que les éléments sont inscrits dans la file d'attente à la fin et éliminés depuis le début.
• L'interface Java Queue donne toutes les règles et processus de l'interface Collection comme l'inclusion, la suppression, etc.
• Deux classes différentes sont utilisées pour implémenter l'interface Queue. Ces classes sont LinkedList et PriorityQueue.
• Outre ces deux-là, il existe une classe, Array Blocking Queue, utilisée pour implémenter l'interface Queue.
• Il existe deux types de files d'attente : les files d'attente illimitées et les files d'attente limitées. Les files d'attente qui font partie du package java.util sont connues sous le nom de files d'attente illimitées et les files d'attente limitées sont les files d'attente présentes dans le package java.util.concurrent.
• Le Deque ou (file d'attente à double extrémité) est également un type de file d'attente qui transporte l'inclusion et la suppression d'éléments aux deux extrémités.
• Le deque est également considéré comme thread-safe.
• Les files d'attente de blocage font également partie des types de files d'attente qui sont également thread-safe. Les files d'attente de blocage sont utilisées pour implémenter les requêtes producteur-consommateur.
• Les files d'attente de blocage ne prennent pas en charge les éléments nuls. Dans les files d'attente de blocage, si un travail similaire aux valeurs nulles est tenté, l'exception NullPointerException est également levée.

Implémentation de la file d'attente

Classes utilisées dans la mise en œuvre de Queue

Les classes utilisées pour implémenter les fonctionnalités de la file d'attente sont données comme suit :

• TableauDeque
• Liste liée
• File d'attente de priorité

Interfaces utilisées dans la mise en œuvre de Queue

Les interfaces Java sont également utilisées dans l'implémentation de la file d'attente Java. Les interfaces utilisées pour implémenter les fonctionnalités de la file d'attente sont données comme suit :

• De quoi
• File d'attente de blocage
• Blocage de Deque

Méthodes de classe de file d'attente Java

Dans la file d'attente Java, de nombreuses méthodes sont très couramment utilisées. L'interface Queue promeut différentes méthodes comme l'insertion, la suppression, le coup d'oeil, etc. Certaines opérations de la file d'attente Java déclenchent une exception alors que certaines de ces opérations renvoient une valeur particulière lorsque le programme est terminé.

Remarque - Dans Java SE 8, aucune modification n'est apportée à la collection de files d'attente Java. Ces méthodes définies ci-dessous sont préparées plus en détail dans les versions suivantes du langage de programmation Java. Par exemple, Java SE 9.

Différentes méthodes de la file d'attente Java sont définies ci-dessous :

Implémentation du tableau de files d'attente Java

L'implémentation d'une file d'attente n'est pas aussi simple qu'une implémentation de pile.

Pour implémenter la file d'attente à l'aide de tableaux, nous déclarons d'abord un tableau contenant n nombre d'éléments.

garniture javascript

Ensuite, nous définissons les opérations suivantes à effectuer dans cette file d'attente.

1) Mettre en file d'attente : Une opération pour insérer un élément dans la file d'attente est Enqueue (fonction queue Enqueue dans le programme). Pour insérer un élément à l’arrière, nous devons d’abord vérifier si la file d’attente est pleine. S'il est plein, nous ne pouvons pas insérer l'élément. Si arrière

2) Dequeue: L'opération pour supprimer un élément de la file d'attente est Dequeue (fonction queue Dequeue dans le programme). Tout d'abord, nous vérifions si la file d'attente est vide. Pour que l’opération de retrait de la file d’attente fonctionne, il doit y avoir au moins un élément dans la file d’attente.

3) Avant : Cette méthode renvoie le début de la file d'attente.

4) Affichage : Cette méthode parcourt la file d'attente et affiche les éléments de la file d'attente.

Java Queue Program

Le programme Java suivant illustre l'implémentation de Queue.

comment trier une liste de tableaux en Java

QueueArrayImplementation.java

 class Queue { private static int front, rear, capacity; private static int queue[]; Queue(int size) { front = rear = 0; capacity = size; queue = new int[capacity]; } // insert an element into the queue static void queueEnqueue(int item) { // check if the queue is full if (capacity == rear) { System.out.printf('
Queue is full
'); return; } // insert element at the rear else { queue[rear] = item; rear++; } return; } //remove an element from the queue static void queueDequeue() { // check if queue is empty if (front == rear) { System.out.printf('
Queue is empty
&apos;); return; } // shift elements to the right by one place uptil rear else { for (int i = 0; i <rear 0 4 - 1; i++) { queue[i]="queue[i" + 1]; } set queue[rear] to if (rear < capacity) decrement rear rear--; return; print queue elements static void queuedisplay() int i; (front="=" rear) system.out.printf('queue is empty
'); traverse front and for (i="front;" i rear; system.out.printf(' %d , ', queue[i]); of queuefront() system.out.printf('
front element the queue: %d', queue[front]); public class queuearrayimplementation main(string[] args) create a capacity q="new" queue(4); system.out.println('initial queue:'); q.queuedisplay(); inserting in q.queueenqueue(10); q.queueenqueue(30); q.queueenqueue(50); q.queueenqueue(70); system.out.println('queue after enqueue operation:'); q.queuefront(); insert q.queueenqueue(90); q.queuedequeue(); system.out.printf('
queue two dequeue operations:'); pre> <p> <strong>Output:</strong> </p> <pre> Initial Queue: Queue is Empty Queue after Enqueue Operation: 10 , 30 , 50 , 70 , Front Element of the queue: 10 Queue is full 10 , 30 , 50 , 70 , Queue after two dequeue operations: 50 , 70 , Front Element of the queue: 50 </pre> <h2>Java Queue Linked List Implementation</h2> <p>As we have implemented the Queue data structure using Arrays in the above program, we can also implement the Queue using Linked List.</p> <p>We will implement the same methods enqueue, dequeue, front, and display in this program. The difference is that we will be using the Linked List data structure instead of Array.</p> <p>The below program demonstrates the Linked List implementation of Queue in Java.</p> <p> <strong>QueueLLImplementation.java</strong> </p> <pre> class LinkedListQueue { private Node front, rear; private int queueSize; // queue size //linked list node private class Node { int data; Node next; } //default constructor - initially front &amp; rear are null; size=0; queue is empty public LinkedListQueue() { front = null; rear = null; queueSize = 0; } //check if the queue is empty public boolean isEmpty() { return (queueSize == 0); } //Remove item from the front of the queue. public int dequeue() { int data = front.data; front = front.next; if (isEmpty()) { rear = null; } queueSize--; System.out.println(&apos;Element &apos; + data+ &apos; removed from the queue&apos;); return data; } //Add data at the rear of the queue. public void enqueue(int data) { Node oldRear = rear; rear = new Node(); rear.data = data; rear.next = null; if (isEmpty()) { front = rear; } else { oldRear.next = rear; } queueSize++; System.out.println(&apos;Element &apos; + data+ &apos; added to the queue&apos;); } //print front and rear of the queue public void print_frontRear() { System.out.println(&apos;Front of the queue:&apos; + front.data + &apos; Rear of the queue:&apos; + rear.data); } } class QueueLLImplementation{ public static void main(String a[]){ LinkedListQueue queue = new LinkedListQueue(); queue.enqueue(6); queue.enqueue(3); queue.print_frontRear(); queue.enqueue(12); queue.enqueue(24); queue.dequeue(); queue.dequeue(); queue.enqueue(9); queue.print_frontRear(); } } </pre> <p> <strong>Output:</strong> </p> <pre> Element 6 added to the queue Element 3 added to the queue Front of the queue:6 Rear of the queue:3 Element 12 added to the queue Element 24 added to the queue Element 6 removed from the queue Element 3 removed from the queue Element 9 added to the queue Front of the queue:12 Rear of the queue:9 </pre> <hr></rear>

Implémentation de listes chaînées de file d'attente Java

Comme nous avons implémenté la structure de données Queue à l'aide de tableaux dans le programme ci-dessus, nous pouvons également implémenter la file d'attente à l'aide de Linked List.

Nous implémenterons les mêmes méthodes de mise en file d'attente, de retrait de la file d'attente, de front et d'affichage dans ce programme. La différence est que nous utiliserons la structure de données Linked List au lieu de Array.

Le programme ci-dessous démontre l'implémentation de liste chaînée de Queue en Java.

QueueLLImplementation.java

liste triée java

 class LinkedListQueue { private Node front, rear; private int queueSize; // queue size //linked list node private class Node { int data; Node next; } //default constructor - initially front & rear are null; size=0; queue is empty public LinkedListQueue() { front = null; rear = null; queueSize = 0; } //check if the queue is empty public boolean isEmpty() { return (queueSize == 0); } //Remove item from the front of the queue. public int dequeue() { int data = front.data; front = front.next; if (isEmpty()) { rear = null; } queueSize--; System.out.println('Element ' + data+ ' removed from the queue'); return data; } //Add data at the rear of the queue. public void enqueue(int data) { Node oldRear = rear; rear = new Node(); rear.data = data; rear.next = null; if (isEmpty()) { front = rear; } else { oldRear.next = rear; } queueSize++; System.out.println('Element ' + data+ ' added to the queue'); } //print front and rear of the queue public void print_frontRear() { System.out.println('Front of the queue:' + front.data + ' Rear of the queue:' + rear.data); } } class QueueLLImplementation{ public static void main(String a[]){ LinkedListQueue queue = new LinkedListQueue(); queue.enqueue(6); queue.enqueue(3); queue.print_frontRear(); queue.enqueue(12); queue.enqueue(24); queue.dequeue(); queue.dequeue(); queue.enqueue(9); queue.print_frontRear(); } } 

Sortir:

 Element 6 added to the queue Element 3 added to the queue Front of the queue:6 Rear of the queue:3 Element 12 added to the queue Element 24 added to the queue Element 6 removed from the queue Element 3 removed from the queue Element 9 added to the queue Front of the queue:12 Rear of the queue:9