Coda prioritaria in C#

Minahil Noor 12 ottobre 2023

Csharp

Questo articolo introdurrà un equivalente della coda di priorità in C#.

Usare `List` come coda prioritaria in `C#`

In C# non esiste una classe speciale per la coda di priorità. Ma possiamo implementarlo usando array ed liste. Useremo la struttura dei dati dell’lista per implementare una coda di priorità. Una coda di priorità è un tipo di dati astratto che ha una priorità associata ai suoi elementi. L’lista verrà creato in modo che la priorità più alta sarà sempre in testa. L’algoritmo per implementare una coda prioritaria utilizzando l’lista è il seguente.

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’operazione push aggiungerà elementi alla coda di priorità in modo tale che l’elemento con la priorità più alta sia sempre in primo piano. L’operazione pop rimuoverà l’elemento con la priorità più alta dalla coda. L’operazione in alto recupererà l’elemento con la priorità più alta senza rimuoverlo. Il programma seguente mostra come possiamo spingere, far apparire e gli elementi principali da una coda prioritaria.

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

Produzione:

3 1 9 7

L’elemento che ha meno valore di priorità ha una priorità più alta.

Usare List come coda prioritaria in C#

Usare `List` come coda prioritaria in `C#`