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 <cstring>
using namespace std;
#define maxn 60005
#define maxs 101
int top;//堆长度
int used;//缓冲区指针
int heap[maxn];//堆
struct mes
{
char name[maxs];//名字
int para;//参数
int pri;//优先级
int t;//顺序
}p[maxn];
int compare(int a,int b)//优先级为第一关键字
{
if(p[a].pri<p[b].pri)
return -1;
if(p[a].pri>p[b].pri)
return 1;
if(p[a].t<p[a].t)
return -1;
if(p[a].t>p[b].t)
return 1;
return 0;
}
void swap(int &a,int &b)
{
int temp;
temp=a;
a=b;
b=temp;
}
int main()
{
top=0;
used=0;
int cnt=0;//记录消息的顺序
string str;
while(cin>>str)
{
if(str=="GET")
{
if(top)//若堆不空，则输出堆首消息的名字和参数
{
cout<<p[heap[1]].name<<" "<<p[heap[1]].para<<endl;
int k;
k=1;//将堆尾节点调制堆首
heap[k]=heap[top--];//堆长-1
while(k*2<=top)//将堆首节点下调至合适的位置
{
int t;
t=k*2;//计算左右儿子权值最小的节点
if(t<top&&(compare(heap[t+1],heap[t])<0))
++t;
if(compare(heap[t],heap[k])<0)//节点t的权值比其父小，则交换并继续下调下去
{
swap(heap[t],heap[k]);
k=t;
}
else
break;
}
}
else
{
cout<<"EMPTY QUEUE!"<<endl;
}
}
else
{
cin>>p[used].name>>p[used].para>>p[used].pri;
p[used].t=cnt++;//顺序+1
int k=++top;//将消息放入堆尾
heap[k]=used++;
while(k>1)//自底向上，将堆尾节点上调到合适位置
{
int t=k/2;//计算k的父节点序号t
if(compare(heap[t],heap[k])>0)//若节点t的权值大于k的权值，则交换节点t和节点k
{
swap(heap[t],heap[k]);
k=t;
}
else
break;
}
}
}
return 0;
}