Description
Message queue is the basic fundamental of windows system. For each process, the system maintains a message queue. If something happens to this process, such as mouse click, text change, the system will add a message to the queue. Meanwhile, the process will do a loop for getting message from the queue according to the priority value if it is not empty. Note that the less priority value means the higher priority. In this problem, you are asked to simulate the message queue for putting messages to and getting message from the message queue.
Input
There's only one test case in the input. Each line is a command, "GET" or "PUT", which means getting message or putting message. If the command is "PUT", there're one string means the message name and two integer means the parameter and priority followed by. There will be at most 60000 command. Note that one message can appear twice or more and if two messages have the same priority, the one comes first will be processed first.(i.e., FIFO for the same priority.) Process to the end-of-file.
Output
For each "GET" command, output the command getting from the message queue with the name and parameter in one line. If there's no message in the queue, output "EMPTY QUEUE!". There's no output for "PUT" command.
Sample Input
GET PUT msg1 10 5 PUT msg2 10 4 GET GET GET
Sample Output
EMPTY QUEUE! msg2 10 msg1 10 EMPTY QUEUE!
#include <iostream>
#include <string>
using namespace std;
struct queue
{
string name;
int r;//参数
int key;//优先级
}p[60010];
int heap[60010],top=0,used=0;//used 是用来记录开辟空间的，在删除之后used在出现新的值得时候，会继续往后开辟，但是会调整top
//即顶层的值
int main()
{
string s;
int x=0;
while(cin>>s)
{
// if(x!=0)
//cout<<"++++++++++++++"<<p[0].name<<' '<<p[0].r<<' '<<p[0].key<<"*********************"<<endl;
if(s=="GET")
{
if(top==0)
cout<<"EMPTY QUEUE!"<<endl;
else
{
cout<<p[ heap[1] ].name<<" "<<p[heap[1]].r<<endl;//注意此处的heap是0
int k=1;
heap[k]=heap[top--];//将最后一个的位置传递给首位置
while(2*k<=top)
{
int t = 2*k;
if( t<top && ( p[ heap[t+1] ].key < p[ heap[t] ].key) )
++t;
if( p[heap[t]].key < p[heap[k]].key )
{
int temp=heap[t];
heap[t]=heap[k];
heap[k]=temp;
k=t;
}
else
break;
}
}
}
else
{
x++;
cin>>p[used].name>>p[used].r>>p[used].key;
int k=++top; //最顶层指针
heap[k] = used++ ;
while(k>1)
{
int t=k/2;
if( p[ heap[t] ].key > p[ heap[k] ].key )//此处不能等于，注意队列的性质
{
int temp = heap[t];
heap[t] = heap[k];
heap[k] = temp;
k = t;
}
else
break;
}
}
}
// cout<<endl<<endl;
//for(int i=0;i<used;i++)
// cout << p[i].name <<' '<< p[i].r<<' '<< p[i].key <<endl;
return 0;
}
借鉴库函数简化代码：
/*学习使用优先队列，即二叉堆*/
#include <iostream>
#include <queue>
#include <map>
#include <stdio.h>
#include <string.h>
using namespace std;
#define maxn
struct Messages
{
char msg[20];//消息名称
int par;//参数
int pri;//优先级别
int t;//同一个重复出现的次数
const bool operator<(Messages a) const{//运算符重载
if(a.pri != pri) return a.pri < pri;//先按优先级别划分，然后按出现次数t
return a.t < t; //后面单独的是this指针指向的，从小到大，小值优先输出
}
};
priority_queue<Messages> Q;//优先队列Q
map<int,int> M;//map的映射 //其实这里的map就相当于数组使用了
int main()
{
char s[4];
while(~scanf("%s",s))//读入操作信息
{
if(s[0]=='P')
{
Messages newMsg;//定义输入信息
scanf("%s %d %d",newMsg.msg,&newMsg.par,&newMsg.pri);
newMsg.t=M[newMsg.pri]++;//map记录了重复出现的值，记录了出现了几次，存在了t中
Q.push(newMsg);//压入队列中
}
else if(s[0]=='G'){
if(Q.empty()) printf("EMPTY QUEUE!
");//如果队列为空的话，输出提示信息
else//否则，有优先队列得，最顶的出队列
{//定义输出信息
printf("%s %d
",Q.top().msg,Q.top().par);//按要求输出信息
Q.pop();//删除队首元素
}
}
}
return 0;
}