Introduction à la file d'attente prioritaire en C/C++

Une file d'attente prioritaire est une file d'attente dans laquelle des éléments sont insérés ou supprimés en fonction de la priorité qui leur est attribuée, où la priorité est une valeur entière comprise entre 0 et 10, où 0 représente l'élément avec la priorité la plus élevée et 10 représente l'élément avec L'élément ayant la priorité la plus élevée a la priorité la plus basse. La mise en œuvre d'une file d'attente prioritaire suit deux règles :

• La donnée ou l'élément ayant la priorité la plus élevée sera exécuté avant la donnée ou l'élément ayant la priorité la plus basse.
• Si deux éléments ont la même priorité, ils seront exécutés dans l'ordre dans lequel ils ont été ajoutés à la liste.

Il existe différentes structures de données disponibles qui peuvent être utilisées pour implémenter des files d'attente prioritaires telles que des piles, des files d'attente et des listes chaînées. Dans cet article, nous expliquerons la structure des données de file d'attente. Il existe deux façons d'implémenter une file d'attente prioritaire, par exemple :

• Maintenir des files d'attente pour plusieurs priorités dans un seul tableau

  Une façon d'implémenter une file d'attente prioritaire consiste à maintenir une file d'attente pour chaque priorité. Nous pouvons stocker ces multiples files d'attente dans un tableau où chaque file d'attente a deux pointeurs, Front et Rear. Dans la file d'attente, le pointeur Front est utilisé pour insérer des éléments dans la file d'attente, et il est incrémenté de 1 à chaque fois qu'un élément est inséré ; l'autre pointeur est le pointeur arrière, utilisé pour supprimer ou supprimer des éléments de la file d'attente, et il est ; décrémenté à chaque fois qu'un élément est inséré, 1 est supprimé de la file d'attente. Enfin, à partir des positions des deux pointeurs on peut également déterminer le nombre d'éléments dans la file d'attente.

REMARQUE - Si chaque file d'attente a la même taille, alors au lieu de créer plusieurs tableaux unidimensionnels, nous pouvons créer un tableau bidimensionnel.

Algorithme d'opération d'insertion de file d'attente prioritaire

insert(queue, data, priority)
   If(queue->Rear[priority] = MAX-1 AND queue->Front[priority] = 0) OR (queue->Rear[priority] +1 =queue->Front[priority])
      Print Overflow
   End
   IF queue->Rear[priority - 1] = MAX-1
      Set queue->Rear[priority - 1] = 0
   Else
      Set queue->Rear[priority] = queue->Rear[priority - 1] +1
   End
      Set queue->CQueue[priority - 1] [queue->Rear[priority - 1] = data
   IF queue->Front[priority - 1] = -1
      Set queue->Front[priority - 1] = 0
End

Algorithme d'opération d'insertion dans la file d'attente prioritaire

delete(queue)
   Set flag = 0, priority = 0
      While priority <= MAX-1
         IF NOT queue->Front[priority] = -1
            Set flag = 1
            Set value = queue->CQueue[priority][queue->Front[priority]]
            IF queue->Front[priority] = queue->Rear[priority]
               Set queue->Front[priority] = queue->Rear[priority] = -1
            Else
            IF queue->Front[priority] = MAX-1
               Set queue->Front[priority] = 0
            Else
               Set queue->Front[priority] = queue->Front[priority] + 1
            End
         End
      Break
   End
   Set priority = priority +
End
If flag = 0
   Print underflow
Else
   Return value
End

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!