消息队列是Windows系统的基础。对于每个进程,系统维护一个消息队列。如果在进程中有特定事件发生,如点击鼠标、文字改变等,系统将把这个消息加到队列当中。同时,如果队列不是空的,这一进程循环地从队列中按照优先级获取消息。请注意优先级值低意味着优先级高。请编辑程序模拟消息队列,将消息加到队列中以及从队列中获取消息。
输入格式:
输入首先给出正整数N(≤),随后N行,每行给出一个指令——GET
或PUT
,分别表示从队列中取出消息或将消息添加到队列中。如果指令是PUT
,后面就有一个消息名称、以及一个正整数表示消息的优先级,此数越小表示优先级越高。消息名称是长度不超过10个字符且不含空格的字符串;题目保证队列中消息的优先级无重复,且输入至少有一个GET
。
输出格式:
对于每个GET
指令,在一行中输出消息队列中优先级最高的消息的名称和参数。如果消息队列中没有消息,输出EMPTY QUEUE!
。对于PUT
指令则没有输出。
输入样例:
9
PUT msg1 5
PUT msg2 4
GET
PUT msg3 2
PUT msg4 4
GET
GET
GET
GET
输出样例:
msg2
msg3
msg4
msg1
EMPTY QUEUE!
作者
DS课程组
单位
浙江大学
代码长度限制
16 KB
时间限制
150 ms
内存限制
64 MB
#include<stdio.h> #include<stdlib.h> #include<string.h> #define MAXNUM 10000; struct message { int priority; char name[20]; }; typedef struct message ElementType ; typedef struct HNode *Heap; /* 堆的类型定义 */ typedef Heap MaxHeap; struct HNode { ElementType *Data; /* 存储元素的数组 */ int Size; /* 堆中当前元素个数 */ int Capacity; /* 堆的最大容量 */ }; MaxHeap CreateHeap(int MaxSize){ MaxHeap H = NULL; H = (MaxHeap)malloc(sizeof(struct HNode)); H->Capacity = MaxSize; H->Data = (ElementType *)malloc(sizeof(ElementType)*(MaxSize+1)); H->Data[0].priority = MAXNUM; H->Size = 0; return H; } ElementType CreateElement(char *n,int pri) { ElementType M; strcpy(M.name,n); M.priority = pri; return M; } bool Insert(MaxHeap H,ElementType X) { if(H->Size == H->Capacity)return 0; int i = ++H->Size; for( ;H->Data[i/2].priority < X.priority; i/=2){ H->Data[i] = H->Data[i/2]; } H->Data[i] = X; return 1; } void DeleteMax(MaxHeap H) { if(H->Size == 0){ printf("EMPTY QUEUE!\n"); } else{ printf("%s\n",H->Data[1].name); int parent , child; parent = 1; ElementType temp = H->Data[H->Size--]; for( ;parent*2<=H->Size ; parent = child){ child = parent * 2; if(child!=H->Size&&H->Data[child+1].priority > H->Data[child].priority) child++; if(temp.priority > H->Data[child].priority)break; else H->Data[parent] = H->Data[child]; } H->Data[parent] = temp; } } int main() { int n; scanf("%d",&n); MaxHeap H = CreateHeap(n); char ops[20]; char names[20]; int pri; ElementType temp; for(int i=0 ; i<n ; i++){ scanf("%s",ops); if(ops[0]=='P') { scanf("%s",names); scanf("%d",&pri); Insert(H,CreateElement(names,pri*-1)); } else { DeleteMax(H); } } return 0; }