有 n 个人正在排队，每个人除了队首都只知道排在自己之前的人是谁，请你尝试还原出这个队列c++

下面是一个用 C++ 实现根据每个人所知道的排在自己之前的人来还原队列的代码： ```cpp #include <iostream> #include <vector> #include <unordered_map> // 函数用于还原队列 std::vector<int> restoreQueue(const std::vector<int>& pre) { int n = pre.size(); // 用于记录每个人的后继，即当前人后面是谁 std::unordered_map<int, int> next; int first = -1; // 遍历 pre 数组，构建 next 映射，并找出队首 for (int i = 0; i < n; ++i) { if (pre[i] == -1) { // 队首的 pre 值为 -1 first = i; } else { // 记录 pre[i] 的后继是 i next[pre[i]] = i; } } std::vector<int> queue; int current = first; // 从队首开始，按照后继关系依次加入队列 while (current != -1) { queue.push_back(current); // 找到当前人的后继 current = next.count(current) ? next[current] : -1; } return queue; } int main() { // 示例输入，pre[i] 表示排在第 i 个人之前的人的编号 std::vector<int> pre = {-1, 0, 1, 2}; std::vector<int> queue = restoreQueue(pre); // 输出还原后的队列 for (int person : queue) { std::cout << person << " "; } std::cout << std::endl; return 0; } ``` 代码解释 1. `restoreQueue` 函数： - 首先，创建一个 `unordered_map` 类型的 `next` 用于记录每个人的后继。 - 遍历 `pre` 数组，找到队首（`pre` 值为 -1 的人），并构建 `next` 映射。 - 从队首开始，按照后继关系依次将人加入队列，直到没有后继为止。 2. `main` 函数： - 提供一个示例输入 `pre` 数组。 - 调用 `restoreQueue` 函数还原队列。 - 输出还原后的队列。 额外需要注意的逻辑点 1. 输入的 `pre` 数组必须保证有且只有一个 -1，表示队首。 2. `pre` 数组中的编号必须在 0 到 `n - 1` 之间，其中 `n` 是人数。 3. 确保输入的 `pre` 数组能够形成一个有效的队列，即不会出现循环或断开的情况。 [2025-07-27 11:12:38 | AI写代码神器 | 644点数解答]