Quelle structure de données est une file d’attente ?

Une file d'attente est une structure de données linéaire. La file d'attente autorise uniquement les opérations de suppression à l'avant de la table, tandis que les opérations d'insertion sont effectuées à l'arrière de la table. Comme la pile, la file d'attente est une table linéaire avec des opérations restreintes ; appelé la queue de la file d'attente, et l'opération de suppression est effectuée. La fin est appelée le chef de l'équipe.

L'environnement d'exploitation de cet article : système Windows 10, ordinateur thinkpad t480.

Une file d'attente est une structure de données linéaire.

Une file d'attente est une table linéaire spéciale. La particularité est qu'elle autorise uniquement les opérations de suppression à l'avant (avant) de la table, et les opérations d'insertion à l'arrière (arrière) de la table. comme une pile, une file d'attente est une liste linéaire avec des opérations restreintes. L'extrémité qui effectue l'opération d'insertion est appelée la queue de la file d'attente, et l'extrémité qui effectue l'opération de suppression est appelée la tête de la file d'attente. Lorsqu’il n’y a aucun élément dans la file d’attente, on parle de file d’attente vide.

Les éléments de données de la file d'attente sont également appelés éléments de file d'attente. L'insertion d'un élément de file d'attente dans la file d'attente est appelée mise en file d'attente, et la suppression d'un élément de file d'attente de la file d'attente est appelée sortie de file d'attente. Étant donné que la file d'attente autorise uniquement l'insertion à une extrémité et la suppression à l'autre extrémité, seul l'élément qui entre dans la file d'attente le plus tôt peut être supprimé de la file d'attente en premier. La file d'attente est donc également appelée premier entré, premier sorti (FIFO - premier en premier sorti) liste linéaire.

File d'attente séquentielle

Pour établir une structure de file d'attente séquentielle, vous devez allouer statiquement ou demander dynamiquement un espace de stockage continu et définir deux pointeurs pour la gestion. L'un est le pointeur de tête avant, qui pointe vers l'élément de tête ; l'autre est le pointeur arrière, qui pointe vers l'emplacement de stockage de l'élément suivant dans la file d'attente, comme indiqué sur la figure

Chaque fois qu'un élément est inséré en fin de file d'attente, front augmente de 1 ; chaque fois qu'un élément est supprimé de la tête de file d'attente, front augmente de 1. Au fur et à mesure des opérations d'insertion et de suppression, le nombre d'éléments de file d'attente continue de changer et l'espace de stockage occupé par la file d'attente se déplace également dans l'espace continu alloué à la structure de file d'attente. Lorsque front=rear, il n’y a aucun élément dans la file d’attente, appelée file d’attente vide. Lorsque l'arrière augmente au-delà de l'espace continu qui pointe vers l'allocation, la file d'attente ne peut plus insérer de nouveaux éléments, mais il reste souvent une grande quantité d'espace disponible qui n'est pas occupé à ce moment-là. Ces espaces sont des unités de stockage qui ont été occupées par. éléments de file d’attente qui ont été retirés de la file d’attente.

Phénomène de débordement dans la file d'attente séquentielle :

(1) Phénomène de « sous-débordement » : lorsque la file d'attente est vide, le phénomène de débordement provoqué par le fonctionnement de la file d'attente. Le « sous-débit » est un phénomène normal et est souvent utilisé comme condition pour le transfert de contrôle de programme.

(2) Phénomène de « véritable débordement » : Lorsque la file d'attente est pleine, une opération push sur la pile provoquera un débordement d'espace. Le « vrai débordement » est une condition d'erreur et doit être évité.

(3) Phénomène de "faux débordement": Étant donné que les pointeurs de tête et de queue ne font qu'augmenter mais ne diminuent pas pendant les opérations de mise en file d'attente et de sortie de file d'attente, l'espace de l'élément supprimé ne peut jamais être réutilisé. Lorsque le nombre réel d'éléments dans la file d'attente est bien inférieur à la taille de l'espace vectoriel, l'opération de file d'attente peut ne pas être possible car le pointeur de queue a dépassé la limite supérieure de l'espace vectoriel. Ce phénomène est appelé « faux débordement ».

File d'attente circulaire

Lors de l'utilisation réelle d'une file d'attente, afin de rendre l'espace de la file d'attente réutilisable, l'utilisation de la file d'attente est souvent légèrement améliorée : quelle que soit l'insertion ou la suppression , une fois Lorsque le pointeur arrière est incrémenté de 1 ou que le pointeur avant est incrémenté de 1 et dépasse l'espace de file d'attente alloué, laissez-le pointer vers la position de départ de cet espace continu. Si vous passez réellement de MaxSize-1 de 1 à 0, vous pouvez utiliser les opérations restantes Rear%MaxSize et Front%MaxSize pour y parvenir. Cela imagine en fait l'espace de file d'attente comme un espace circulaire, et les unités de stockage dans l'espace circulaire sont utilisées de manière cyclique. La file d'attente ainsi gérée est également appelée file d'attente circulaire. En plus de quelques applications simples, la file d'attente vraiment pratique est la file d'attente circulaire.

Dans une file d'attente circulaire, lorsque la file d'attente est vide, il y a avant=arrière, et lorsque tout l'espace de la file d'attente est plein, il y a aussi avant=arrière. Afin de distinguer les deux situations, il est stipulé que la file d'attente circulaire ne peut contenir au maximum que des éléments de file d'attente MaxSize-1. Lorsqu'il ne reste qu'une seule unité de stockage vide dans la file d'attente circulaire, la file d'attente est pleine. Par conséquent, la condition pour que la file d'attente soit vide est front=rear et la condition pour que la file d'attente soit pleine est front=(rear+1)%MaxSize. La situation des files d'attente vides et pleines est la suivante :

Recommandé : "Vidéo de programmation"

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!