C#中的优先级队列实现

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了C#中的优先级队列实现，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3133字，纯文字阅读大概需要5分钟。

内容图文

我正在尝试使用SortedDictionary实现优先级队列机制,我想就当前的实现获取建议.

我的实现如下：

public class PriorityQueue
{
    private Object lockObj;
    private SortedDictionary<PQMsgPriority, Queue<PQMessage>> messageDictionary; 

    public PriorityQueue()
    {
        lockObj = new object();
        messageDictionary = new SortedDictionary<PQMsgPriority, Queue<PQMessage>>();
    }

    public void Enqueue(PQMessage item)
    {
        lock (lockObj)
        {
            if(item != null && item.MsgPriority == PQMsgPriority.None)
            {
                if (messageDictionary.ContainsKey(item.MsgPriority))
                {
                    Queue<PQMessage> dataList = messageDictionary[item.MsgPriority];
                    dataList.Enqueue(item);
                    messageDictionary[item.MsgPriority] = dataList;
                }
                else
                {
                    Queue<PQMessage> dataList = new Queue<PQMessage>();
                    dataList.Enqueue(item);
                    messageDictionary.Add(item.MsgPriority, dataList);
                }
            }
        }
    }

    public PQMessage Dequeue()
    {
        lock (lockObj)
        {
            PQMessage messageData = null;
            PQMsgPriority deleteKey = PQMsgPriority.None;

            //If no data available, throw an exception
            if (messageDictionary.Count == 0)
                throw new InvalidOperationException();

            foreach (KeyValuePair<PQMsgPriority, Queue<PQMessage>> item in messageDictionary)
            {
                Queue<PQMessage> dataList = item.Value;
                messageData = dataList.Dequeue();
                messageDictionary[item.Key] = dataList;

                //If there is no more elements remaining in the list, set a flag (deleteKey) for deleting the key
                if (dataList.Count == 0) 
                    deleteKey = item.Key;

                break;
            }

            //If the deleteKey flag is set, delete the key from the dictionary
            if (deleteKey != PQMsgPriority.None)
                messageDictionary.Remove(deleteKey);

            return messageData;
        }
    }

    public int Count()
    {
        lock (lockObj)
        {
            return messageDictionary.Count;
        }
    }

    public PQMessage Peek()
    {
        lock (lockObj)
        {
            PQMessage messageData = null;

            //If no data available, throw an exception
            if (messageDictionary.Count == 0)
                throw new InvalidOperationException();

            foreach (KeyValuePair<PQMsgPriority, Queue<PQMessage>> item in messageDictionary)
            {
                Queue<PQMessage> dataList = item.Value;
                messageData = dataList.Peek();
                break;
            }

            return messageData;
        }
    }
}

public enum PQMsgPriority
{
    High = 0,
    Medium = 1,
    Low = 2,
    None = 3
}

public class PQMessage
{
    private PQMsgPriority msgPriority;
    private Object message;

    #region Properties
    public PQMsgPriority MsgPriority
    {
        get { return msgPriority; }
        set { msgPriority = value; }
    }
    public Object Message
    {
        get { return message; }
        set { message = value; }
    }
    #endregion

    public PQMessage(PQMsgPriority msgPriority, Object message)
    {
        this.msgPriority = msgPriority;
        this.message = message;
    }
}

如果还有其他实现优先队列的方法,请向我指出正确的方向.

解决方法:

(我应该以我假设您是为了学习而不是防弹的实现而拒绝此声明.如果想要某些可行的方法,那么最好重用现有的实现).

只是一些一般性评论.在下面的示例中,第三行是不必要的.

Queue<PQMessage> dataList = messageDictionary[item.MsgPriority];
dataList.Enqueue(item);
messageDictionary[item.MsgPriority] = dataList;

从messageDictionary返回的dataList是映射内引用的副本.这意味着,当您使数据入队时,它与以前一样在相同的基础队列上工作(不是队列的副本),因此不需要再次放回去,只需删除该行即可.

在出队实施中,您有一个循环,每次都在第一个元素上中断(例如,您只循环一次).也许您可以使用LINQ进行调查以获取First元素并立即将其返回？ (对于Peek实现类似).

最后,假设PQMessage本身具有优先级,也许您可??以考虑将SortedList用于实现？ (请参阅here)

内容总结

以上是互联网集市为您收集整理的C#中的优先级队列实现全部内容，希望文章能够帮你解决C#中的优先级队列实现所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端