首页 > 试题广场 >

实现一个优先级消息队列。

[问答题]
实现一个优先级消息队列。
不妨将消息抽象成一个整数，该整数数值代表消息的优先级。优先级消息队列是一个这样的队列：任何时间都有可能有消息入队列，任何时间都有可能消息出队列。但只能弹出当前保存的优先级最高的消息。 
class CPriorityMsgQueue
{
  public:
            //任意消息进入队列
          void enQueue(int msg);
          //优先级最高的消息弹出队列
          int deQueue();
  private:
           //可以自行添加需要的私有成员
}
添加回答
小杨vita头像 小杨vita
用堆实现优先级队列
发表于 2015-10-20 22:17:25 回复(0)
stonegrass头像 stonegrass
解题思路：优先级消息队列 使用Java数据结构PriorityQueue，其实它的源码实现就是二叉堆。 
class CPriorityMsgQueue{
    PriorityQueue<Integer> pqueue = new PriorityQueue<Integer>();


	





	public void enQueue(int msg){





	pqueue.offer(msg);





	}





	





	public int deQueue(){ 





	 pqueue.poll(msg);  





	 } 


}

编辑于 2016-11-25 16:03:41 回复(1)
Jason09头像 Jason09
用stl::priority_queue，不是可以直接满足题目要求的吗？
发表于 2016-10-20 20:48:32 回复(0)
DanEmpress头像 DanEmpress

a.链表实现

简单链表的实现过程为在链表的头insert元素，使用O(1)时间完成，每次deleteMin元素，查找出链表中最小的元素，花费O(N)时间完成；另外一种方法是让链表保持有序状态，在进行任务insert的时候进行排序（花费O(N)），每次获取链表的头（花费O(1)）。

b.二叉查找树实现

使用二叉查找树实现中，对于insert和deleteMin花费时间均为O(log(N))，但存在一个潜在问题，既是容易造成不平衡二叉树，因为deleteMin始终是从左边开始往右边进行删除。

c.二叉堆实现

二叉堆对于优先队列实现比较普遍，通二叉查找树一样，二叉堆具有两个性质：结构性和堆序性。
结构性：必须是一颗完全二叉树，树的插入从左到右，一颗完全二叉树的高度为小于log(N)的最大整数。
堆序性：二叉树的父节点必须小于两个子节点。
在二叉堆的具体实现中，通过一个数组来存储所有的元素，具体操作包括：
insert操作：在数组的最后位置添加该元素，然后再通过二叉堆的性质上虑新插入的元素，直到找到该元素的合适位置；
deleteMin操作：删除的元素为根元素，同时把数组最后元素赋值给根元素，根元素根据二叉堆的性质下虑，直到找到合适的位置。
buildHeap操作：对一组输入的数据进行构造堆，通过从下到上对非叶子节点进行下虑，所花费时间为O(N)

发表于 2016-09-01 09:41:33 回复(0)
冷沦黎曦头像 冷沦黎曦
classCPriorityMsgQueue
{
  public:
         //任意消息进入队列
          voidenQueue(intmsg);
          //优先级最高的消息弹出队列
          intdeQueue();
  private:
           //可以自行添加需要的私有成员
          int value;
          Queue queue;
}

void CPriorityMsgQueue::enQueue(intmsg)
{
   queue.push(msg);
}

void CPriorityMsgQueue::deQueue()
{
  int len = queue.size();
  sort(queue,1,len);
  queue.pop_back();
}
发表于 2017-09-13 18:19:57 回复(0)
君奕头像 君奕
用两个栈实现，栈A从上到下从大到小排列，来一个数，先跟栈A顶元素比，大则直接入栈A，否则一直A出栈入B栈，直到A栈顶小于msg，然后再把B栈全部倒回去。

注意：只能从空队列开始操作
编辑于 2017-08-21 21:50:58 回复(0)
努力奋斗的摩羯座女孩头像 努力奋斗的摩羯座女孩
classCPriorityMsgQueue
{
  public:
            //任意消息进入队列
          voidenQueue(intmsg)
          {
       if（  q.empty() )
              q.push( msg);
       else 
        {
            while(  q.front() >msg && !  q.empty() )
            {
               int a = q. front();
               q.pop();
               fuzhu.push(a);
          }
           if( q.empty()  )
          {
               fuzhu.push(msg);

            }

       if(  q.front() <= msg  )
      {
           fuzhu.push(msg);
          while( !  q.empty() )
         {
               int a = q. front();
               q.pop();
               fuzhu.push(a);
         }
      }

while(!fuzhu.empty())
{
   q.push(fuzhu.front());
  fuzhu.pop();
}


}
            


         }
          //优先级最高的消息弹出队列
          int  deQueue()
         {
          if( q.empty())  return q.empty();
          int a =     q.front();
          q.pop();
          return a;
          }
  private:
           //可以自行添加需要的私有成员
        queue<int> q;
        queue<int> fuzhu;
}


发表于 2016-09-02 14:14:52 回复(0)
rong_JCR头像 rong_JCR 
// 编辑起来好别扭啊。。。
classCPriorityMsgQueue
{
  public:
            //任意消息进入队列
          voidenQueue(intmsg)
          {
             if(msgStack.empty())
              {  msgStack.push(msg);
                 return;
               }
             inttp = msgStack;
             while(!msgStack.empty() && tp < msg)
             {
                 msgStack.pop();
                 helper.push(tp);
              }
             msgStack.push(msg);
             while(!helper.empty())
             {
                 inttmp = helper.top();   msgStack.push(tmp);  helper.pop(); 
             }
          }
          //优先级最高的消息弹出队列
          intdeQueue()
          {
             intresMsg = msgStack.top();
             msgStack.pop();
             returnresMsg; 
          }
  private:
          stack<int> msgStack;
          stack<int> helper;

 
}
发表于 2016-09-02 12:05:09 回复(0)
周星星_头像 周星星_ 
class CPriorityMsgQueue
{
  public:
            //任意消息进入队列
          void enQueue(int msg)
          {
              for(vector<int>::iterator it=allmsg.begin();it!=allmsg.end();it++)
              {
                  if(*it<msg) allmsg.insert(it,msg);
              }
          }
          //优先级最高的消息弹出队列
          int deQueue()
          {
              if(!allmsg.empty()) allmsg.erase(allmsg.begin());
          }
  private:
          vector<int> allmsg; //可以自行添加需要的私有成员
}

发表于 2016-08-11 21:23:07 回复(0)
小虎牙头像 小虎牙

1.消息队列

    消息队列是项目中经常需要使用的模式，下面使用STL的queue容器实现：

  

[cpp] view plaincopy
  1. #include <queue>     // STL header file for queue   
  2. #include <list>   
  3. using   namespace  std;  // Specify that we are using the std namespace   
  4.   
  5. class  Message;  
  6.   
  7. class  Message_Queue  
  8. {  
  9.    typedef  queue<Message *, list<Message *> > MsgQueType;  
  10.   
  11.    MsgQueType m_msgQueue;  
  12.         
  13. public :  
  14.    void  Add(Message *pMsg)  
  15.    {  
  16.       // Insert the element at the end of the queue   
  17.       m_msgQueue.push(pMsg);  
  18.    }  
  19.   
  20.    Message *Remove()  
  21.    {  
  22.       Message *pMsg = NULL;  
  23.         
  24.       // Check if the message queue is not empty   
  25.       if  (!m_msgQueue.empty())  
  26.       {  
  27.          // Queue is not empty so get a pointer to the   
  28.          // first message in the queue   
  29.          pMsg = m_msgQueue.front();  
  30.            
  31.          // Now remove the pointer from the message queue   
  32.          m_msgQueue.pop();  
  33.       }  
  34.       return  pMsg;  
  35.    }  
  36.      
  37.    int  GetLength()  const   
  38.    {  
  39.       return  m_msgQueue.size();  
  40.    }     
  41. };  


 

2.优先级消息队列

      上面的消息队列类只支持在队列的尾部添加一个元素，在许多的应用程序中，需要根据消息的优先级将消息添加到队列中，当一个高优先级的消息来了，需要将该消息添加到所有比它优先级低的消息前面，下面将使用priority_queue来实现优先级消息队列类。

    

函数对象(Functors)

优先级消息队列的实现和上面消息队列实现相似，唯一不同的是这里使用了函数对象来决定优先权CompareMessages，该结构重载了操作符"(,)"，该机制可以实现可以将一个函数作为一个参数，和函数指针对比有如下好处：

       1.函数对象效率更高，可以是内联函数，函数指针总是有函数调用的开销。

        2.函数对象提供了一个安全的实现方法，这样的实现不会出现空指针访问。

[cpp] view plaincopy
  1. #include <queue>      // STL header file for queue   
  2. #include <list>   
  3. using   namespace  std;   // Specify that we are using the std namespace   
  4.   
  5. class  Message;  
  6.   
  7. class  Priority_Message_Queue  
  8. {  
  9.     struct  Entry  
  10.     {  
  11.         Message *pMsg;  
  12.         int  priority;  
  13.     };  
  14.      
  15.     struct  Compare_Messages  
  16.     {  
  17.         bool  operator () ( const  Entry& left ,  const  Entry& right)  
  18.         {  
  19.             return  (left.priority < right.priority);  
  20.         }  
  21.     };    
  22.    
  23.    typedef  priority_queue<Entry, vector<Entry>, Compare_Messages  >   
  24.              Message_Queue_Type;  
  25.   
  26.    Message_Queue_Type m_message_Queue;  
  27.         
  28. public :  
  29.   
  30.    void  Add(Message *pMsg,  int  priority)  
  31.    {  
  32.       // Make an entry   
  33.       Entry entry;  
  34.       entry.pMsg = pMsg;  
  35.       entry.priority = priority;  
  36.       // Insert the element according to its priority   
  37.       m_message_Queue.push(entry);  
  38.    }  
  39.      
  40.    Message *Remove()  
  41.    {  
  42.       Message *pMsg = NULL;  
  43.         
  44.       // Check if the message queue is not empty   
  45.       if  (!m_message_Queue.empty())  
  46.       {  
  47.          // Queue is not empty so get a pointer to the   
  48.          // first message in the queue   
  49.          pMsg = (m_message_Queue.top()).pMsg;  
  50.            
  51.          // Now remove the pointer from the message queue   
  52.          m_message_Queue.pop();  
  53.       }  
  54.       return  (pMsg);  
  55.    }  
  56.      
  57.    size_t  Get_Length()  const   
  58.    {  
  59.       return  m_message_Queue.size();  
  60.    }     
  61. };  
发表于 2015-11-23 10:20:09 回复(0)
Ziwen头像 Ziwen
用二叉堆实现比较常见和有效。
发表于 2015-10-23 10:35:04 回复(0)
whx.53@163.com头像 whx.53@163.com
用二叉堆实现
发表于 2015-10-20 16:15:28 回复(0)
提交观点

问题信息

C++工程师 队列 2016 Java工程师 58集团
来自：58同城2016研发工...
上传者：小小
难度：
12条回答 13866浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号