File d'attente circulaire Java

L'article suivant fournit un aperçu de la file d'attente circulaire Java. Une file d'attente circulaire est une structure de données linéaire et les opérations sont effectuées de manière FIFO (First In First Out), tout comme une simple file d'attente. Dans la file d'attente circulaire, la dernière position est connectée à la première position en formant un cercle. On l'appelle également le Ring Buffer. Dans la structure de file d'attente simple, si l'arrière atteint la fin de la file d'attente, c'est-à-dire que la file d'attente devient pleine, il y a des chances que les espaces au début des éléments soient vides et ne puissent pas être utilisés. Cette limitation de la file d'attente est résolue par la file d'attente CIrculaire. Dans cette rubrique, nous allons découvrir la file d'attente circulaire Java.

Commencez votre cours de développement de logiciels libres

Développement Web, langages de programmation, tests de logiciels et autres

Syntaxe :

Vous trouverez ci-dessous la syntaxe de base de l'utilisation de la file d'attente circulaire dans le programme Java :

Comment créer une file d'attente circulaire en Java ainsi que son fonctionnement ?

Comprenons en détail la création et le fonctionnement de la file d'attente circulaire :

Les opérations de base effectuées sur la file d'attente circulaire sont indiquées ci-dessous :

1. Front : Il est utilisé pour pointer vers le premier élément de la file d'attente.
2. Arrière : Il permet de pointer vers le dernier élément de la file d'attente.
3. Enqueue(value): C'est une fonction qui permet d'insérer l'élément dans la file d'attente. Les éléments de la file d'attente sont insérés en position arrière.
4. Dequeue() : Cette fonction permet de supprimer l'élément de la Queue. En tant que nature fondamentale de la file d'attente, la suppression des éléments s'effectue depuis le début de la file d'attente.

Vous trouverez ci-dessous les étapes suivies lors de la création, de l'insertion ou de la suppression des éléments dans la file d'attente circulaire :

• Initialement, la valeur de l'avant et de l'arrière est fixée à -1.
• En opération de mise en file d'attente (valeur) :
• Si nous insérons le premier élément dans la file d'attente, l'avant et l'arrière sont définis sur 0.
• Lors de l'insertion du nouvel élément dans la file d'attente, l'arrière devient arrière + 1.
• Le nouvel élément est ajouté à la position de l'arrière.
• L'arrière est incrémenté de manière circulaire, c'est-à-dire que s'il atteint la fin et que la file d'attente est pleine, il pointe vers le début de la file d'attente.
• En opération de retrait de file d'attente :
• Tout d'abord, il est vérifié si la file d'attente est vide ou non. Moyenne de l'avant== arrière== -1, signifie que la file d'attente est vide, la suppression ne peut pas être effectuée.
• Si la file d'attente ne comporte qu'un seul élément, c'est-à-dire front == Rear, supprimez l'élément et définissez front == Rear == -1.
• S'il y a des éléments dans la file d'attente, la valeur indiquée par front est supprimée et augmente circulairement l'index de front de 1.

Les scénarios suivants doivent être gardés à l'esprit lorsque vous travaillez dans la file d'attente circulaire :

1. La file d'attente est pleine si avant = 0 et arrière = taille -1, ce qui signifie que l'avant pointe vers la première position et l'arrière vers la dernière. La file d'attente est donc pleine et aucune insertion ne peut avoir lieu.
2. La file d'attente est pleine si avant = arrière+1, ce qui signifie que si, après tant de suppressions, l'avant est en position 3 de la file d'attente et l'arrière après insertions de manière circulaire est en position 2, la liste est pleine et plus aucune insertion ne peut avoir lieu.
3. La file d'attente n'est pas pleine si front!= 0 et Rear = max-1, ce qui signifie qu'il y a des positions en début de file qui sont vides, donc des insertions peuvent avoir lieu.
4. Si arrière!= taille-1, alors la nouvelle valeur peut être insérée car l'arrière peut être incrémenté davantage à l'aide d'un mod(taille).

Exemples

Vous trouverez ci-dessous l'exemple montrant l'implémentation de Circular Queue dans le programme Java :

• Insérer des éléments dans la file d'attente
• Affichage des éléments de la file d'attente vide
• Insérer des éléments dans la file d'attente
• Supprimer des éléments de la file d'attente
• Insérer des éléments dans une file d'attente complète
• Affichage des éléments de la file d'attente ainsi que la position de l'avant et de l'arrière.

public class CirQueue {
// Defining the size of Circular Queue
int SIZE = 5;
int front, rear;
int queue[] = new int[SIZE];
//creating the constructor of the above class
CirQueue() {
front = -1;
rear = -1;
}
// Implementing the 2 scenarios to check if the queue is full or not
boolean isFullQueue() {
if (front == 0 && rear == SIZE - 1) {
return true;
}
if (front == rear + 1) {
return true;
}
return false;
}
// Check if the queue is empty or not
boolean isEmptyQueue() {
if (front == -1)
return true;
else
return false;
}
// Adding an element in the queue
void enQueue(int value) {
if (isFullQueue()) {
System.out.println("Sorry !! Queue is full.. No more elements could be inserted in it");
}
else {
// if there is no element in the queue
if (front == -1)
front = 0;
// incrementing the rear position in circular manner using modulo operator
rear = (rear + 1) % SIZE;
//placing the value at the rear position
queue[rear] = value;
System.out.println("Element " + value + " is inserted successfully");
}
}
// Deleting the element from the queue
void deQueue() {
int value;
// checking of the queue is empty or not
if (isEmptyQueue()) {
System.out.println("Sorry !!The Queue is empty.. ");
} else {
value = queue[front];
// if there is only one element in the queue
if (front == rear) {
front = -1;
rear = -1;
}
else {
// Incrementing the front in a circular manner
front = (front + 1) % SIZE;
}
}
}
// Displaying the elements of the Circular queue
void displayQueue() {
int i;
if (isEmptyQueue()) {
System.out.println("Sorry!! The Queue is Empty");
} else {
System.out.println("Position of Front:  " + front);
System.out.println("Below given are the elements of the Queue");
for (i = front; i != rear; i = (i + 1) % SIZE)
System.out.print(queue[i] + " ");
System.out.println(queue[i]);
System.out.println("Position of Rear: " + rear);
}
}
// Main function to drive the code
public static void main(String[] args) {
// creating the object of the class to call the methods
CirQueue que = new CirQueue();
// Queue is empty. No element is inserted as of now
que.deQueue();
que.enQueue(10);
que.enQueue(24);
que.enQueue(33);
que.enQueue(67);
que.enQueue(22);
que.displayQueue();
que.deQueue();
que.displayQueue();
que.enQueue(900);
que.displayQueue();
// Element cannot be inserted as the queue is full
que.enQueue(867);
que.deQueue();
que.displayQueue();
}
}

Sortie :

Vous trouverez ci-dessous la capture d'écran de la sortie après diverses insertions et suppressions sur la file d'attente circulaire :

Conclusion

La description ci-dessus explique clairement ce qu'est la file d'attente circulaire et comment elle fonctionne dans n'importe quel langage de programmation. La file d'attente circulaire a été introduite afin de résoudre la limitation de la file d'attente normale. Avant de travailler dessus, il est très important que le programmeur comprenne d'abord la file d'attente ainsi que son implémentation dans le programme réel.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!