La file d'attente peut être décrite comme une structure de données linéaire non primitive qui suit l'ordre FIFO dans lequel les éléments de données sont insérés à partir d'une extrémité (extrémité arrière) et supprimés à l'autre extrémité (extrémité avant). Les autres variantes de la file d'attente sont la file d'attente circulaire, la file d'attente à double extrémité et la file d'attente prioritaire.
Tableau de comparaison
| Base de comparaison | File d'attente linéaire | File d'attente circulaire |
|---|---|---|
| De base | Organise les éléments de données et les instructions dans un ordre séquentiel les uns après les autres. | Organise les données dans le motif circulaire où le dernier élément est connecté au premier élément. |
| Ordre d'exécution de la tâche | Les tâches sont exécutées dans l'ordre où elles ont été placées auparavant (FIFO). | L'ordre d'exécution d'une tâche peut changer. |
| Insertion et suppression | Le nouvel élément est ajouté à partir de l'arrière et retiré de l'avant. | L'insertion et la suppression peuvent être effectuées à n'importe quelle position. |
| Performance | Inefficace | Fonctionne mieux que la file d'attente linéaire. |
Définition de la file d'attente linéaire
Une file d'attente linéaire est rationnellement une liste du premier entré premier sorti . C'est ce qu'on appelle linéaire car il ressemble à une ligne droite où les éléments sont positionnés les uns après les autres. Il contient une collection homogène d'éléments dans laquelle de nouveaux éléments sont ajoutés à une extrémité et supprimés à une autre. Le concept de la file d'attente peut être compris par l'exemple d'une file d'attente du public attendant à l'extérieur du guichet pour obtenir le billet de théâtre. Dans cette file d'attente, la personne rejoint l'extrémité arrière de la file d'attente pour prendre le ticket, lequel est émis au début de la file d'attente.
Il y a plusieurs opérations effectuées dans la file d'attente
- Tout d'abord, la file d'attente est initialisée à zéro (c'est-à-dire vide).
- Déterminez si la file d'attente est vide ou non.
- Déterminez si la file d'attente est pleine ou non.
- Insertion du nouvel élément à partir de l'arrière (Enqueue).
- Suppression de l’élément du début (Dequeue).
La file d'attente peut être mise en œuvre de deux manières
- Statiquement (en utilisant des tableaux)
- Dynamiquement (utilisation de pointeurs)
La limite de la file d'attente linéaire est qu'elle crée un scénario dans lequel aucun nouvel élément ne peut être ajouté dans la file d'attente, même si la file d'attente contient les espaces vides. Cette situation est illustrée dans la figure ci-dessous. Ici, l'arrière pointe sur le dernier index alors que toutes les cases sont encore vides, aucun nouvel élément ne peut être ajouté.
Définition de la file d'attente circulaire
Une file d'attente circulaire est une variante de la file d'attente linéaire qui surmonte efficacement la limitation de la file d'attente linéaire. Dans la file d'attente circulaire, le nouvel élément est ajouté à la toute première position de la file d'attente si le dernier est occupé et que de l'espace est disponible. En ce qui concerne la file d'attente linéaire, l'insertion ne peut être effectuée que de l'arrière et la suppression de l'avant. Dans une file d'attente complète après l'exécution de séries de suppressions successives, il se produit une certaine situation dans laquelle aucun nouvel élément ne peut être ajouté, même si l'espace est disponible car la condition de dépassement inférieur (Arrière = max - 1) existe toujours.
La file circulaire relie les deux extrémités via un pointeur où le tout premier élément vient après le dernier. Il assure également le suivi de l'avant et de l'arrière en mettant en œuvre une logique supplémentaire afin de pouvoir tracer les éléments à insérer et à supprimer. Avec cela, la file d'attente circulaire ne génère pas la condition de débordement tant qu'elle n'est pas pleine.
Quelques conditions suivies par la file d'attente circulaire:
- Avant doit pointer sur le premier élément.
- La file d'attente sera vide si Front = Rear.
- Lorsqu'un nouvel élément est ajouté, la file d'attente est incrémentée de la valeur un (Arrière = Arrière + 1).
- Lorsqu'un élément est supprimé de la file d'attente, l'avant est incrémenté de un (Avant = Avant + 1).
Principales différences entre la file d'attente linéaire et la file d'attente circulaire
- La file d'attente linéaire est une liste ordonnée dans laquelle les éléments de données sont organisés dans l'ordre séquentiel. En revanche, la file d'attente circulaire stocke les données de manière circulaire.
- La file d'attente linéaire suit l'ordre FIFO pour l'exécution de la tâche (l'élément ajouté à la première position va être supprimé à la première position). Inversement, dans la file d'attente circulaire, l'ordre des opérations effectuées sur un élément peut changer.
- L'insertion et la suppression des éléments sont fixées dans une file d'attente linéaire, c'est-à-dire par l'addition à partir de l'arrière et par la suppression de l'avant. D'autre part, la file d'attente circulaire est capable d'insérer et de supprimer l'élément de n'importe quel point jusqu'à ce qu'il soit inoccupé.
- La file d'attente linéaire gaspille l'espace mémoire alors que la file d'attente circulaire optimise l'utilisation de l'espace.
Mise en oeuvre de la file d'attente linéaire
L'algorithme donné ci-dessous illustre l' ajout d'éléments dans une file d'attente:
La file d'attente a besoin de trois variables de données, dont un tableau pour stocker la file d'attente et une autre pour stocker les positions initiale avant et arrière (-1).
insérer (élément, file d'attente, n, arrière) {si (arrière == n), puis afficher "débordement de la file d'attente"; sinon {arrière = arrière + 1; queue [arrière] = item; }} L'algorithme donné ci-dessous illustre la suppression d'éléments dans une file d'attente:
delete_circular (élément, file d'attente, arrière, avant) {if (arrière == avant), puis affiche "dépassement inférieur de la file d'attente"; sinon {avant = avant + 1; item = queue [avant]; }} Mise en oeuvre de la file d'attente circulaire
Un algorithme pour interpréter l' ajout de l'élément dans la file d'attente circulaire:
insert_circular (élément, file d'attente, arrière, avant) {arrière = (arrière + 1) mod n; if (front == rear) puis print "la file d'attente est pleine"; else {queue [arrière] = item; }} L'algorithme explique la suppression de l'élément dans la file d'attente circulaire:
delete_circular (élément, file d'attente, arrière, avant) {if (avant == arrière) puis print ("la file d'attente est vide"); sinon {avant = avant + 1; item = queue [avant]; }} Conclusion
La file d'attente linéaire est inefficace dans certains cas où les éléments doivent se déplacer vers les espaces vides pour pouvoir effectuer une opération d'insertion. C’est la raison pour laquelle il a tendance à gaspiller l’espace de stockage alors que la file d’attente circulaire en fait un usage approprié, car les éléments sont ajoutés à n’importe quel emplacement s’il existe un espace vide.
