File d'attente prioritaire en C#
Cet article présentera une file d’attente prioritaire équivalente en C#.
Utilisez la Liste comme file d’attente prioritaire en C#
En C#, il n’y a pas de classe spéciale pour la file d’attente prioritaire. Mais nous pouvons l’implémenter en utilisant des tableaux et des listes. Nous utiliserons la structure de données de liste pour implémenter une file d’attente prioritaire. Une file d’attente prioritaire est un type de données abstrait qui a une priorité associée à ses éléments. La liste sera créée de manière à ce que la priorité la plus élevée soit toujours en tête. L’algorithme d’implémentation d’une file d’attente prioritaire à l’aide de la liste est le suivant.
PUSH(HEAD, VALUE, PRIORITY)
Step 1 : Create a new node with VALUE and PRIORITY Step 2
: Check if HEAD has lower priority.If true follow Steps 3 -
4 and end.Else goto Step 5. Step 3 : NEW->NEXT = HEAD Step 4 : HEAD = NEW Step 5
: Set TEMP to head of the list Step 6
: While TEMP->NEXT != NULL and TEMP->NEXT->PRIORITY > PRIORITY Step 7
: TEMP = TEMP->NEXT[END OF LOOP] Step 8 : NEW->NEXT = TEMP->NEXT Step 9
: TEMP->NEXT = NEW Step 10 : End POP(HEAD) Step 2
: Set the head of the list to the next node in the list.HEAD = HEAD->NEXT.Step 3
: Free the node at the head of the list Step 4 : End TOP(HEAD)
: Step 1 : Return HEAD->VALUE Step 2 : End
L’opération push ajoutera des éléments à la file d’attente prioritaire de telle sorte que l’élément avec la priorité la plus élevée soit toujours en haut. L’opération pop supprimera l’élément avec la priorité la plus élevée de la file d’attente. L’opération supérieure récupérera l’élément de priorité la plus élevée sans le supprimer. Le programme ci-dessous montre comment nous pouvons pousser, faire apparaître et les éléments supérieurs d’une file d’attente prioritaire.
using System;
class PriorityQueue {
public class Node {
public int data;
public int priority;
public Node next;
}
public static Node node = new Node();
public static Node newNode(int d, int p) {
Node temp = new Node();
temp.data = d;
temp.priority = p;
temp.next = null;
return temp;
}
public static int top(Node head) {
return (head).data;
}
public static Node pop(Node head) {
Node temp = head;
(head) = (head).next;
return head;
}
public static Node push(Node head, int d, int p) {
Node start = (head);
Node temp = newNode(d, p);
if ((head).priority > p) {
temp.next = head;
(head) = temp;
} else {
while (start.next != null && start.next.priority < p) {
start = start.next;
}
temp.next = start.next;
start.next = temp;
}
return head;
}
public static int isEmpty(Node head) {
return ((head) == null) ? 1 : 0;
}
public static void Main(string[] args) {
Node queue = newNode(1, 1);
queue = push(queue, 9, 2);
queue = push(queue, 7, 3);
queue = push(queue, 3, 0);
while (isEmpty(queue) == 0) {
Console.Write("{0:D} ", top(queue));
queue = pop(queue);
}
}
}
Production:
3 1 9 7
L’élément qui a moins de valeur de priorité a une priorité plus élevée.