Comment implémenter une file d'attente basée sur un tableau en utilisant le langage C

En programmation, la file d'attente est une structure de données couramment utilisée. De nombreux langages de programmation ont leurs propres implémentations de file d'attente, telles que Queue en Java et deque en Python. Cependant, en langage C, il n’existe pas d’implémentation de file d’attente prête à l’emploi. Par conséquent, en langage C, nous devons implémenter la file d'attente en définissant un tableau et en utilisant des pointeurs et d'autres astuces.

Dans cet article, nous présenterons comment implémenter une file d'attente basée sur un tableau en utilisant le langage C.

1. Définir une structure de file d'attente

Nous pouvons implémenter des opérations de file d'attente en définissant une structure de file d'attente. Cette structure de file d'attente comprend des informations telles que la taille de la file d'attente, les pointeurs de tête et de queue, les données des éléments, etc.

#define MAX_SIZE 100

typedef struct queue {
    int size;
    int front;
    int rear;
    int data[MAX_SIZE];
} Queue;

Dans le code ci-dessus, nous définissons une constante MAX_SIZE pour représenter la taille maximale de la file d'attente, et déclarons une file d'attente nommée Queue en définissant une structure.

Parmi eux, size représente la taille de la file d'attente, front représente le pointeur de tête de file d'attente, Rear représente le pointeur de queue de file d'attente et data est un tableau stockant des éléments.

2. Opération d'initialisation de la file d'attente

Dans la mise en œuvre de la file d'attente, l'opération d'initialisation de la file d'attente doit être effectuée en premier pour garantir l'utilisation correcte de la file d'attente.

void init(Queue *q) {
    q->size = 0;
    q->front = 0;
    q->rear = -1;
}

Dans le code ci-dessus, nous définissons une fonction d'initialisation init, qui accepte le pointeur q pointant vers la structure de file d'attente comme paramètre et définit la taille de la file d'attente sur 0, le pointeur de tête sur 0 et le pointeur de queue sur - 1, indiquant que la file d'attente est vide.

3. Opération de mise en file d'attente des éléments

L'opération de mise en file d'attente consiste à placer un élément à la fin de la file d'attente. L'implémentation ici consiste à ajouter l'élément à la fin des données du tableau et à mettre à jour la position du pointeur arrière. .

int enqueue(Queue *q, int value) {
    if(q->size == MAX_SIZE) {
        return 0;
    }
    q->rear++;
    q->data[q->rear] = value;
    q->size++;
    return 1;
}

Dans le code ci-dessus, déterminez d'abord si la file d'attente est pleine. Si elle est pleine, renvoyez 0 pour indiquer que l'insertion a échoué. Sinon, reculez d'un bit le pointeur arrière, attribuez la valeur de l'élément à la fin des données. tableau, et la taille de la file d'attente est augmentée de 1, et enfin 1 est renvoyé pour indiquer une insertion réussie.

4. Opération de retrait d'élément de file d'attente

L'opération de retrait de file d'attente de la file d'attente consiste à retirer l'élément en tête de la file d'attente et à mettre à jour la position du pointeur avant. L'idée mise en œuvre ici est de renvoyer la valeur de l'élément à la position avant dans les données, de déplacer le pointeur avant vers l'arrière d'un bit et de mettre à jour la taille de la file d'attente en même temps.

int dequeue(Queue *q) {
    if(q->size == 0) {
        return -1;
    }
    int value = q->data[q->front];
    q->front++;
    q->size--;
    return value;
}

Dans le code ci-dessus, déterminez d'abord si la file d'attente est vide. Si elle est vide, renvoyez -1 pour indiquer que la file d'attente est vide. Sinon, renvoyez la valeur de l'élément à l'avant des données et déplacez l'avant. pointeur en arrière d'un bit. La file d'attente diminue la taille de 1 et renvoie la valeur de l'élément.

5. Test de l'implémentation de la file d'attente

Maintenant que nous avons implémenté diverses opérations de la file d'attente, testons-la :

#include <stdio.h>

int main() {
    Queue myQueue;
    init(&myQueue);
    enqueue(&myQueue, 1);
    enqueue(&myQueue, 2);
    enqueue(&myQueue, 3);
    printf("%d\n", dequeue(&myQueue));
    printf("%d\n", dequeue(&myQueue));
    printf("%d\n", dequeue(&myQueue));
    return 0;
}

Dans le code de test ci-dessus, nous définissons d'abord une file d'attente nommée myQueue et utilisons la fonction init pour l'initialiser. Ensuite, nous utilisons la fonction enqueue pour insérer les numéros 1, 2 et 3 dans la file d'attente, et utilisons la fonction dequeue pour supprimer des éléments de la file d'attente et les afficher à l'écran.

Le résultat ici devrait être :

1
2
3

6. Résumé

Dans cet article, nous avons appris comment implémenter une file d'attente basée sur un tableau en utilisant le langage C. En définissant une structure de file d'attente et les fonctions opérationnelles associées, nous pouvons facilement ajouter, supprimer et accéder aux éléments de la file d'attente. Bien qu'il soit difficile d'utiliser des pointeurs pour implémenter des files d'attente, cette méthode peut nous aider à mieux comprendre les principes des files d'attente et est d'une grande aide dans l'apprentissage des structures de données et des algorithmes.

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!