Priority Queue in C#

This article will introduce a priority queue equivalent in C#.

Use the List as Priority Queue in C

In C#, there is no special class for the priority queue. But we can implement it using arrays and lists. We will use the list data structure to implement a priority queue. A priority queue is an abstract data type that has a priority associated with its elements. The list will be created in a way that the highest priority will always be at the head. The algorithm for implementing a priority queue using the list is as follows.

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

The push operation will add elements to the priority queue such that the element with the highest priority is always on top. The pop operation will remove the element with the highest priority from the queue. The top operation will retrieve the highest priority element without removing it. The program below shows how we can push, pop, and top elements from a priority queue.


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

Output:

3 1 9 7

The element that has less value of priority has higher priority.

Contribute
DelftStack is a collective effort contributed by software geeks like you. If you like the article and would like to contribute to DelftStack by writing paid articles, you can check the write for us page.