第 5 周动手做总结_数据结构_队列与应用-id:45 C. DS 队列 - 组队列

题目描述

组队列是队列结构中一种常见的队列结构，在很多地方有着广泛应用。组队列是是指队列内的元素分组聚集在一起。组队列包含两种命令：

1. ENQUEUE，表示当有新的元素进入队列，首先会检索是否有同一组的元素已经存在，如果有，则新元素排在同组的最后，如果没有则插入队列末尾。

2. DEQUEUE，表示队列头元素出队

3. STOP，停止操作

建议使用C++自带的队列对象queue，编程更方便

输入

第1行输入一个t(t<=10)，表示1个队列中有多少个组

第2行输入一个第1组的元素个数和数值

第3行输入一个第2组的元素个数和数值

以此类推输入完t组以定义同组元素之后，开始输入多个操作命令(<200)，对空的组队列进行操作，例如输入ENQUEUE 100，表示把元素100插入队列

输出

DEQUEUE出队的元素

输入样例

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

输出样例

101 102 103

提示

可以看到队列分组，先入队的组在队列中靠前，出队也靠前：

DEQUEUE 输出 201，队列变为 | 203 | 301 302 | 102 101 | …

题解

主要的是要注意输入进来的数要按照分组依据压进新的队列，而且是先进先出，而不是按之前的队列的分组进不同的位置，因为是队列，如果该元素不属于任何现有组，插入到最后一位

代码实现

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main()
{
    int t, i, n, j, item, num, f, k;
    string type;
    queue<int> myQA[10];   // 存储原始组
    vector<queue<int>> myQB;   // 用于按组存储已插入的元素

    cin >> t;
    f = 0; // 第一次DEQUEUE输出标志

    // 读取每个组的元素
    for (i = 0; i < t; i++)
    {
        cin >> n;
        for (j = 0; j < n; j++)
        {
            cin >> item;
            myQA[i].push(item);  // 将元素插入原始组
        }
    }

    while (cin >> type)
    {
        if (type == "STOP")
        {
            break;
        }
        else if (type == "ENQUEUE")
        {
            cin >> num;
            bool inserted = false;

            // 遍历每个组，检查该元素是否属于该组
            for (i = 0; i < t; i++)
            {
                queue<int> temp = myQA[i];  // 复制组队列
                while (!temp.empty())
                {
                    if (temp.front() == num)  // 找到该元素所属的组
                    {
                        // 查找是否已经存在该组的队列
                        for (auto& q : myQB) // 遍历myQB中的每个队列q
                        {
                            if (!q.empty() && q.front() == myQA[i].front())
                            {
                                q.push(num);    // 将元素插入对应组的队列
                                inserted = true;
                                break;
                            }
                        }
                    }
                    temp.pop();
                }
                if (inserted)
                {
                    break;
                }
            }

            // 如果该元素不属于任何现有组，插入到新的队列
            if (!inserted)
            {
                queue<int> newGroupQueue;
                newGroupQueue.push(num);
                myQB.push_back(newGroupQueue);
            }
        }
        else if (type == "DEQUEUE")
        {
            k = 0;
            // 查找第一个非空队列并出队
            while (k < myQB.size() && myQB[k].empty())
            {
                k++;
            }
            if (k < myQB.size())
            {
                if (f == 0)
                {
                    cout << myQB[k].front(); // 首次输出
                    f = 1; // 标记首次输出
                }
                else
                {
                    cout << " " << myQB[k].front(); // 后续输出
                }
                myQB[k].pop(); // 出队

                // 如果队列已空，移除该队列
                if (myQB[k].empty())
                {
                    myQB.erase(myQB.begin() + k);
                }
            }
        }
    }
    cout << endl;

    return 0;
}