Prioritätswarteschlange in C#

In diesem Artikel wird eine Prioritätswarteschlange in C# eingeführt.

Verwenden Sie die List als Prioritätswarteschlange in C

In C# gibt es keine spezielle Klasse für die Prioritätswarteschlange. Wir können es jedoch mithilfe von Arrays und Listen implementieren. Wir werden die Listendatenstruktur verwenden, um eine Prioritätswarteschlange zu implementieren. Eine Prioritätswarteschlange ist ein abstrakter Datentyp, dessen Elementen eine Priorität zugeordnet ist. Die Liste wird so erstellt, dass immer die höchste Priorität an der Spitze steht. Der Algorithmus zum Implementieren einer Prioritätswarteschlange unter Verwendung der Liste ist wie folgt.

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

Durch die Push-Operation werden Elemente zur Prioritätswarteschlange hinzugefügt, sodass das Element mit der höchsten Priorität immer oben steht. Durch die Pop-Operation wird das Element mit der höchsten Priorität aus der Warteschlange entfernt. Die oberste Operation ruft das Element mit der höchsten Priorität ab, ohne es zu entfernen. Das folgende Programm zeigt, wie wir Elemente aus einer Prioritätswarteschlange verschieben, platzieren und anheben können.


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); 
    } 
} 
} 

Ausgabe:

3 1 9 7

Das Element mit dem geringeren Wert Priorität hat eine höhere Priorität.