POJ 2259 Team Queue：隊列模擬與鏈表優化

問題描述

模擬「團隊隊列」：每個元素屬於某個團隊。入隊時，若隊列中已有同團隊成員，則插入到該團隊最後一名成員之後；否則加入隊尾。出隊按正常隊列順序（隊頭優先）。

數據結構設計

• 團隊鏈表：每個團隊維護一個鏈表，存儲其成員在全局隊列中的節點，支持 O(1) 尾部插入。
• 全局隊列順序：用一個隊列（或鏈表）記錄「有成員在隊列中的團隊」的順序。
• 元素→團隊映射：數組 team_id[element] 快速查找所屬團隊。
• 團隊狀態標記：in_queue[team] 標記團隊是否已在全局隊列中。

操作流程

ENQUEUE x

1. 查找 t = team_id[x]。
2. 若 !in_queue[t]：將團隊 t 加入全局隊列尾部，創建新鏈表節點，in_queue[t]=true。
3. 否則：在團隊 t 的鏈表尾部插入新節點。

DEQUEUE

1. 取全局隊列頭部團隊 t。
2. 彈出團隊 t 鏈表的頭節點，輸出其元素值。
3. 若團隊 t 鏈表變空：將 t 從全局隊列移除，in_queue[t]=false。

代碼實現（簡化版）

struct Node { int val; Node* next; };
Node* team_head[1001], *team_tail[1001];
int team_of[1000000];
queue global_q;
bool in_q[1001];

void enqueue(int x) {
    int t = team_of[x];
    Node* node = new Node{x, nullptr};
    if (!in_q[t]) {
        in_q[t] = true;
        global_q.push(t);
        team_head[t] = team_tail[t] = node;
    } else {
        team_tail[t]->next = node;
        team_tail[t] = node;
    }
}

int dequeue() {
    int t = global_q.front();
    Node* node = team_head[t];
    int val = node->val;
    team_head[t] = node->next;
    delete node;
    if (!team_head[t]) {
        global_q.pop();
        in_q[t] = false;
    }
    return val;
}

關鍵細節

• 多測試用例：每個 case 重置所有數據結構。
• 元素範圍 0~999999，團隊數 ≤ 1000，用數組映射 O(1)。
• 輸出格式：每個 case 前輸出 Scenario #k，每次 DEQUEUE 輸出一行，case 間空行。

總結

Team Queue 是典型的「多隊列合併」模擬題。核心在於維護「團隊內部順序」與「團隊全局順序」兩層結構，鏈表+隊列配合實現 O(1) 入隊出隊。注意初始化與邊界條件（空隊列、單元素團隊）。