Implémentation de la structure de données File d'attente en C

Introduction

Dans ce projet, vous allez apprendre à implémenter une structure de données de file d'attente en C. Les files d'attente sont largement utilisées en informatique, par exemple, dans les files d'attente de messages qui sont utilisées pour transmettre des données dans un ordinateur.

👀 Aperçu

$ gcc queue.c -o queue
$./queue
11250

🎯 Tâches

Dans ce projet, vous allez apprendre :

• Comment implémenter la méthode front() pour renvoyer la valeur de l'élément frontal dans la file d'attente
• Comment implémenter la méthode pop() pour supprimer et renvoyer l'élément frontal de la file d'attente
• Comment implémenter la méthode count() pour renvoyer le nombre d'éléments actuellement dans la file d'attente
• Comment implémenter la méthode is_empty() pour vérifier si la file d'attente est vide

🏆 Réalisations

Après avoir terminé ce projet, vous serez capable de :

• Comprendre les opérations de base d'une structure de données de file d'attente
• Implémenter les méthodes principales d'une file d'attente en C
• Appliquer vos connaissances sur les files d'attente pour résoudre des problèmes du monde réel

Skills Graph

Implémentez la méthode front()

Dans cette étape, vous allez apprendre à implémenter la méthode front() de la file d'attente.

La méthode front() doit renvoyer la valeur de l'élément frontal dans la file d'attente. Si la file d'attente est vide, la méthode doit quitter le programme avec exit(-1).

Suivez les étapes ci-dessous pour terminer cette étape :

1. Ouvrez le fichier queue.c situé à /home/labex/project/queue.c.
2. Localisez la méthode front() dans le code.
3. Implémentez la méthode front() comme suit :

static int front() {
    if(!phead) {
        exit(-1);
    }
    return phead->val;
}

La méthode front() vérifie d'abord si le pointeur phead est NULL, ce qui indique une file d'attente vide. Si la file d'attente est vide, la méthode quitte le programme avec exit(-1).

Si la file d'attente n'est pas vide, la méthode renvoie la valeur stockée dans le nœud phead, qui représente l'élément frontal de la file d'attente.

Implémentez la méthode pop()

Dans cette étape, vous allez apprendre à implémenter la méthode pop() de la file d'attente.

La méthode pop() doit supprimer et renvoyer l'élément frontal de la file d'attente. Si la file d'attente est vide, la méthode doit quitter le programme avec exit(-1).

Suivez les étapes ci-dessous pour terminer cette étape :

1. Ouvrez le fichier queue.c situé à /home/labex/project/queue.c.
2. Localisez la méthode pop() dans le code.
3. Implémentez la méthode pop() comme suit :

static int pop() {
    if(!phead) {
        exit(-1);
    }
    int val = phead->val;
    phead = phead->next;
    return val;
}

La méthode pop() vérifie d'abord si le pointeur phead est NULL, ce qui indique une file d'attente vide. Si la file d'attente est vide, la méthode quitte le programme avec exit(-1).

Si la file d'attente n'est pas vide, la méthode stocke la valeur du nœud phead, qui représente l'élément frontal de la file d'attente. Ensuite, elle met à jour le pointeur phead pour qu'il pointe vers le nœud suivant, éliminant ainsi effectivement l'élément frontal de la file d'attente. Enfin, la méthode renvoie la valeur stockée.

Implémentez la méthode count()

Dans cette étape, vous allez apprendre à implémenter la méthode count() de la file d'attente.

La méthode count() doit renvoyer le nombre d'éléments actuellement dans la file d'attente.

Suivez les étapes ci-dessous pour terminer cette étape :

1. Ouvrez le fichier queue.c situé à /home/labex/project/queue.c.
2. Localisez la méthode count() dans le code.
3. Implémentez la méthode count() comme suit :

static int count() {
    int cnt = 0;
    for(struct node* p = phead; p; p=p->next) {
        cnt++;
    }
    return cnt;
}

La méthode count() initialise une variable cnt à 0. Ensuite, elle parcourt la file d'attente en suivant les pointeurs next du nœud phead et de ses successeurs. Pour chaque nœud rencontré, elle incrémente la variable cnt. Enfin, la méthode renvoie la valeur de cnt, qui représente le nombre d'éléments dans la file d'attente.

Implémentez la méthode is_empty()

Dans cette étape, vous allez apprendre à implémenter la méthode is_empty() de la file d'attente.

La méthode is_empty() doit renvoyer 1 si la file d'attente est vide, et 0 sinon.

Suivez les étapes ci-dessous pour terminer cette étape :

1. Ouvrez le fichier queue.c situé à /home/labex/project/queue.c.
2. Localisez la méthode is_empty() dans le code.
3. Implémentez la méthode is_empty() comme suit :

static int is_empty() {
    return phead == NULL;
}

La méthode is_empty() vérifie simplement si le pointeur phead est NULL, ce qui indique une file d'attente vide. Si phead est NULL, la méthode renvoie 1, indiquant que la file d'attente est vide. Sinon, elle renvoie 0, indiquant que la file d'attente n'est pas vide.

Félicitations! Vous avez maintenant implémenté toutes les méthodes requises pour la structure de données de file d'attente. Vous pouvez maintenant compiler et exécuter le programme pour tester la fonctionnalité de la file d'attente.

4. Compiler et exécuter :

$ gcc queue.c -o queue
$./queue
00000

La sortie attendue est la suivante :

$ gcc queue.c -o queue
$./queue
11250

Sommaire

Félicitations! Vous avez terminé ce projet. Vous pouvez pratiquer plus de laboratoires sur LabEx pour améliorer vos compétences.