C# 3.0 Cookbook, 3rd Edition

11.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 generic priority queue that orders items as they are added to the queue and returns items based on their priority. The PriorityQueue<T> class of Example 11-1 shows how this can be accomplished.

Example 11-1. Generic PriorityQueue class

using System;
using System.Collections;
using System.Collections.Generic;
public class PriorityQueue<T> : IEnumerable<T>
{
    public PriorityQueue(){}
    public PriorityQueue(IComparer<T> icomparer)
    {
        specialComparer = icomparer;
    }


    protected List<T> internalQueue = new List<T>(); 
    protected IComparer<T> specialComparer = null; 
    protected List<T> InternalQueue 
    {
        get {return internalQueue;}
    }

    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<T> newPQ = new PriorityQueue<T>(specialComparer); newPQ.CopyTo(internalQueue.ToArray(),0); return newPQ; } public int IndexOf(T item) { return (internalQueue.IndexOf(item)); } public bool Contains(T item) { return (internalQueue.Contains(item)); } public int BinarySearch(T item) { return ...