poj2259.团队队列

标答

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

queue<int> Q;        
queue<int> q[1010];  
int team[1000000];   // team[i] 表示成员 i 属于哪个团队

int main() {
    ifstream in("in.txt");
    string op;
    int t;

    in >> t;  // 读取团队数量
    for (int i = 1; i <= t; i++) {
        int n, x;
        in >> n;  // 读取团队成员数量
        for (int j = 1; j <= n; j++) {
            in >> x;      // 读取成员编号
            team[x] = i;  // 将成员 x 归属到团队 i
        }
    }

    in >> op;  // 读取操作
    while (op != "STOP") {
        if (op == "ENQUEUE") {
            int x;
            in >> x;  // 读取要入队的成员编号
            if (q[team[x]].empty()) {  // 检查该团队是否为空
                Q.push(team[x]);  // 如果为空，将团队入队
            }
            q[team[x]].push(x);  // 将成员 x 入队
        } else {  // 如果操作是 DEQUEUE
            // DEQUEUE 的内容一定是 Q 里第一个团队的第一个元素
            cout << q[Q.front()].front() << endl;  // 输出队列头部成员
            q[Q.front()].pop();  // 移除队列头部成员
            if (q[Q.front()].empty()) {  // 如果这个团队没有成员了，就出队
                Q.pop();
            }
        }
        in >> op;  // 读取下一个操作
    }
    
    return 0;
}

• 用team[x]来达到快速获取x所在团队的目的（但是team声明的容量要很大）

• q是一个数组 而非一个队列，q的每一个元素都是一个队列 ！
  q只用来存储已经被ENQUEUE的成员，它不管被ENQUEUE的顺序，而是只根据team[x]为下标，把每个成员入到其所属的团队的队列q[team[x]]的队尾

• 队列Q是用来控制顺序的。Q中先入队的int整数 代表的是排在前面的团队的编号

• q和Q分工互补，一个管入队和查询是否有同伴,一个管给团队排序,这是队列的一种思想！

  我的思路

1. 一个总队列，它的每一个结点是一个团队链表的首结点
2. ENQUEUE：遍历总队列的每一个结点，如果有与要插入结点的flag相同的首结点，就入到其所在的链表的尾部；如果没有，就插入总队列尾部作为一个新结点

---

勘误

1. **用vector<vector<int»二维数组可能导致的疏忽 **

你的代码问题出现在这一行：

vec[z][x] = val;

此时 vec[z] 并没有被初始化为大小为 n 的 vector，因此你在访问 vec[z][x] 时会出现越界错误。

你可以在读取 n 之后，使用 resize 方法初始化 vec[z] 的大小，如下：

for (int z = 0; z < N; z++) {
    int n;
    cin >> n;
    vec[z].resize(n);  // 初始化 vec[z] 的大小为 n
    for (int x = 0; x < n; x++) {
        int val;
        cin >> val;
        vec[z][x] = val;            
    }
}

1. 指针初始化

你的代码目前存在几个潜在问题和需要修正的地方：

1. head 没有初始化：

你声明了一个指针 node* head;，但没有对它进行初始化。此时 head 的值是未定义的，可能会导致程序崩溃。你应该在主函数开始时初始化 head，例如：

node* head = new node();

2. DEQUEUE 操作中的链表操作存在问题：

在 DEQUEUE 操作中，你使用 head->next_back 访问头节点的下一个元素，但当 head 只指向一个节点或者没有下一个节点时，这样的操作会导致空指针异常。

修正： 你应该先检查链表是否为空，然后再进行出队操作，并且需要确保正确的链表更新。可以这样修改：

else if(str=="DEQUEUE"){
    if(head->next_back == nullptr){
        cout << "Queue is empty" << endl;
    } else {
        node* p = head->next_back;
        cout << p->data << endl;

        // 更新 head 的 next_back，指向 p 的 next_up
        head->next_back = p->next_up;

        // 如果还有下一个队列节点，更新它
        if(head->next_back != nullptr) {
            head->next_back->next_back = p->next_back;
        }
        delete p;  // 删除 dequeued 的节点
    }
}

3. 在 ENQUEUE 时，没有处理初始空链表的情况：

当 head 为空时（也就是链表还没有任何元素时），p->next_back 的访问会出错。需要处理 head 是空链表的情况。

修正： 你应该在 ENQUEUE 时检查 head 是否指向空链表，若是空链表，则将 s 直接插入到 head->next_back：

if(head->next_back == nullptr){ 
    head->next_back = s; 
} else {
    // 这里放原有的遍历和插入逻辑
}

以上只是细节（如指针导致的运行时错误）的勘误，下面是思路上的勘误

---

思路的勘误

1. DEQUEUE的代码没有考虑到p->next_up==NULL的情况，导致少输出

---

细节

c++有deque容器，也有queue容器
![[Pasted image 20241009214401.png]]