【队列安排】题解

题干信息解读
老师要将班上 N 个同学排成一列，同学编号为 1~N，具体操作如下：
1.先将 1 号同学安排进队列。
2.从 2 号到 N 号同学依次入列，每次入列时，老师会指定该同学站在之前已入列同学的左边或右边。
3.之后从队列中去掉 M 个同学，其他同学位置顺序不变。老师想知道最终队列从左到右所有同学的编号。

整体做题思路
数据结构选择：使用双向链表来维护队列，因为双向链表可以在 O (1) 时间复杂度内完成插入和删除操作。
插入操作处理：对于每个同学的插入，根据指定的位置，在双向链表中找到对应的位置进行插入。
删除操作处理：对于每个删除指令，在双向链表中找到对应的同学并删除，同时处理好前后节点的指针关系。

题目中的难点和注意事项
插入操作细节：在插入新同学时，需要注意维护双向链表的指针关系，确保插入后链表结构正确。
删除操作处理：删除同学时，要检查该同学是否已被删除，避免重复删除。
边界情况处理：处理好链表为空或只有一个节点的情况，避免出现指针错误。

AC代码（如有雷同，纯属巧合）

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

struct Node {
    int val;
    Node* prev;
    Node* next;
    Node(int x) : val(x), prev(nullptr), next(nullptr) {}
};

int main() {
    int N;
    cin >> N;
    
    // 创建1号节点
    Node* node1 = new Node(1);
    vector<Node*> nodes(N + 1, nullptr);  // 存储每个编号对应的节点指针
    nodes[1] = node1;
    
    // 处理2到N号同学的插入
    for (int i = 2; i <= N; ++i) {
        int k, p;
        cin >> k >> p;
        
        Node* newNode = new Node(i);
        nodes[i] = newNode;
        
        Node* kNode = nodes[k];
        
        if (p == 0) {  // 插入到k号同学左边
            newNode->next = kNode;
            newNode->prev = kNode->prev;
            if (kNode->prev) {
                kNode->prev->next = newNode;
            }
            kNode->prev = newNode;
            // 如果k是头节点，更新头节点
            if (kNode == node1) {
                node1 = newNode;
            }
        } else {  // 插入到k号同学右边
            newNode->prev = kNode;
            newNode->next = kNode->next;
            if (kNode->next) {
                kNode->next->prev = newNode;
            }
            kNode->next = newNode;
        }
    }
    
    // 处理删除操作
    int M;
    cin >> M;
    vector<bool> deleted(N + 1, false);  // 标记每个同学是否已被删除
    
    for (int i = 0; i < M; ++i) {
        int x;
        cin >> x;
        
        if (x < 1 || x > N || deleted[x]) {
            continue;  // 同学不存在或已被删除，忽略
        }
        
        Node* xNode = nodes[x];
        if (xNode->prev) {
            xNode->prev->next = xNode->next;
        } else {
            // xNode是头节点，更新头节点
            node1 = xNode->next;
        }
        
        if (xNode->next) {
            xNode->next->prev = xNode->prev;
        }
        
        deleted[x] = true;
    }
    
    // 输出最终队列
    Node* current = node1;
    bool first = true;
    while (current) {
        if (!first) {
            cout << " ";
        }
        cout << current->val;
        first = false;
        current = current->next;
    }
    cout << endl;
    
    // 释放内存
    current = node1;
    while (current) {
        Node* next = current->next;
        delete current;
        current = next;
    }
    
    return 0;
}

时间复杂度和空间复杂度
时间复杂度：插入操作和删除操作的时间复杂度均为 O (1)，因此总的时间复杂度为 O (N + M)，其中 N 是同学的数量，M 是删除的操作次数。
空间复杂度：主要用于存储双向链表的节点，空间复杂度为 O (N)。