Coda prioritaria in C#

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.