java - 实现一个队列，您可以在其中在特定位置插入元素，同时在恒定时间内入队/出队？

Question

示例输入:

2
3 101 102 103
3 201 202 203
ENQUEUE 101
ENQUEUE 201
ENQUEUE 102
ENQUEUE 202
ENQUEUE 103
ENQUEUE 203
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
STOP

第一行=“组”的数量，N

接下来的 N 行 = 第一个数字是组 K 中元素的数量，接下来的 K 个数字是元素本身(在 0...999999 范围内)

STOP 输入之前的所有行 = Enqueue 或 Dequeue 查询。如果入队，则将当前正在处理的元素 E 排入队列末尾的 A. 如果队列中没有元素与 E 或 B. 属于同一“组”，就在最后一个元素之后与 E 属于同一个“组”

出队很简单，只需从队列中删除第一个元素。对于每个出队查询，输出出队的元素。

元素的入队和出队应该只花费常数时间

输出将是:

101
102
103
201
202
203

我最初考虑的是某种二维嵌套结构，例如队列数组之类的，但是入队/出队不会花费恒定的时间，所以我不确定。

此外，我在查询之前就已经给出了元素本身这一事实应该是一个提示，但对于我不确定的内容。

Answer 1

如果组不相交，则每个组中的元素总是聚集在一起。换句话说，你有一个队列队列:

• 为每个组创建一个(最初为空)队列；
• 创建一个索引结构，对输入的数字对应的组进行恒时搜索(暴力破解是一个1000000个引用的数组，可以改成HashSet)；
• 创建队列引用队列(“主”队列)。

现在 ENQUEUE X

• 为X找到对应的队列；
• 向其中添加X；如果为空，则将队列加入主队列。

对于DEQUEUE

• 取出主队列中的第一个队列，从中取出元素；
• 如果为空，则将该队列从主队列中取出。