Problem J44: Message Queue / 消息队列

版权信息： · 优先队列模拟问题

任务总览

题目描述

在 Windows 系统中，每个进程都维护着一个消息队列。当系统中发生一些事件（例如鼠标点击、文本变更等）时，就会向进程的消息队列中添加消息。

本题要求你模拟这样一个消息队列系统，支持以下两类命令：

• PUT <消息名称> <参数> <优先级>：将一条消息发送到消息队列；
• GET：从消息队列中获取一条消息。

优先级说明：

• 数值越小表示优先级越高；
• 若多条消息具有相同优先级，按其进入队列的先后顺序（FIFO）处理。

输入格式

输入为多行命令，最多不超过 60000 条。每行命令格式如下：

• GET：从队列中获取一条消息；
• PUT msg 参数 优先级：将消息放入队列，其中：
  • msg 为消息名称（字符串）；
  • 参数 为整数；
  • 优先级 为整数。

输出格式

• 对于每一个 GET 命令：
  • 若队列为空，输出一行：EMPTY QUEUE!；
  • 否则输出消息名称与参数，格式为：msg 参数；
• PUT 命令不产生输出。

输入输出样例

输入示例

GET
PUT msg1 10 5
PUT msg2 10 4
GET
GET
GET

输出示例

EMPTY QUEUE!
msg2 10
msg1 10
EMPTY QUEUE!

题目分析与解法

✅ 模拟方法：

1. 建立消息结构体，包含：消息名称、参数、优先级、插入序号（用于 FIFO）；
2. 维护一个支持优先级排序的队列（推荐使用 std::priority_queue 或手动排序）；
3. 对于 PUT 操作：
   • 将消息加入队列；
   • 插入时记录其顺序编号（可用计数器递增）；
4. 对于 GET 操作：
   • 若队列非空，取出当前优先级最高且最早加入的消息；
   • 若队列为空，输出 EMPTY QUEUE!。

边界细节说明

• 同一消息内容可以重复出现在队列中；
• 如果优先级相同，应按照先入先出原则处理；
• 命令数量最大为 60000，需考虑效率；
• 消息名称不包含空格。

时间复杂度分析