Principe de mise en œuvre de la file d'attente Java
Le mot «file d'attente» est ce que les Britanniques appellent la «file d'attente». "Le plafond en ligne" au Royaume-Uni signifie se tenir debout. En informatique, une file d'attente est une structure de données, qui est un peu comme une pile, sauf que le premier élément de données inséré dans la file d'attente sera supprimé en premier, et dans la pile, le dernier élément de données inséré est supprimé en premier. La file d'attente fonctionne comme les rangées de personnes debout devant le cinéma: la première personne entrant dans l'affilié arrivera à la tête de l'équipe pour acheter des billets. La dernière personne qui fait la queue peut acheter des billets.
Les files d'attente sont également utilisées comme outils pour les programmeurs, comme les piles. Il peut également être utilisé pour simuler des environnements du monde réel, tels que la simulation des personnes en attente dans une banque, les avions en attente de décoller ou des paquets sur Internet attendent d'être transmis.
Dans le système d'exploitation informatique, diverses files d'attente fonctionnent tranquillement. Le travail d'impression attend l'impression dans la file d'attente d'impression. Lors de la saisie du clavier, il y a aussi une file d'attente qui stocke la saisie. De même, si une clé est exploitée à l'aide d'un traitement de texte et que l'ordinateur doit faire quelque chose d'autre temporairement, le contenu taraudé ne sera pas perdu, et il attendra dans la file d'attente jusqu'à ce que le traitement de texte ait le temps de le lire. La file d'attente est utilisée pour garantir que l'ordre de typage n'est pas modifié lorsqu'il est traité.
Opérations de base des files d'attente
Les deux opérations de base d'une file d'attente consistent à insérer (insérer) un élément de données, c'est-à-dire en mettant un élément de données dans la queue de la file d'attente, et l'autre supprime (supprimer) un élément de données, c'est-à-dire en supprimant l'élément de données à la tête de l'équipe. Ceci est similaire aux amateurs de films faisant la queue jusqu'à la fin de la ligne lorsqu'ils font la queue pour acheter des billets, puis arrivent à la tête de la ligne, puis quittent la file d'attente.
La dénomination des méthodes d'insertion et de suppression des éléments de données dans la pile est très standard, appelée Push and Pop. La méthode de la file d'attente n'a pas été nommée standardisée jusqu'à présent. "INSERT" peut être appelé put, ajouter ou enque, tandis que "supprimer" peut être appelé supprimer, obtenir ou désoliquer. La fin de l'élément de données d'insertion peut également être appelée arrière, queue ou fin. Le chef de l'équipe qui supprime l'élément de données peut également être appelé Head. Insérer, retirer, avant et arrière seront utilisés ci-dessous.
Insérer insérer la valeur dans la queue de la file d'attente, et la queue de la flèche de file d'attente est ajoutée pour pointer de la nouvelle élément de données.
Une fois l'élément de données supprimé, le chef de l'équipe est ajouté par un. Habituellement, lors de la mise en œuvre d'une file d'attente, l'élément de données supprimé sera enregistré en mémoire, mais il ne peut pas être accessible car la tête de la file d'attente a été déplacée vers sa prochaine position.
Contrairement au cas dans la pile, les éléments de données dans la file d'attente ne commencent pas toujours à l'indice 0 du tableau. Après avoir supprimé certains éléments de données, le pointeur d'en-tête pointe vers une position d'indice supérieure.
L'opération de vue renvoie la valeur de l'élément de données d'en-tête, mais ne supprime pas l'élément de données de l'équipe.
Si vous souhaitez supprimer un élément de données d'une file d'attente vide ou insérer un élément de données dans une file d'attente complète, l'application invitera un message d'erreur.
File d'attente en boucle
Lorsqu'un nouvel élément de données est inséré dans la file d'attente, la flèche arrière à la tête de l'équipe se déplace vers la large position de l'indice du tableau. Lors de la suppression des éléments de données, la queue du pointeur avant de la file d'attente se déplace également vers le haut. Cette conception peut être contraire à l'observation directe des gens, car lorsque les gens font la queue pour les billets de cinéma, la file d'attente avance toujours, et après que la personne devant elle achète le billet et quitte la file d'attente, les autres avancent. Après avoir supprimé un élément de données dans la file d'attente de l'ordinateur, vous pouvez également faire avancer tous les autres éléments de données, mais cela est très efficace. Au lieu de cela, nous conservons tous les éléments de données en position de la même chose à travers le mouvement des pointeurs de la tête et de la queue de la file d'attente.
Le problème avec cette conception est que le pointeur de queue se déplacera rapidement à la fin du tableau. Bien qu'il existe une unité d'élément de données vide au début du tableau, qui est l'emplacement de l'élément de données supprimé, mais comme le pointeur de queue ne peut plus se retirer, les nouveaux éléments de données ne peuvent pas être insérés. Que dois-je faire?
Traitement de recapation
Afin d'éviter que le problème de la file d'attente soit insatisfait mais ne peut pas insérer de nouveaux éléments de données, les pointeurs de la tête et de la queue peuvent être enveloppés au début du tableau. Ceci est la file d'attente de boucle (parfois aussi appelée "bague tampon").
Le processus d'enveloppement du pointeur: insérez suffisamment d'éléments de données dans la file d'attente pour faire pointer le pointeur de queue vers l'extrémité tardive du tableau. Supprimez quelques autres éléments de données à l'avant du tableau. Insérez maintenant un nouvel élément de données. Vous verrez que le pointeur de queue sera inversé de la fin à la position de départ. De nouveaux éléments de données seront insérés dans cet emplacement.
Insérez plus d'éléments de données. Le pointeur de queue se déplace vers le haut comme prévu. Notez qu'après le rembobinage du pointeur de queue, il est désormais en dessous du pointeur de tête, qui inverse la position initiale. Cela peut être appelé une "séquence cassée": les éléments de données dans la file d'attente sont présents dans deux séquences différentes du tableau.
Après avoir supprimé suffisamment d'éléments de données, le chef de l'équipe s'enroule également. À l'heure actuelle, le pointeur de file d'attente revient à l'état de position lors de l'exécution initiale, et le pointeur de tête est en dessous du pointeur de queue. Les éléments de données sont également restaurés en une seule séquence continue.
Code Java pour les files d'attente
Le programme queue.java crée une classe de file d'attente, qui a des méthodes INSERT (), reous (), peek (), iseempty () et size ().
pile de packages et file d'attente;
class queue {private int maxsize; privé long [] quearray; Front privé; arrière privé; Int nitems privé; Fitre publique (int s) {maxSize = s; Quearray = new Long [maxSize]; front = 0; arrière = -1; nitems = 0; } public void insert (long j) {if (arrière == maxSize-1) arrière = -1; Quearray [++ arrière] = J; Nitems ++; } public long retire () {long temp = quearray [front ++]; if (front == maxSize) front = 0; Nitems--; Tempère de retour; } public long peekfront () {return queaterray [front]; } public boolean isEmpty () {return (nitems == 0); } public boolean iffull () {return (nitems == maxSize); } public int size () {return nitems; }}La classe de file d'attente implémentée par le programme a non seulement des champs avant (tête) et arrière (tête de l'équipe), mais également le nombre d'éléments de données actuels dans la file d'attente: Nitems.
La condition préalable au fonctionnement de la méthode insert () est que la file d'attente n'est pas satisfaite. Cette méthode n'est pas affichée dans main (), mais la méthode insert () doit généralement être appelée d'abord, puis la méthode isull () doit être appelée après le retour false. (Une approche plus générale consiste à ajouter un jugement à la méthode insert () pour vérifier si la file d'attente est complète. Si un élément de données est inséré dans la file d'attente complète, une exception sera lancée.)
D'une manière générale, l'opération d'insertion consiste à ajouter un arrière (pointeur de queue d'équipe) et à insérer de nouvelles données à la position pointée par le pointeur de queue. Cependant, lorsque le pointeur arrière pointe vers le haut du tableau, c'est-à-dire la position MaxSize-1, il doit être remonté au bas du tableau avant d'insérer l'élément de données. L'opération d'enroulement définit l'arrière à -1, donc lorsque l'arrière est ajouté 1, il est égal à 0, qui est la valeur de l'indice en bas du tableau, et enfin Nitem en est ajouté.
La condition préalable au fonctionnement de la méthode retire () est que la file d'attente n'est pas vide. Avant d'appeler cette méthode, vous devez appeler la méthode iSEmpty () pour vous assurer que la file d'attente n'est pas vide ou ajouter ce mécanisme de vérification d'erreur à la méthode supprime ().
L'opération de suppression obtient toujours la valeur de l'élément de données d'en-tête du pointeur avant, puis ajoute le avant. Cependant, si vous le faites que la valeur du front dépasse le haut du tableau, le front doit revenir à la position où l'indice du tableau est 0. Pendant ce test, la valeur de retour est temporairement stockée. Enfin, Nitem est réduit d'un.
La méthode peek () est simple et facile à comprendre: elle renvoie la valeur de l'élément de données pointé par le pointeur avant. Certaines implémentations de file d'attente permettent également de visualiser la valeur de l'élément de données de file d'attente; Par exemple, ces méthodes peuvent être appelées peekfront (), peekRear () ou tout simplement avant () et arrière ().
La mise en œuvre des méthodes iSEmpty (), iSull () et size () reposent toutes sur le champ Nitems, qui renvoie si Nitems est égal à 0, qu'il soit égal à maxsize ou renvoie sa propre valeur.
Y compris les champs de comptage des éléments de données Nitems dans la classe de file d'attente ajoutera une petite opération supplémentaire aux méthodes insert () et supprimer (), car les méthodes insert () et supprimer () doivent augmenter et diminuer la valeur de cette variable respectivement. Ce n'est peut-être pas des frais généraux supplémentaires, mais si vous traitez beaucoup d'opérations et supprimez les opérations, cela peut affecter les performances.
Parce que certaines implémentations de file d'attente n'utilisent pas les champs de comptage des éléments de données, mais utilisent avant et arrière pour calculer si la file d'attente est vide ou complète et le nombre d'éléments de données. Si vous faites cela, les routines isEmpty (), iffull () et size () seront assez compliquées car, comme mentionné précédemment, la séquence d'éléments de données est soit effondrée en deux segments, soit un segment continu.
Et, un étrange problème s'est posé. Lorsque la file d'attente est pleine, les pointeurs avant et arrière prennent une certaine position, mais lorsque la file d'attente est vide, la même relation de position peut également apparaître. Donc, en même temps, la file d'attente peut sembler pleine ou vide. La solution à ce problème est: faire en sorte que la capacité du tableau soit une plus que le nombre maximum d'éléments de données de file d'attente.
Merci d'avoir lu, j'espère que cela peut vous aider. Merci pour votre soutien à ce site!