A queue is a data structure that works on a first in, first out (FIFO) basis. Items are inserted at the rear of the queue and removed from the front. The term “enqueue” denotes the operation that inserts data in the queue, while the term “dequeue” denotes the operation that removes data from the queue.

A priority queue is a type of queue in which the elements are arranged based on priority values ​​you assign to them. Support for a priority queue was newly introduced in .NET 6. This article will discuss the PriorityQueue class in .NET 6 and how to work with it in our .NET 6 applications.

To work with the code examples provided in this article, you should have Visual Studio 2022 installed in your system. If you don’t already have a copy, you can download Visual Studio 2022 here.

Create a console application project in Visual Studio

First off, let’s create a .NET Core Console Application project in Visual Studio. Assuming Visual Studio 2022 is installed in your system, follow the steps outlined below to create a new .NET Core Console Application project in Visual Studio.

  1. Launch the Visual Studio IDE.
  2. Click on “Create new project.”
  3. In the “Create new project” window, select “Console App (.NET Core)” from the list of templates displayed.
  4. Click Next.
  5. In the “Configure your new project” window shown next, specify the name and location for the new project.
  6. Click Create.

We’ll use this project to work with a priority queue in the subsequent sections of this article.

Create a priority queue in .NET 6

A queue in .NET 6 is typically a FIFO data structure, in which items are added to the rear of the queue and removed from the front. A priority queue in .NET 6 is a special type of queue that orders the items based on the priority values ​​you assign to them.

You can create an instance of the PriorityQueue class using the constructor of the PriorityQueue class as shown below.

PriorityQueue<string, int> priorityQueue = new PriorityQueue<string, int>();

Once you have created a PriorityQueue, you can add items to the queue using the Enqueue() method. The Enqueue method accepts two parameters—the element to be added as string and the priority of the element as an integer.

Note that items in a priority queue are arranged in the descending order of their priority values. Hence the item having the largest priority value (eg, 9) is positioned at the rear of the queue, and the item having the lowest priority value (eg, 0) is positioned at the front. In other words, a dequeue removes the item with the lowest priority value.

The following code snippet shows how you can add items to a priority queue using the Enqueue method.

PriorityQueue<string, int> priorityQueue = new PriorityQueue<string, int>();
priorityQueue.Enqueue("Item A", 4);
priorityQueue.Enqueue("Item B", 3);
priorityQueue.Enqueue("Item C", 2);
priorityQueue.Enqueue("Item D", 6);
priorityQueue.Enqueue("Item E", 7);
priorityQueue.Enqueue("Item F", 5);
priorityQueue.Enqueue("Item G", 0);
priorityQueue.Enqueue("Item H", 9);
priorityQueue.Enqueue("Item I", 1);
priorityQueue.Enqueue("Item J", 8);

Retrieve elements from a priority queue in .NET 6

You can retrieve items from a PriorityQueue in two different ways. One option is to use the Dequeue() method, which returns the item having the lowest priority value in the queue. The other option is to use the Peek() method, which returns the item having the lowest priority value without removing it from the queue.

The TryDequeue and TryPeek methods are enhanced versions of the Dequeue and Peek methods that handle exceptions internally. They return true if an item has been successfully removed from the queue, and return false otherwise.

The following code snippet illustrates how you can remove the items from the priority queue and display each item and its priority at the console window.

while (priorityQueue.TryDequeue(out string queueItem, out int priority))
{
     Console.WriteLine($"Item : {queueItem}. Priority : {priority}");
}

Complete priority queue example in .NET 6

The complete program is given below for your reference.

using System.Collections.Generic;
internal class Program
{
   static void Main(string[] args)
   {
     PriorityQueue<string, int> priorityQueue =
     new PriorityQueue<string, int>();
     priorityQueue.Enqueue("Item A", 4);
     priorityQueue.Enqueue("Item B", 3);
     priorityQueue.Enqueue("Item C", 2);
     priorityQueue.Enqueue("Item D", 6);
     priorityQueue.Enqueue("Item E", 7);
     priorityQueue.Enqueue("Item F", 5);
     priorityQueue.Enqueue("Item G", 0);
     priorityQueue.Enqueue("Item H", 9);
     priorityQueue.Enqueue("Item I", 1);
     priorityQueue.Enqueue("Item J", 8);

     while (priorityQueue.TryDequeue(out string queueItem, out int priority))
     {
         Console.WriteLine($"Item : {queueItem}. Priority : {priority}");
     }
     Console.Read();
   }
}

When you execute the application, the console output should appear as shown in Figure 1 below.

dotnet priority queue 01 IDG

Figure 1. Dequeueing our priority queue.

Count the elements in a priority queue in .NET 6

You can use the following code snippet to check the number of items in the priority queue at any given point of time.

int ctr = priorityQueue.Count;
Console.WriteLine($"No of items remaining in the priority queue : {ctr}");

If you insert these lines of code after the while statement in our program, as illustrated below, the number of available items in the priority queue will be 0. This is because each call to the TryDequeue method removes an element from the priority queue.

while (priorityQueue.TryDequeue(out string queueItem, out int priority))
{
    Console.WriteLine($"Item : {queueItem}. Priority : {priority}");
}
int ctr = priorityQueue.Count;
Console.WriteLine($"No of items remaining in the priority queue : {ctr}");

If you run our program with the code above, it will display the items of the priority queue and their priority values. Lastly, it will print a value 0, which denotes the total number of elements remaining in the priority queue at the end.

dotnet priority queue 02 IDG

Figure 2. Our priority queue with element counter.

A priority queue in .NET 6 uses the IComparer interface to determine the priority of elements stored inside it. You can write your own implementation of the IComparer interface and use it to determine the priorities of elements in a priority queue. I’ll discuss this further in a future post here.

Finally, note that a PriorityQueue instance is not thread-safe. You should write your own custom code to handle thread safety to avoid race conditions. Priority queues are typically used by operating systems for load balancing, thread scheduling, and handling interrupts. An operating system will use a priority queue to store threads and schedule or preempt them as needed.

Copyright © 2022 IDG Communications, Inc.

Source link

Leave a Reply

Your email address will not be published. Required fields are marked *