P1160 队列安排可能是很多人在洛谷遇到的第一道“名字带队列、实则考链表”的题。题面本身不难读N个同学排队1号先进队2号到N号依次插到某个已有同学的左边或右边最后再按规则删掉若干人输出剩下的人。但就是这道看起来像模拟的题我见过太多用vector硬刚然后超时的同学也见过链表写出来却因为头指针没更新一直WA的同学。这篇文章不打算复述题面而是从“为什么要用双向链表”“数组怎么模拟链表”“插入删除的边界坑”“出错后怎么定位”这几个角度把这道题完完整整拆一遍。不管你是打信息学竞赛还是单纯想补C数据结构基本功按这个思路走一遍都会有收获。1. 先看懂P1160的题面真正让你动手的只有三件事1.1 题面在说什么以及“队列安排”为什么和队列关系不大P1160的原始场景很简单老师要安排N个同学的队列先把1号同学放进去。从2号到N号每个同学入队的时候都会带着一条指令格式是“k p”意思是“我站到编号为k的同学左边p0或右边p1”。所有入队指令结束后还会有M条出队指令每条指令给一个编号x表示把x号同学移出队列如果x已经不在队列里这条指令就忽略不计。最后从左到右输出仍然留在队列里的同学编号。这里最容易混淆的点是它虽然叫“队列安排”但并不是标准的“队尾入队、队头出队”的队列。每一条插入指令都发生在队列中间某个人的旁边属于任意位置的插入删除也不是只能删队头而是删任意一个还在队里的编号。所以这道题真正考的不是“队列”这个数据结构而是“在一个线性序列中高效插入、删除、遍历”的能力。很多人一开始用队列的思维去想反而把自己绕进去了。1.2 用一个实际样例把整条链走一遍我拿这道题最常见的样例来说输入是这样的4 1 1 1 1 2 0 1第一行的4表示有4个同学。接下来三行是插入指令第2号同学插入到1号的右边第3号同学插入到1号的右边第4号同学插入到2号的左边。最后一行表示有1次删除删除编号为1的同学。逐步推演操作当前队列初始1号已经在队12号插入到1号右边1 23号插入到1号右边1 3 24号插入到2号左边1 3 4 2删除1号3 4 2最终输出就是“3 4 2”。这个推演过程看起来简单但它已经把链表里的“头节点变化”“中间插入”“删除节点”都覆盖到了。尤其是3号插入到1号右边那一步实际上插在了1号和2号中间这正是链表操作最核心的动作。1.3 数据范围里早就写好了答案方向P1160的N和M都能到100000时间限制通常也就1秒。这意味着如果你每次插入、删除都去数组里找位置再移动元素最坏情况下一次操作就要移动接近N个元素整体复杂度会到O(NM)也就是10^10级别任何OJ都扛不住。所以数据范围本身就在提示你必须找一个插入删除能做到常数时间的数据结构。顺着这个方向想自然就是链表。2. 为什么数组和vector会挂从复杂度倒推数据结构2.1 vector.insert/erase的隐藏开销很多人的第一版解法长这样用一个vector存当前队列插入时先find找到k的位置再调用insert删除时find到x再erase。本地小数据怎么跑都对一提交不是TLE就是WA。原因在于vector底层是连续内存。在中间插入或删除一个元素需要把该位置后面的所有元素整体向后或向前挪动一位。一次插入最坏要移动O(N)个元素N次插入就是O(N^2)后面还有M次删除整体直接到O(NM)。语言层面救不了换Python的list、Java的ArrayList也是一样。凡是“在序列中间频繁增删”的需求就必须跳出连续存储改走链式存储。2.2 双向链表为什么是正解以及为什么单向不行链表的特点是每个节点只记录左右邻居插入和删除都只需要改邻居的指针不需要移动任何人的位置。插入一个节点是O(1)删除一个已知编号的节点也是O(1)总体复杂度就是O(NM)和题目规模完全线性。那为什么必须用双向链表而不是单向因为指令要求“插到k的左边”。如果是单向链表你知道k的下一个是谁但想知道k前面那个人是谁必须从头遍历一遍双向链表每个节点同时存了left和right一步就能拿到前驱。这就是为什么这题需要的是双向链表。我把几种方案对比一下方案插入复杂度删除复杂度按编号定位遍历输出综合评价vector/数组O(N)O(N)O(1)O(N)总复杂度O(NM)必挂std::listO(1)O(1)需要额外映射O(N)可用但指针细节被隐藏std::setO(logN)O(logN)O(logN)O(N)也能过但不是最优思路数组模拟双向链表O(1)O(1)O(1)O(N)竞赛首选2.3 编号到节点的映射数组下标就是天然哈希实现双向链表时很多初学者会纠结链表节点是不是要new出来如果动态new节点怎么按编号快速找到这个人最简单的答案是因为编号正好是1到N的连续整数直接用编号当下标。开两个数组l和rl[3]表示编号3的同学左邻居是谁r[3]表示编号3的同学右邻居是谁。这样“按编号找到节点”就是O(1)的数组访问不需要哈希表也不需要指针。更重要的是后面的删除操作直接通过编号下标就能定位到节点这是动态链表做不到的便利。3. 数组模拟双向链表的完整实现与关键细节3.1 开局只有1号节点时的表示方法用数组模拟链表习惯上把0当作“空指针”。初始时队列里只有1号同学他的左边和右边都没有人所以写成l[1] 0; r[1] 0;同时需要一个head变量记录队头是谁初始head 1。后面所有插入删除都可能改变head所以head必须跟着更新。这里的0号是哨兵不是真实存在的节点代码里要避免写入l[0]或r[0]。3.2 插入到左边的四步指针操作插入的核心代码可以这样写const int MAXN 100005; int l[MAXN], r[MAXN]; bool removedFlag[MAXN]; int head 1; l[1] r[1] 0; for (int i 2; i n; i) { int k, p; cin k p; if (p 0) { // 将 i 插入到 k 的左边 int pre l[k]; if (pre ! 0) r[pre] i; l[i] pre; r[i] k; l[k] i; if (k head) head i; } // p 1 的情况下面再处理 }这段代码看着短但每一步都有意义。pre是k原来的左邻居。如果pre不是0那么pre原来的右边本来是k现在k左边多了个i所以pre的右边要改成i。接着设置i自己的左右左边是pre右边是k。然后让k的左指针指向i。最后如果k正好是队头说明i插到了整个队列的最前面head要更新成i。3.3 插入到右边的对称处理与两种边界p 1时是插入到k的右边逻辑完全对称int nxt r[k]; r[k] i; l[i] k; r[i] nxt; if (nxt ! 0) l[nxt] i;先记住k原来的右邻居nxt然后让k的右边变成ii的左边是ki的右边是nxt。最后如果nxt不是0就把nxt的左指针改成i。这里的边界是如果k原本是队尾nxt就是0此时i变成新的队尾就不需要去改l[0]。左右两种插入其实都可以总结成一句话先记住要插入位置前后的两个节点再把新节点“缝”进去。顺序通常是先改旧邻居的指针再改新节点自己的指针最后改目标节点k的指针。3.4 为什么“先存旧值再改指针”是铁律这个坑我至少见人踩过十次。有人写插入左边时会这样l[k] i; // 先改k的左指针 r[l[k]] i; // 这时的l[k]已经被覆盖成i了看起来是先给k找了个新左邻居i然后想更新原来左邻居的右边指针结果拿到的不是原来的左邻居而是i自己。链表操作里凡是你还需要用到的旧值必须提前存到临时变量里。pre和nxt就是干这个用的。这条铁律在你做其他链表题时同样适用凡是“需要用到即将被覆盖的旧数据”都要先保存。4. 删除操作里最容易致命的三个坑4.1 坑一重复删除导致链表彻底断掉删除阶段说的很清楚如果x已经不在队列中忽略。这句话是送分也是最大的陷阱。如果写成这样void removeNode(int x) { int L l[x], R r[x]; r[L] R; l[R] L; }第一次删除x没问题。但如果x之前已经被删了l[x]和r[x]依然保留着它被摘除那一刻的邻居信息。再次执行时会用这些已经过期的邻居去连接别人导致原本正确的链被拦腰截断甚至形成环输出阶段死循环。解决办法就是加一个标记数组bool removedFlag[MAXN];删除前先判断如果已经删过就直接continue否则完成删除后再标记。注意这个标记数组是全局默认初始化为false的不需要手动memset。4.2 坑二删除的是头节点时head没有同步更新比如当前队列是1-2-3head 1。现在删除1。正确的逻辑是1的左邻居是0右邻居是2那么删除后head应该变成2。但如果删除代码直接写r[l[x]] r[x]; l[r[x]] l[x];在删除头节点时l[x]是0代码会访问r[0]这是对哨兵节点的误操作而且head仍然是1输出时会发现这个节点明明已经被删了却还在链上或者更糟糕输出陷入死循环。所以删除时一定要单独判断if (pre 0) { head nxt; } else { r[pre] nxt; }pre是0说明x是现在的队头删除后它的右邻居nxt就成了新队头。4.3 坑三摘除节点时的“断链重连”必须双向一致双向链表删除一个节点要同时维护两个方向。完整的删除代码应该是int pre l[x]; int nxt r[x]; if (pre ! 0) r[pre] nxt; else head nxt; if (nxt ! 0) l[nxt] pre; removedFlag[x] true;很多人写完r[pre] nxt就忘了l[nxt] pre。这道题只要求从左往右输出所以少一步可能也能过但如果你以后需要反向遍历、找前驱、反转链表这个失误早晚会回来找你。链表操作的根基就是指针一致性每次都画一次图把两个方向都补上。4.4 队列被删空时的输出细节极端情况下N1并且M1最终队列会被删空。删除1号时pre是0nxt也是0所以head被更新成0。输出阶段从head0出发循环条件写成cur ! 0那么整个循环一次都不会执行直接输出一个换行。这种情况看起来简单但如果你在输出时用了“先输出第一个再循环输出后面的”这种写法就要格外小心因为队列可能为空。我习惯统一用for循环配合空格判断或者干脆允许末尾多一个空格多数OJ都能接受。当然想写严格格式也很简单vectorint ans; for (int cur head; cur ! 0; cur r[cur]) { ans.push_back(cur); } for (size_t i 0; i ans.size(); i) { if (i) cout ; cout ans[i]; } cout \n;5. 调试与验证在错误样例面前如何快速定位5.1 必须构造的几组边界数据很多人拿着题目样例跑对就以为自己AC了实际上P1160最大的威力在于边界情况。我建议至少构造以下几组数据每组的预期结果都要能手推出来第一组全部插到同一个人的左边验证head的更新。3 1 0 1 0 0过程初始是12号插入到1左边队列变成2 13号插入到1左边变成2 3 1。head先变成2再变成2最终输出2 3 1。第二组全部插到队尾右边验证队尾指针变化。3 1 1 2 1 0过程2号插到1右边队列1 23号插到2右边队列1 2 3。输出1 2 3。第三组删除头节点。3 1 1 1 1 1 1过程2号插到1右边队列1 23号插到1右边队列1 3 2。删除1队列3 2。输出3 2。第四组同一个编号删除两次。3 1 1 1 1 2 1 1第一次删除1队列3 2第二次删除1应该忽略。输出3 2。第五组删除尾节点。3 1 1 1 1 1 2队列先变成1 3 2删除2后输出1 3。第六组N1且M1。1 1 1初始只有1号删除1后队列为空输出只有换行。每组数据都拿纸手动推一遍再拿程序跑一旦结果对不上也就基本锁定了是哪个操作出了问题。5.2 打印整条链别靠眼睛推状态调试链表题最省事的手段就是写一个打印函数在每个关键操作后把整条链打出来void showQueue(int head) { for (int cur head; cur ! 0; cur r[cur]) { cout cur - ; } cout NULL\n; }在插入和删除的代码里临时调用配合单点打印l[3]、r[3]这类信息基本能立刻看到是哪个指针被改坏了。这个函数只依赖head和r数组输出的是从左到右的顺序足够覆盖本题所有需要观察的状态。遇到复杂问题再额外打印l数组往往能把双向连接问题也暴露出来。5.3 用暴力程序对拍比肉眼检查可靠得多如果想把验证做得更扎实可以写一个用vector模拟的暴力版本逻辑完全按照题面来不追求性能只追求正确。然后写一个随机数据生成器n和m限制在10以内插入的k保证是已经入队的编号删除的编号允许重复。用循环生成几千组随机数据分别跑暴力程序和链表程序比较输出是否一致。对拍的价值在于它能用极小的数据规模把各种情况密集地撞出来尤其是那些你根本想不到的边界组合。P1160很适合作为对拍的入门练习因为数据结构简单生成随机数据和比对的代码量都不大。一旦对拍跑了几千组没问题再交评测机基本就是一遍过。6. 从P1160延伸链表思想在算法和工程中的位置6.1 数组模拟链表的三种进阶形态P1160里用到的l、r数组是竞赛中最朴素的数组模拟链表。把这个思路稍微变形就能得到更多东西。第一个变形是邻接表把“每个节点只有一个前驱和一个后继”改成“每个点可以连多个后继”用head[cur]和next数组存边这是图论里最基础的存储方式。第二个变形是LRU缓存淘汰用双向链表维护访问顺序再用哈希表提供O(1)定位这正是LeetCode那道LRU Cache的解法。第三个变形是更复杂的区间维护比如某些平衡树操作的雏形。可以说P1160是理解这些高级结构的起点。6.2 当“队列”这个词被工程复用算法里的队列是两个指针维护的一个线性表到了实际工程里“队列”这个词被大量复用。线程池里的阻塞队列用来缓冲任务生产者把任务丢进去消费者按顺序取消息系统里的消息队列用来削峰填谷和解耦Kafka、RabbitMQ、RocketMQ这些都是消息队列的工程实现算法里还有单调队列专门用来优化滑动窗口最值问题。它们的共同点都是“先进先出”或“顺序处理”的抽象。但学P1160的时候不用急着去背消息队列的可靠性、幂等等概念把链表本身吃透才是根。我见过不少人连数组模拟链表都写不利索就开始讨论消息队列重复消费的问题实际上那是空中楼阁。6.3 做题之外的收获先画图再动键盘我自己最开始做这道题的时候也吃过head没更新的亏。那时候急着写代码l和r绕来绕去最后对着一个死循环不知所措。后来慢慢养成了一个习惯不管多简单的链表题先在草稿纸上画出三个节点把插入前后的“前驱-后继”关系用箭头标清楚再动键盘写代码。这个习惯帮我省下的调试时间比任何技巧都多。P1160代码量不大但逼着你把“指针修改顺序”“头尾边界”“重复操作的幂等性”一次想清楚这种思维在以后写任何涉及状态修改的程序时都用得上。做完这道题你会觉得链表不再是脑子里一团乱麻而是一张可以随时摊开看的图。