Structure de données - File
Une file est une structure de données linéaire qui suit le principe Premier entré, premier sorti (FIFO). Elle peut être comparée au scénario réel de la file d'attente pour acheter des billets — la personne qui fait la queue en premier est servie en premier.
Concept et principe de la file
tête
queue
enfiler : insérer en queue | défiler : supprimer en tête | Complexité O(1)
Vérification FIFO : enfiler 10→20→30, défiler 10→20→30 (Premier entré, premier sorti)
Une file ne permet l'insertion qu'à une extrémité (la queue) et la suppression à l'autre extrémité (la tête).
C'est exactement l'opposé du principe LIFO de la pile.
Implémentation de la file en tableau
Exemple
#include <stdbool.h>
#define MAX 100
struct Queue {
int items[MAX];
int front; /* pointeur front : pointe vers le premier élément */
int rear; /* pointeur rear : pointe vers la position d'insertion suivante */
};
void initQueue(struct Queue* q) {
q->tête = 0;
q->queue = 0;
}
bool isEmpty(struct Queue* q) {
return q->front == q->rear;
}
bool isFull(struct Queue* q) {
return q->rear == MAX;
}
/* enfiler : ajouter un élément à l'arrière */
void enqueue(struct Queue* q, int value) {
if (isFull(q)) {
printf("La file est pleine !\n");
return;
}
q->items[q->rear++] = value; /* écrire à l'indice rear, puis déplacer rear vers l'arrière */
printf("enfiler : %d\n", value);
}
/* défiler : retirer l'élément à l'indice front */
int dequeue(struct Queue* q) {
if (isEmpty(q)) {
printf("La file est vide !\n");
return -1;
}
return q->items[q->front++]; /* renvoyer l'élément à l'indice front, puis déplacer front vers l'arrière */
}
int main() {
struct Queue q;
initQueue(&q);
enqueue(&q, 10); /* enfiler : 10 */
enqueue(&q, 20); /* enqueue: 20 */
enqueue(&q, 30); /* enqueue: 30 */
printf("dequeue: %d\n", dequeue(&q)); /* sortie : dequeue: 10 (FIFO) */
printf("dequeue: %d\n", dequeue(&q)); /* sortie : dequeue: 20 */
printf("dequeue: %d\n", dequeue(&q)); /* sortie : dequeue: 30 */
return 0;
}
Une file implémentée avec un tableau normal a un problème de "faux débordement" : à mesure que les opérations enqueue et dequeue se poursuivent, front et rear continuent de se déplacer vers la fin du tableau, et même s'il y a beaucoup d'espaces vides au début du tableau, ils ne peuvent pas être réutilisés. La solution consiste à utiliser uneFile circulaire。
File circulaire
Formules clés pour la file circulaire
enqueue: items[rear] = value; rear = (rear + 1) % MAX;
dequeue: value = items[front]; front = (front + 1) % MAX;
Vérification de file vide : front == rear | Vérification de file pleine : (rear + 1) % MAX == front
Exemple d'exécution (capacité=5, max 4 éléments) : enfiler 10→20→30→40, défiler 10→20, enfiler 50→60 → 60 stocké à l'indice 0 (retour circulaire), réutilisant parfaitement l'espace libéré.
Une file circulaire traite logiquement le tableau comme une structure en anneau avec la tête et la queue connectées, et implémente le rebouclage des pointeurs via l'arithmétique modulo.
Exemple
#include <stdbool.h>
#define MAX 5 /* définir délibérément une petite capacité pour rendre l'effet circulaire plus facile à observer */
struct CircularQueue {
int items[MAX];
int front; /* indice de tête */
int rear; /* indice de queue (prochaine position d'insertion) */
};
void initQueue(struct CircularQueue* q) {
q->tête = 0;
q->queue = 0;
}
/* vérification de vide : front et rear coïncident */
bool isEmpty(struct CircularQueue* q) {
return q->front == q->rear;
}
/* vérification de saturation : (rear + 1) % MAX == front Remarque : la file circulaire laisse délibérément une position vide pour distinguer l'état vide de l'état plein */
/* enfiler : écrire à la position rear, puis déplacer rear vers l'avant de manière circulaire */
bool isFull(struct CircularQueue* q) {
return (q->rear + 1) % MAX == q->tête;
}
"La file circulaire est pleine !"
void enqueue(struct CircularQueue* q, int value) {
if (isFull(q)) {
printf(/* modulo pour le rebouclage */\n");
return;
}
q->items[q->rear] = value;
q->rear = (q->rear + 1) % MAX; "enqueue: %d (rear=%d)
printf(/* dequeue : renvoyer l'élément à l'emplacement front, puis déplacer front vers l'avant de façon circulaire */\n", value, q->queue);
}
/* Dequeue : renvoyer l'élément à l'emplacement front, puis front avance de façon cyclique */
int dequeue(struct CircularQueue* q) {
if (isEmpty(q)) {
printf("La file circulaire est vide !\n");
return -1;
}
int value = q->items[q->front];
q->front = (q->front + 1) % MAX; /* L'opération modulo implémente le rebouclage */
return value;
}
int main() {
struct CircularQueue q;
initQueue(&q);
enqueue(&q, 10); /* Enfiler : 10 (rear=1) */
enqueue(&q, 20); /* Enfiler : 20 (rear=2) */
enqueue(&q, 30); /* Enfiler : 30 (rear=3) */
enqueue(&q, 40); /* Enfiler : 40 (rear=4) — capacité 5, max 4 éléments */
printf("Défiler : %d\n", dequeue(&q)); /* Défiler : 10 (front=1) */
printf("Défiler : %d\n", dequeue(&q)); /* Défiler : 20 (front=2) */
enqueue(&q, 50); /* Enfiler : 50 (rear=0 — revient au début !) */
enqueue(&q, 60); /* Enfiler : 60 (rear=1) */
printf("Éléments restants : ");
while (!isEmpty(&q)) {
printf("%d ", dequeue(&q));
}
printf("\n"); /* Sortie : éléments restants : 30 40 50 60 */
return 0;
}
Scénarios d'application des files d'attente
| Scénarios d'application | Description |
|---|---|
| Recherche en largeur d'abord (BFS) | Parcourir les nœuds d'un graphe niveau par niveau ; une file est nécessaire pour stocker les nœuds "à visiter". |
| Ordonnancement des tâches du système d'exploitation | Le CPU alloue des tranches de temps dans l'ordre d'arrivée des tâches |
| File d'attente des tâches d'impression | Plusieurs ordinateurs partagent une imprimante ; les demandes d'impression sont mises en file d'attente et traitées dans l'ordre de soumission |
| File de messages | Dans les systèmes distribués, les messages produits par les producteurs sont transmis aux consommateurs via une file d'attente |