File d'attente circulaire en C : comment implémenter ?
Publié: 2020-10-23Les données sont disposées dans une file d'attente circulaire selon un motif circulaire où le dernier élément est connecté au premier élément. Contrairement à la file d'attente linéaire où les tâches sont exécutées sur FIFO (First In First Out), l'ordre circulaire de la file d'attente d'exécution des tâches peut changer. Les opérations d'insertion et de suppression peuvent être effectuées dans n'importe quelle position.
La file d'attente circulaire est plus efficace que la file d'attente linéaire. Dans la représentation graphique d'une file d'attente circulaire, vous pouvez observer que les positions avant et arrière sont connectées, ce qui en fait un cercle dans lequel les opérations sont toujours exécutées sur une base FIFO. Chaque nouvel élément est ajouté à l'arrière et supprimé de l'avant. Une file d'attente circulaire a une meilleure utilisation et a une complexité temporelle de O(1).
La source
Table des matières
Applications d'une file d'attente circulaire
- Ordonnancement CPU : les files d'attente circulaires utilisent les espaces mémoire vides qui se trouvent dans les files d'attente linéaires.
- Système de circulation : dans le système de circulation, à l'aide des files d'attente circulaires, les feux de circulation sont activés à l'intervalle de temps défini.
- Gestion de la mémoire : les systèmes d'exploitation maintiennent fréquemment une ligne de processus qui sont prêts à s'exécuter ou qui attendent qu'un événement spécifique se produise.
Apprenez : Programme C pour le tri à bulles : Tri à bulles en C
Exemple de code avec explication
Ligne 1 : // (1) Préprocesseurs
Ligne 2 : // Définir la limite de la file d'attente à 5 éléments
Ligne 3 : #include<stdio.h>
Ligne 4 : #define LIM 5
Ligne 5 : // (2) Déclarations de type de données de file d'attente
Ligne 6 : // les données contiennent des données ; delPos, position à supprimer ; longueur, non. de
Ligne 7 : // éléments actuellement présents dans la file d'attente
Ligne 8 : typedef struct queue {
Ligne 9 : int data[LIM], delPos, longueur ;
Ligne 10 : } Q ;
Ligne 11 : // (3) Déclarations globales
Ligne 12 : // Fonctions & variable globale q de type struct queue
Ligne 13 : Q q ;
Ligne 14 : void ui_Q_Ops(), insertQel(), deleteQel(), displayQels(), initQ();
Ligne 15 : // (4) Appelle la fonction d'interface utilisateur après l'initialisation
Ligne 16 : int main()
Ligne 17 : {
Ligne 18 : initQ();
Ligne 19 : ui_Q_Ops();
Ligne 20 : renvoie 0 ;
Ligne 21 : }
Ligne 22 : // (5) Initialiser la file d'attente
Ligne 23 : annuler initQ()
Ligne 24 : {
Ligne 25 : q.longueur = 0 ;
Ligne 26 : q.delPos = 0 ;
Ligne 27 : }
Ligne 28 : // (6) Menu Driven Loop appelle les fonctions correctes
Ligne 29 : annuler ui_Q_Ops()
Ligne 30 : {
Ligne 31 : int choix=0 ;
Ligne 32 : entrée de caractères[16] ;
Ligne 33 : tandis que(choix !=4){
Ligne 34 : printf(" \n ———————-\n ");
Ligne 35 : printf(" 1. Insérer dans la file d'attente \n ");
Ligne 36 : printf(" 2. Supprimer de la file d'attente \n ");
Ligne 37 : printf(" 3. Afficher les éléments de la file d'attente \n ");
Ligne 38 : printf(" 4. Quittez le programme \n ");
Ligne 39 : printf(" Entrer le choix : ");
Ligne 40 : if (fgets(input, 15, stdin) != NULL){
Ligne 41 : if (sscanf(input, "%d", &choice) == 1){
Ligne 42 : switch(choix){
Ligne 43 : cas 1 : insertQel();
Ligne 44 : pause ;
Ligne 45 : cas 2 : deleteQel();
Ligne 46 : pause ;
Ligne 47 : cas 3 : displayQels();
Ligne 48 : pause ;
Ligne 49 : cas 4 : retour ;
Ligne 50 : par défaut : printf("Choix invalide\n ");
Ligne 51 : continuez ;
Ligne 52 : }
Ligne 53 : } sinon
Ligne 54 : printf(" Choix invalide \n ");
Ligne 55 : }
Ligne 56 : }
Ligne 57 : }
Ligne 58 : // (7) Insérer dans la file d'attente
Ligne 59 : // Si la longueur est identique à la limite MAX, la file d'attente est pleine, sinon insérez
Ligne 60 : // réalisé de manière circulaire avec somme longueur et module delPos par MAX Limit
Ligne 61 : // et la longueur de l'incrément
Ligne 62 : annuler insertQel()
Ligne 63 : {
Ligne 64 : int el, inspos ;
Ligne 65 : entrée de caractères[16] ;
Ligne 66 : si (q.longueur == LIM){
Ligne 67 : printf(" La file d'attente est pleine \n ");
Ligne 68 : retour ;
Ligne 69 : }
Ligne 70 : inspos = (q.delPos + q.length) % LIM ;
Ligne 71 : printf(" Entrez l'élément à insérer : ");
Ligne 72 : if (fgets(input, 15, stdin) != NULL){
Ligne 73 : if (sscanf(input, "%d", &el)){
Ligne 74 : q.data[inspos] = el ;
Ligne 75 : q.longueur++ ;
Ligne 76 : } sinon
Ligne 77 : printf(" Entrée invalide \n ");
Ligne 78 : }
Ligne 79 : }
Ligne 80 : // (8) Supprimer de la file d'attente
Ligne 81 : // Si Length vaut 0, la file d'attente est vide, sinon supprimer à delPos
Ligne 82 : // et décrémenter la longueur
Ligne 83 : annuler deleteQel()
Ligne 84 : {
Ligne 85 : si (q.longueur == 0){
Ligne 86 : printf(" La file d'attente est vide \n ");
Ligne 87 : } sinon {
Ligne 88 : printf(" Élément supprimé %d \n ", q.data[q.delPos]);
Ligne 89 : q.delPos = (q.delPos + 1) % LIM ;
Ligne 90 : q.longueur– ;
Ligne 91 : }
Ligne 92 : }
Ligne 93 : // (9) Afficher les éléments de la file d'attente
Ligne 94 : // Affichage de manière circulaire en exécutant une boucle commençant à delPos
Ligne 95 : // et ajout de l'itérateur et du module par Max Limit
Ligne 96 : annuler displayQels()
Ligne 97 : {
Ligne 98 : int i ;
Ligne 99 : si (q.longueur == 0){
Ligne 100 : printf(" La file d'attente est vide \n ");
Ligne 101 : } sinon {
Ligne 102 : printf(” Les éléments de file d'attente sont : “);
Ligne 103 : for(i = 0; i < q.length; i++){
Ligne 104 : printf("%d", q.data[(q.delPos+i)%LIM]);
Ligne 105 : }
Ligne 106 : printf(" \n ");
Ligne 107 : }
Ligne 108 : }
Ligne 109 :
Les sorties:
Opérations sur une file d'attente circulaire
1. insertQel() - Insertion d'un élément dans la file d'attente circulaire
Dans une file d'attente circulaire, la fonction enQueue() est utilisée pour insérer un élément dans la file d'attente circulaire. Dans une file d'attente circulaire, la nouvelle fonctionnalité est toujours insérée en position arrière. La fonction enQueue() prend une valeur entière comme paramètre et l'insère dans la file d'attente circulaire. Les étapes suivantes sont mises en œuvre pour insérer un élément dans la file d'attente circulaire :
Étape 1 - Vérifiez si la longueur est la même que la limite MAX. Si vrai, cela signifie que la file d'attente est PLEINE. S'il est PLEIN, alors affichez « La file d'attente est pleine » et terminez la fonction.
Étape 2 - S'il n'est PAS COMPLET, insérez la valeur obtenue de manière circulaire avec la longueur de somme et le module delPos par MAX Limit et la longueur d'incrément
2. deleteQel() - Suppression d'un élément de la file d'attente circulaire
Dans une file d'attente circulaire, deQueue() est une fonction utilisée pour supprimer un élément de la file d'attente circulaire. Dans une file d'attente circulaire, l'élément est toujours supprimé de la première position. La fonction deQueue() ne prend aucune valeur en paramètre. Les étapes suivantes sont mises en œuvre pour supprimer un élément de la file d'attente circulaire…
Étape 1 – Vérifiez si la file d'attente est VIDE. (avant == -1 && arrière == -1)
Étape 2 - S'il est VIDE, affichez "La file d'attente est vide" et terminez la fonction.
Étape 3 - S'il n'est PAS VIDE, affichez les éléments supprimés en fonction des positions. Une fois chaque élément ajouté, passez à la limite de file d'attente de modification de position suivante.
3. displayQels() – Affiche les éléments de file d'attente qui sont présents dans la file d'attente circulaire. Les étapes suivantes sont mises en œuvre pour afficher les éléments d'une file d'attente circulaire :
Étape 1 – Vérifiez si la file d'attente est VIDE.
Étape 2 - Si la longueur est 0, elle est VIDE, puis affichez "La file d'attente est vide" et terminez la fonction.
Étape 3 - S'il n'est PAS VIDE, définissez une variable entière 'i.'
Étape 4 - Réglez i sur 0.
Étape 5 - Encore une fois, affichez les éléments en fonction de la position et incrémentez la valeur de un (i++). Répétez la même chose jusqu'à ce que 'i <q.length' devienne FALSE.
La file d'attente circulaire peut également être implémentée en utilisant la liste liée. Voici les algorithmes :
- Algorithme pour la mise en file d'attente :
if (FRONT == NULL) // Insertion dans une file d'attente vide
AVANT = ARRIÈRE = nouveauNoeud
fin si
autre
REAR -> next = newNode // Insertion après le dernier élément
REAR = nouveauNoeud
finir autrement
ARRIÈRE -> suivant = AVANT
Mettre fin à la file d'attente
- Algorithme pour Dequeue :
if(FRONT == NULL) // Condition de sous-dépassement
Imprimer "File d'attente insuffisante"
fin de la file d'attente
fin si
else if(FRONT == REAR) // La file d'attente ne contient qu'un seul nœud
temp = AVANT -> données
gratuit (température)
AVANT = AVANT -> suivant
ARRIÈRE -> suivant = AVANT
fin si
else if (FRONT == N – 1) // Si FRONT est le dernier noeud
front = 0 // Faire de FRONT le premier nœud
fin si
fin de la file d'attente
Lisez aussi : Python Vs C : comparaison complète côte à côte
Conclusion
Les structures de données et les algorithmes sont d'une grande importance et pas seulement dans la programmation C mais aussi dans d'autres langages. Sa valeur est sans précédent, et pour des sujets d'une telle importance, il vaut mieux investir dans des cours conçus et encadrés par des experts, qui apporteront une excellente valeur ajoutée à votre portefeuille. upGrad propose une large gamme de cours puissants qui non seulement améliorent vos compétences, mais construisent de solides piliers de base.
Il est conçu par le très réputé IIIT-B, où ils fournissent non seulement un contenu de qualité supérieure, mais vous font également partie d'un réseau solide où vous vous connecterez avec des personnes qui évoluent dans le même cheminement de carrière ainsi qu'avec les experts de l'industrie qui résoudre vos doutes et vous soutenir à chaque fois.
Apprendre à connaître leur mentalité et leur processus de pensée vous aiderait. Et l'une des choses u niques que vous obtenez chez upGrad est que vous pouvez opter pour les options EMI et ménager vos poches.
Nous espérons que vous aurez une excellente opportunité d'apprentissage dans l'exécution de ces projets C. Si vous souhaitez en savoir plus et avez besoin du mentorat d'experts de l'industrie, consultez le diplôme PG upGrad & IIIT Banglore en développement de logiciels Full-Stack .