Title: Make a generic priority queue class in C#

This example shows how to make a generic priority queue class. A generic class is similar to a regular class except it can take one or more parameters that are types. The class can then use the type to define variables and parameters that have that type.

This example creates a generic PriorityQueue class that lets you associate a priority with objects of any given type. Its Enqueue method adds an item to the queue. Its Dequeue method returns the item with the largest priority from the queue and returns it.

The following code shows the generic PriorityQueue class.

class PriorityQueue<T> { // The items and priorities. List<T> Values = new List<T>(); List<int> Priorities = new List<int>(); // Return the number of items in the queue. public int NumItems { get { return Values.Count; } } // Add an item to the queue. public void Enqueue(T new_value, int new_priority) { Values.Add(new_value); Priorities.Add(new_priority); } // Remove the item with the largest priority from the queue. public void Dequeue(out T top_value, out int top_priority) { // Find the hightest priority. int best_index = 0; int best_priority = Priorities[0]; for (int i=1; i<Priorities.Count; i++) { if (best_priority < Priorities[i]) { best_priority = Priorities[i]; best_index = i; } } // Return the corresponding item. top_value = Values[best_index]; top_priority = best_priority; // Remove the item from the lists. Values.RemoveAt(best_index); Priorities.RemoveAt(best_index); } }

The <T> part of the class's declaration indicates that the class takes a type parameter named T. Inside the class, you can use the symbol T to represent the data type assigned to the class when the main program creates it.

The class starts by defining two lists to hold the items and their priorities. Notice how the code uses <T> to create a List containing whatever data type was used to create the PriorityQueue object. The other list simply contains int values.

The NumItems property returns the number of items currently in the queue.

The Enqueue method adds an item to the Values list and its priority to the Priorities list. Notice how the new_item parameter has type T.

The Dequeue method finds the item with the largest priority, sets return values to return the item and its priority, and removes them from their lists.

The following code shows how the main program creates its PriorityQueue.

// The priority queue. private PriorityQueue<string> Queue = new PriorityQueue<string>();

After you create the queue, using it is easy. The following code shows how the program adds an item to it.

Queue.Enqueue(txtValue.Text, int.Parse(txtPriority.Text));

The following code shows how the program removes an item from the queue.

string top_value; int top_priority; Queue.Dequeue(out top_value, out top_priority);

See the example code for other details.

The advantage of generic classes is that they can manipulate objects of any data type fairly easily. For example, this generic PriorityQueue class can hold strings, Employees, Orders, or just about anything else with which you might want to associate a priority.

The System.Collections.Generic namespace contains several useful predefined generic classes including Dictionary, List, Queue (not a priority queue), Stack, and more.

Download the example to experiment with it and to see additional details.