PTA 数据结构 Windows消息队列（优先队列）

傷城~ 2022-04-12 08:59 222阅读 0赞

7-7 Windows消息队列 （25 分）

消息队列是Windows系统的基础。对于每个进程，系统维护一个消息队列。如果在进程中有特定事件发生，如点击鼠标、文字改变等，系统将把这个消息加到队列当中。同时，如果队列不是空的，这一进程循环地从队列中按照优先级获取消息。请注意优先级值低意味着优先级高。请编辑程序模拟消息队列，将消息加到队列中以及从队列中获取消息。

### 输入格式: ###

输入首先给出正整数N（≤105），随后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!

这题一开始有一个测试点超时，加上std::ios::sync\_with\_stdio(false)关掉同步就好了。

#include <iostream>
    #include <cstdio>
    #include <cstdlib>
    #define OVERFLOW -1
    #define OK 1
    #define ERROR 0
    typedef int Status;
    typedef struct 
    {
        char name[15];
        int priority;
    }ElemType;
    typedef struct Heap
    {
        int capacity;
        int size;
        ElemType *data;
    }Heap,*PriorityQueue;
    void swap(ElemType &a,ElemType &b)
    {
        ElemType t = a;
        a = b;
        b = t;
    }
    void shiftdown(PriorityQueue pqueue, int i) //向下调整
    {
        while(i*2 <= pqueue->size)  //有左孩子
        {
            int IndexofMinChild = i*2;
            if(i*2 + 1 <= pqueue->size) //有右孩子
            {
                if(pqueue->data[i*2].priority > pqueue->data[i*2+1].priority)  //找孩子中最小的
                {
                    IndexofMinChild = i*2+1;
                }
            }
            if(pqueue->data[i].priority > pqueue->data[IndexofMinChild].priority)
            {
                swap(pqueue->data[i],pqueue->data[IndexofMinChild]);
                i = IndexofMinChild;
            }
            else
                break;
        }
    }
    void shiftup(PriorityQueue pqueue,int i)
    {
        while(i/2 >= 1)
        {
            if(pqueue->data[i/2].priority > pqueue->data[i].priority)
            {
                swap(pqueue->data[i/2],pqueue->data[i]);
                i /= 2;
            }
            else
                break;
        }
    }
    Status Init(PriorityQueue &pqueue,int n)
    {
        pqueue = (PriorityQueue)malloc(sizeof(Heap));
        if(!pqueue)
            exit(OVERFLOW);
        pqueue->data = (ElemType*)malloc(sizeof(ElemType)*(n+1));
        if(!pqueue->data)
            exit(OVERFLOW);
        pqueue->capacity = n;
        pqueue->size = 0;
        return OK;
    }
    Status Enqueue(PriorityQueue pqueue,ElemType e)
    {
        if(!pqueue->size)  //队列中没有元素
        {
            pqueue->data[1] = e;
            ++(pqueue->size);
            return OK;
        }
        int index = ++(pqueue->size);
        pqueue->data[index] = e;  //将e放到数组最后
        shiftup(pqueue,index);   //向上调整
        return OK;
    }
    bool Empty(PriorityQueue pqueue)
    {
        if(!pqueue->size)
            return true;
        return false;
    }
    Status Dequeue(PriorityQueue pqueue,ElemType &e)
    {
        if(Empty(pqueue))  //没有元素
            return ERROR;
        if(pqueue->size == 1)  //只有一个元素
        {
            e = pqueue->data[1];
            --(pqueue->size);
            return OK;
        }
        int IndexofLast = pqueue->size;
        e = pqueue->data[1];
        swap(pqueue->data[1],pqueue->data[IndexofLast]);  //将最后一个元素换到堆顶
        --(pqueue->size);
        shiftdown(pqueue,1);   //堆顶向下调整
        return OK;
    }
    
    int main()
    {
        std::ios::sync_with_stdio(false);
        PriorityQueue pqueue;
        char command[5];
        ElemType e;
        int n;
        std::cin >> n;
        Init(pqueue,n);
        while(n--)
        {
            std::cin >> command;
            if(command[0]=='P')
            {
                std::cin >> e.name >> e.priority;
                Enqueue(pqueue,e);
            }
            else if(command[0]=='G')
            {
                if(Empty(pqueue))
                    std::cout << "EMPTY QUEUE!" << std::endl;
                else
                {
                    Dequeue(pqueue,e);
                    std::cout << e.name << std::endl;
                }
            }
        }
        return 0;
    }