解题思路
本题是双队列模拟:维护缓冲区 buffer(待移入发送区)与发送区 send_q(按进入发送区的先后顺序排队),并用集合 in_buffer 记录当前缓冲区里有哪些编号,以 O(1) 判断 RECEIVE 是否重复。
核心操作 flush:当 SEND/QUERY 需要访问发送区但发送区为空、缓冲区非空时,把缓冲区全部按 FIFO 依次移入发送区,并从 in_buffer 中删除对应编号。
逐条处理指令:
- RECEIVE x:仅当 x∈in_buffer 时失败输出 −1;否则入队缓冲区并输出 x。已在发送区、不在缓冲区的编号可以再次接收(易错点)。
题目内容
某网络设备采用收发机制管理数据包,该机制包含两个区域:缓冲区和发送区,并支持以下指令:
-
RECEIVE x:接收到编号为 x 的数据包。具体规则如下:
- 如果缓冲区没有该编号的数据包,则接收成功,将其存入缓冲区,输出数据包编号
- 如果缓冲区存在该编号的数据包,则接收失败,输出 −1
-
SEND:发送一个数据包。具体规则如下:
- 如果发送区不为空,则从发送区取出一个最早的数据包发送,输出数据包编号
- 如果发送区为空但缓冲区不为空,则将缓冲区中的所有数据包转移到发送区,然后取出最早接收的数据包进行发送,输出数据包编号
- 如果两个区域都为空,则输出 0
-
QUERY:查询最早接收但尚未发送的数据包编号。具体规则如下:
- 如果发送区不为空,则输出发送区中最早的数据包编号
- 如果发送区为空但缓冲区不为空,则将缓冲区中的所有数据包转移到发送区,然后输出最早接收的数据包编号
- 如果两个区域都为空,则输出 0
输入描述
接收到的指令集。
输出描述
对指令处理输出的结果集。
补充说明
- 数据范围
- 指令集数量n:1≤n≤100
- 数据包编号x:1≤x≤1000
- 输入的所有指令格式保证合法
样例1
输入
["RECEIVE 1","RECEIVE 2","QUERY","SEND","QUERY","SEND"]
输出
[1,2,1,1,2,2]
说明
- RECEIVE 1:缓冲区无重复数据包,接收成功,输出 1
- RECEIVE 2:缓冲区无重复数据包,接收成功,输出 2
- QUERY:发送区为空,将缓冲区数据移至发送区,最早接收 1,输出 1
- SEND:发送区 [1,2],发送并输出 1
- QUERY:发送区剩余 2,输出 2
- SEND:发送区剩余 2,发送并输出 2
样例2
输入
["RECEIVE 3","RECEIVE 3","SEND","SEND","SEND"]
输出
[3,-1,3,0,0]
说明
- RECEIVE 3:缓冲区无重复数据包,接收成功,输出 3
- RECEIVE 3:缓冲区存在重复数据包,接收失败,输出 −1
- SEND:发送区为空,将缓冲区数据移至发送区,发送并输出 3
- SEND:发送区和缓冲区均为空,输出 0
- SEND:发送区和缓冲区均为空,输出 0
样例3
输入
["RECEIVE 1"]
输出
[1]
说明
- RECEIVE 1:缓冲区无重复数据包,接收成功,输出 1