Prioritätswarteschlange in C#

Minahil Noor 12 Oktober 2023

Csharp

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

Verwendung von 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.

Verwendung von die List als Prioritätswarteschlange in C#

Verwendung von die `List` als Prioritätswarteschlange in `C#`