C# Cookbook

10.2. Creating a Priority Queue

Problem

You need a data structure that operates similarly to a Queue but that returns objects based on a specific order. When objects are added to this queue, they are located in the queue according to their priority. When objects are retrieved from the queue, the queue simply returns the highest or lowest priority element based on which one you ask for.

Solution

Create a priority queue that orders items as they are added to the queue and return items based on their priority. The PriorityQueue class shows how this is accomplished:

using System; using System.Collections; public class PriorityQueue : IEnumerable, ICloneable { public PriorityQueue( ) {} public PriorityQueue(IComparer icomparer) { specialComparer = icomparer; } protected ArrayList internalQueue = new ArrayList( ); protected IComparer specialComparer = null; public int Count { get {return (internalQueue.Count);} } public void Clear( ) { internalQueue.Clear( ); } public object Clone( ) { // Make a new PQ and give it the same comparer PriorityQueue newPQ = new PriorityQueue(specialComparer); newPQ.CopyTo(internalQueue.ToArray( ),0); return newPQ; } public int IndexOf(string str) { return (internalQueue.BinarySearch(str)); } public bool Contains(string str) { if (internalQueue.BinarySearch(str) >= 0) { return (true); } else { return (false); } } public int BinarySearch(string str) { return (internalQueue.BinarySearch(str, specialComparer)); } public bool Contains(string str, IComparer specialComparer) ...