En informatique, une file d'attente est une structure de données linéaire dans laquelle les composants sont placés à une extrémité et supprimés de l'autre extrémité selon le principe « premier entré, premier sorti » (FIFO). Cette structure de données peut être utilisée pour contrôler une séquence d'actions ou stocker des données. C est un langage informatique avec une capacité de file d’attente incorporée sous forme de tableaux ou de listes chaînées.
Caractéristiques:
- Une file d'attente est un type de structure de données linéaire qui peut être construite avec un tableau ou une liste chaînée.
- Les éléments sont déplacés vers l'arrière de la file d'attente tout en étant supprimés du devant.
- Mettre en file d'attente (ajouter un élément à l'arrière) et retirer de la file d'attente (supprimer un élément à l'avant) sont deux opérations de file d'attente.
- Lorsque des éléments sont ajoutés et supprimés fréquemment, une file d'attente peut être créée sous forme de file d'attente circulaire pour éviter de gaspiller de la mémoire.
Utilisation du tableau :
Pour implémenter une file d'attente en C à l'aide d'un tableau, définissez d'abord la taille maximale de la file d'attente et déclarez un tableau de cette taille. Les entiers avant et arrière ont été respectivement fixés à 1. La variable avant représente l'élément avant de la file d'attente et la variable arrière représente l'élément arrière.
Avant de pousser le nouvel élément vers la position finale de la file d'attente, nous devons augmenter la variable back de 1. La file d'attente est maintenant pleine et aucun autre élément supplémentaire ne peut être ajouté lorsque la position back atteint la capacité maximale de la file d'attente. Nous ajoutons un élément au début de la file d'attente et augmentons la variable front de un uniquement pour supprimer un élément de la file d'attente. Si les positions avant et arrière sont égales et qu’aucun composant supplémentaire ne peut être supprimé, on peut donc dire que la file d’attente est vide.
Vous trouverez ci-dessous une instance d'une file d'attente écrite en C qui utilise un tableau :
Langage de programmation C :
#define MAX_SIZE 100 int queue[MAX_SIZE]; int front = -1; int rear = -1; void enqueue(int element) { if (rear == MAX_SIZE - 1) { printf('Queue is full'); return; } if (front == -1) { front = 0; } rear++; queue[rear] = element; } int dequeue() { if (front == -1 || front > rear) { printf('Queue is empty'); return -1; } int element = queue[front]; front++; return element; } int main() { enqueue(10); enqueue(20); enqueue(30); printf('%d ', dequeue()); printf('%d ', dequeue()); printf('%d ', dequeue()); printf('%d ', dequeue()); return 0; } Le résultat du code sera :
Sortir:
10 20 30 Queue is empty-1
Explication:
- Tout d’abord, nous mettons trois éléments 10, 20 et 30 dans la file d’attente.
- Ensuite, nous retirons et imprimons l’élément avant de la file d’attente, qui est 10.
- Ensuite, nous retirons et imprimons à nouveau l'élément avant de la file d'attente, qui est 20.
- Ensuite, nous retirons et imprimons à nouveau l'élément avant de la file d'attente, qui est 30.
- Enfin, nous effectuons une suppression de la file d'attente à partir d'une file d'attente vide qui affiche « La file d'attente est vide » et renvoie -1.
Utilisation de la liste chaînée :
Une autre approche alternative pour construire une file d’attente dans le langage de programmation C consiste à utiliser une liste chaînée. Chacun des nœuds de la file d'attente est exprimé selon cette méthode par un nœud qui contient la valeur de l'élément et un pointeur vers le nœud suivant dans la file d'attente. Afin de garder une trace du premier et du dernier nœuds de la file d'attente, respectivement, des pointeurs avant et arrière sont utilisés.
Nous établissons un nouveau nœud avec la valeur de l'élément et définissons son prochain pointeur sur NULL pour ajouter un élément à la file d'attente. Vers le nouveau nœud, nous définissons les pointeurs avant et arrière si la file d'attente est vide. Sinon, nous mettons à jour le pointeur arrière et définissons le pointeur suivant de l'ancien nœud arrière pour qu'il pointe vers le nouveau nœud.
Lors de la suppression d'un nœud d'une file d'attente, le nœud précédent est d'abord supprimé, puis le pointeur avant est mis à jour vers le nœud suivant dans la file d'attente et enfin la mémoire qu'occupait le nœud supprimé est libérée. Si le pointeur avant est NULL après la suppression, la file d'attente est vide.
Voici un exemple de file d'attente implémentée en C à l'aide d'une liste chaînée :
Langage de programmation C :
#include #include struct Node { int data; struct Node* next; }; struct Node* front = NULL; struct Node* rear = NULL; void enqueue(int element) { struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); new_node->data = element; new_node->next = NULL; if (front == NULL && rear == NULL) { front = rear = new_node; return; } rear->next = new_node; rear = new_node; } int dequeue() { if (front == NULL) { printf('Queue is empty'); return -1; } struct Node* temp = front; int element = temp->data; if (front == rear) { front = rear = NULL; } else { front = front->next; } free(temp); return element; } int main() { enqueue(10); enqueue(20); enqueue(30); printf('%d ', dequeue()); printf('%d ', dequeue()); printf('%d ', dequeue()); printf('%d ', dequeue()); return 0; } Le résultat du code sera :
Sortir:
10 20 30 Queue is empty-1
Explication:
- Tout d’abord, nous mettons trois éléments 10, 20 et 30 dans la file d’attente.
- Ensuite, nous retirons et imprimons l’élément avant de la file d’attente, qui est 10.
- Ensuite, nous retirons et imprimons à nouveau l'élément avant de la file d'attente, qui est 20.
- Ensuite, nous retirons et imprimons à nouveau l'élément avant de la file d'attente, qui est 30.
- Enfin, nous essayons de retirer la file d'attente de la file d'attente vide, ce qui imprime le message « La file d'attente est vide » et renvoie -1.
Avantages :
- Les files d'attente sont particulièrement utiles pour mettre en œuvre des algorithmes qui nécessitent que les éléments soient traités dans une séquence précise, comme la recherche en largeur et la planification des tâches.
- Étant donné que les opérations de file d'attente ont une complexité temporelle O(1), elles peuvent être exécutées rapidement même sur d'énormes files d'attente.
- Les files d'attente sont particulièrement flexibles puisqu'elles peuvent être simplement implémentées à l'aide d'un tableau ou d'une liste chaînée.
Désavantages:
- Une file d'attente, contrairement à une pile, ne peut pas être construite avec un seul pointeur, ce qui rend l'implémentation de la file d'attente légèrement plus complexe.
- Si la file d'attente est construite sous forme de tableau, elle risque de se remplir rapidement si trop d'éléments sont ajoutés, ce qui entraînerait des problèmes de performances, voire un crash.
- Lors de l'utilisation d'une liste chaînée pour implémenter la file d'attente, la surcharge de mémoire de chaque nœud peut être importante, en particulier pour les petits éléments.
Conclusion:
Les applications qui utilisent des files d'attente, une structure de données cruciale, incluent les systèmes d'exploitation, les réseaux et les jeux, pour n'en nommer que quelques-uns. Ils sont idéaux pour les algorithmes qui doivent gérer les éléments dans un ordre particulier car ils sont simples à créer à l'aide d'un tableau ou d'une liste chaînée. Cependant, les files d'attente présentent des inconvénients dont il faut tenir compte lors de la sélection d'une structure de données pour une application particulière, tels que la consommation de mémoire et la complexité de mise en œuvre.