如果你在PTA上刷到“猴子选大王”这道题第一反应多半是这不就是约瑟夫问题吗没错它确实是。但这道题之所以被放进“队列算法设计”这一类里背后其实藏着一个非常关键的思路转变——你不需要用链表去模拟那个圈也不用开一个布尔数组反复扫描谁还活着一个先进先出的队列就能把“围成一圈轮流报数、报到3出局”的完整过程自然地演出来。这篇文章想写给正在刷PTA、被队列章节折磨的同学也写给初学数据结构、对“入队出队到底有什么用”感到困惑的读者。我会以“猴子选大王”为具体场景把题目拆开讲清楚为什么队列适合这个模型给出可以直接提交的C语言代码再把边界条件、复杂度、常见Bug和进阶解法一次说透。默认题目规则是n只猴子编号1到n从1号开始报数报到3的猴子淘汰下一只猴子重新从1报数循环直到只剩一只它就是大王。如果你的题目把“3”改成了变量m思路完全一样把代码里的常量改成读入的变量即可。1. 题目拆解猴子选大王到底在考什么1.1 一个经典问题换了个马甲猴子选大王这道题几乎所有刷过PTA的人都会遇到但它并不是一道“新题”。早在公元1世纪犹太历史学家约瑟夫斯就记载过一个类似的传说一群士兵围成圈每隔一定人数就处死一人最后幸存者的位置成为著名数学问题“约瑟夫问题”。猴子选大王就是把这段残酷历史包装成了小朋友能接受的童话版本n只猴子围成一圈从1号开始报数报数到3的猴子淘汰出圈剩下的猴子继续围成圈报数直到场上只剩一只猴子它就是猴王。很多同学看到这个题的第一反应是“模拟”第二反应是“用链表”。但通过标题里的“队列算法设计”几个字出题人已经给了非常明确的暗示这道题希望你用队列这个数据结构去解。用队列的关键不是把猴子“围成一圈”存成环而是把“轮流报数”这个动作翻译成“队头出队、判断后决定是重新入队还是彻底淘汰”。这是从过程模拟到结构抽象的思维升级。理解了这一点后面所有代码都顺了。先用最朴素的语言理解题意输入一个正整数n输出最后那只猴子的编号。整个过程可以抽象为反复执行三件事——取队首猴子、让它报数、根据报数结果决定它的去留。这三件事对应的正是队列的两个核心操作出队dequeue和入队enqueue。1.2 为什么这道题会出现在队列章节里如果你只用数组加一个“淘汰标记”来模拟也不是不行代码还能写得更短。但队列在这个场景里体现的是“结构与逻辑的一致性”。猴子围成的圈本质上是一个逻辑上的循环序列而队列的先进先出特性配合“出队后重新入队”这个操作正好可以在物理上把一个线性队列变成逻辑上的环。举个例子食堂排队打饭第一个来的人排在最前面打到饭后离开后面的人依次往前。在猴子选大王里队列前面的猴子先报数报数没到3的猴子并不离开而是绕到队尾继续排队等待下一轮轮到自己。你看这就是标准的FIFO行为。如果报数到了3这只猴子就不再入队相当于从队伍里被移除了。所以这道题放在队列章节不是为了给约瑟夫问题加一层无意义的包装而是用猴子报数这个生动场景让学习者体会到“队首出队 队尾入队”如何自然地表达循环过程。这也是为什么我建议同学们不要一上来就套数学公式而是先老老实实用队列跑一遍等真的理解了操作过程再去研究更高级的算法。1.3 看清输入输出和数据规模PTA上的这题输入一般是一行一个正整数n输出一行一个整数表示猴王编号。常见版本里n的范围大概在1000到1000000之间不同题源会不一样。我见过有的版本把报数上限也作为输入比如一行两个整数n和m那么代码里把3换成m就行。这里有一个容易忽略的点如果n只有1只猴子还需要模拟吗不需要直接输出1。如果n等于2按规则1号报1入队2号报2入队1号再报3被淘汰剩下2号当大王。这些极限数据不是刁难你而是帮你检验程序是否会在特殊输入上崩溃。我后面专门用一节来列这些边界情况提交前最好自己先在心里跑一遍。2. 核心思路用队列的入队和出队模拟报数2.1 队列的先进先出和报数过程到底怎么对应队列这种数据结构生活里最典型的就是排队。新来的站到队尾处理完的从队头离开先来先服务。这个“先进先出”特性用在猴子选大王上特别自然。把当前还在圈内的所有猴子按报数顺序排成队列一开始队列顺序就是1、2、3一直到n。每一轮报数本质上是取队头这只猴子它报出当前计数然后看这个数是不是3。如果没到3它虽然报完数但并没有被淘汰于是它应该跑到队列末尾去等待下一轮重新轮到它如果它报的数刚好是3那么它被淘汰直接离开队列不再回来。你发现没有“取队头猴子”就是出队“跑回队尾等待下一轮”就是入队。一次完整的报数过程在队列层面就是一次“先出队、再决定是否入队”的操作。循环往复队列长度不断减小直到队列只剩一个元素那个元素就是猴王编号。很多人在这一步卡住是因为总想着“怎么模拟圆圈的形成”。其实不用刻意去模拟圈只要保证“下一只需要报数的猴子始终在队头”逻辑上它就是一个圈。队列里的元素顺序会随着不断出队入队而循环滚动这比“手动维护指针去找下一个存活节点”要直观得多。2.2 报数、淘汰、循环三个动作的队列语义把整个模拟过程拆成细粒度动作可以整理成下面这张表后面写代码时每一个分支都是从这里映射过去的报数结果队列操作含义报数 count 3队头出队然后从队尾入队猴子仍在圈内轮到下一只继续报数报数 count 3队头出队不再入队猴子被淘汰圈内猴子数量减一报数完成后 count 重置计数器归零下一只猴子从1开始重新报数这里面最容易写错的是计数器的重置时机。正确逻辑是队头猴子出队后先把报数计数器加1然后判断它报的数是否是3。如果是3出队后不用再入队同时把计数器重置为0如果不是3出队后要立刻重新入队但计数器保持累加状态因为下一次报数的猴子接着报count1。还有一个关键的细节当队头猴子被淘汰时它的下一位自动成为新的队头下一轮报数从1开始所以计数器必须归零。如果漏掉这一步程序会随机出错输出的猴王编号完全不对。计数器是整个模拟的灵魂我建议在写代码前先在草稿纸上跑一遍n5的过程梳理清楚count到底应该在哪个环节加、哪个环节清零。2.3 队列选型循环数组、链式队列还是暴力数组同样是队列实现方式有好几种PTA提交时怎么选主要看数据规模和自己的熟练度。第一种是循环数组队列。用一个连续数组加head、tail两个指针入队时tail后移出队时head后移遇到数组末尾就取模回到开头。这种方案速度最快代码也不难写适合n确定且内存可控的题。它的缺点是容量需要提前估算数组开太小会越界开太大又浪费空间。第二种是链式队列。用结构体Node表示节点维护front和rear两个指针动态分配和释放节点。好处是不用担心容量队列想多长就多长逻辑也更贴近课堂上学到的“队列标准操作”。缺点是每次都malloc和free常数开销比数组大而且指针操作容易写错内存泄漏更是新手重灾区。第三种是直接用数组做“存活标记”写起来最快但它并没有用到队列思想不符合这道题“队列算法设计”的训练目标。我见过不少同学用这种方法偷懒结果一遇到n很大的变体题目循环里反复从头扫描数组时间复杂度直接爆炸。我在PTA上一般推荐循环数组队列理由很简单题目数据范围明确数组开到位就不怕运行时间也稳定。但为了让你真正吃透队列操作下面我会把数组版本和链式版本都写出来。两者核心思想完全一致区别只是在“容器”的物理实现上。3. 代码实现从思路到可提交的PTA代码3.1 循环数组队列的完整实现先给出最推荐的循环数组版本。这里把报数上限默认成3如果你想改成m把代码里的3换成读入的变量即可。#include stdio.h #define MAXN 1000005 int queue[MAXN]; // 循环队列数组 int head, tail; // 队头下标、队尾下标 int main() { int n, i; scanf(%d, n); // 初始化队列猴子编号1~n依次入队 head 0; tail 0; for (i 1; i n; i) { queue[tail] i; tail (tail 1) % MAXN; } int count 0; // 报数计数器 // 当队列中至少还有2只猴子时继续模拟 while ((tail - head MAXN) % MAXN 1) { int monkey queue[head]; // 取出队头猴子 head (head 1) % MAXN; // 队头出队 count; // 这只猴子报数 if (count 3) { count 0; // 报到3淘汰不再入队 } else { // 没被淘汰重新从队尾入队 queue[tail] monkey; tail (tail 1) % MAXN; } } // 队列中只剩一只猴子输出它 printf(%d\n, queue[head]); return 0; }这段代码的核心就是while循环。每一轮循环做一次“出队判断”相当于一只猴子报了一次数。当队列剩余元素大于1时循环继续只剩一个元素时它必然是猴王。注意循环队列的判断在循环数组里head和tail都是下标通过取模实现环形移动。判断队列长度的公式是(tail - head MAXN) % MAXN。为什么要加MAXN再取模因为tail可能小于head直接用tail-head会出现负数。加上MAXN后再取模保证结果一定是非负的队列长度。这个公式建议背下来很多循环队列题目都会用到。3.2 链式队列版本结构体和指针操作如果不喜欢固定数组或者想练练链式队列的建立、入队、出队可以用下面这个版本。它同样能通过PTA的测试点只是运行速度略慢。#include stdio.h #include stdlib.h typedef struct Node { int data; struct Node *next; } Node; int main() { int n, i; scanf(%d, n); Node *front NULL, *rear NULL; // 队头、队尾指针 // 1~n依次入队 for (i 1; i n; i) { Node *node (Node*)malloc(sizeof(Node)); node-data i; node-next NULL; if (rear NULL) { front rear node; } else { rear-next node; rear node; } } int count 0; // 队列中至少剩2个节点时继续 while (front-next ! NULL) { Node *cur front; // 当前报数的猴子 front front-next; // 出队 count; if (count 3) { count 0; free(cur); // 淘汰 } else { cur-next NULL; // 重新入队 rear-next cur; rear cur; } } printf(%d\n, front-data); return 0; }链式队列版本里每次报数时有一个节点先出队如果没到3就把它接到队尾。注意把cur接到队尾之前必须把cur-next置为NULL否则这个节点可能还残留着指向下一个节点的指针破坏链表结构。特别提醒这个版本手动malloc后又free了被淘汰的节点内存管理要小心不要重复free。在PTA评测环境下即使有一点点内存泄漏通常也不会判错但养成好习惯总没错。3.3 用一张模拟表看懂队列状态变化光看代码还是不够直观我以n5为例把队列操作过程完整列出来。这里的“操作后队列”指的是下一步即将轮到谁报数的顺序。轮次队首猴子报数操作操作后队列第1轮11出队后入队2 3 4 5 1第1轮22出队后入队3 4 5 1 2第1轮33出队后淘汰4 5 1 2第2轮41出队后入队5 1 2 4第2轮52出队后入队1 2 4 5第2轮13出队后淘汰2 4 5第3轮21出队后入队4 5 2第3轮42出队后入队5 2 4第3轮53出队后淘汰2 4第4轮21出队后入队4 2第4轮42出队后入队2 4第4轮23出队后淘汰4最终队列只剩4号所以n5时猴王是4。这个结果可以用约瑟夫问题的递推公式验证也可以自己在草稿纸上推一遍。我强烈建议你动手画一遍这个过程不要只看表格。画过一遍之后你对“出队、入队、淘汰”这三种操作的边界理解会完全不同。4. 细节打磨边界条件、复杂度与常见坑4.1 特殊输入的测试点提交前一定要先测几个特殊值。第一个是n1。队列里只有1号猴子while循环条件“队列至少2个元素”一开始就不成立直接输出队头1程序不会崩溃。第二个是n2。过程是1号报1入队2号报2入队1号再出队时报到3被淘汰队列里剩2号输出2。你可以看到即使只剩两只猴子也需要反复循环好几轮才能决出胜负因为报数到3不是每次都能命中。第三个是n3。推演结果是1、2报数后都入队3报数淘汰剩下1、2后1报1入队2报2入队1报3淘汰最后剩2号。所以n3时输出2。这些特殊值不是瞎猜的是检验实现是否正确的第一道关卡。很多同学代码写完第一版直接拿n10去测结果错了也不知道错在哪因为输出结果没有“标准答案”可以参考。先跑这些简单用例能快速定位问题在计数器、循环条件还是队列操作上。4.2 时间复杂度与空间复杂度以及大n时的优化循环数组版本的时间复杂度是O(n)更准确地说是O(kn)其中k是报数上限。因为每淘汰一只猴子需要让k只猴子依次报数其中k-1只重新入队、1只被淘汰。总共有n-1只猴子会被淘汰所以总操作次数大约为k(n-1)次。空间复杂度是O(n)因为队列中最多同时存在n只猴子。如果k3差不多就是3n次操作的常数级开销PTA数据量下完全够用。但如果题目把k改为一个特别大的数比如n1000000、k1000000那么队列模拟的O(k*n)会直接退化到10^12级别必然超时。这时候就不能再死磕队列了要转而使用约瑟夫问题的数学递推解法后面第5.1节会详细讲。另外要注意循环数组的MAXN如果开得比n小存取数组时会越界。PTA有些标题会在题目描述里隐藏数据范围建议开一个足够大的常量比如1000005或者根据n动态分配数组。如果n能到1000000MAXN至少要比n大1因为循环队列判满条件会浪费一个位置。4.3 常见踩坑清单我在带新人做这道题时见过最多的错误集中在下面几个位置列出来帮你排雷。第一count忘记重置。报到3的猴子被淘汰后count必须归零下一只猴子从1开始报。如果漏掉重置后面的报数会变成4、5、6整个模拟直接错乱。这是很多人代码跑出莫名其妙结果的头号原因。第二循环队列的判空和判满混淆。head tail表示队列空(tail 1) % MAXN head表示队列满。在这道题里我们不会主动判空因为循环条件已经保证至少剩一个元素但如果你在其他题目里复用这个模板一定要分清这两个条件。第三数组下标的出队入队顺序写反。必须先取head位置的元素再移动head必须先把元素写入tail位置再移动tail。反过来写会读到脏数据或覆盖还没出队的元素。第四链式版本忘了把重新入队的节点next置NULL。前面已经强调过如果不置空链表可能成环while循环就变成死循环PTA会报超时。第五题目要求多组输入时没有写while循环。部分PTA题的输入是多组测试数据格式会是“多行每行一个n”如果只处理一次输入就会漏掉后面的数据。建议看清楚题目要求需要多组输入就在外层加一层while(scanf(...) ! EOF)。5. 拓展与思考从猴子选大王到队列实际应用5.1 约瑟夫问题的数学递推什么时候用得上队列解法直观、容易想到但遇到n特别大的变体题目效率就不够了。这时候可以用约瑟夫问题的递推公式一行代码就能算出答案。设f(1)0表示只有1只猴子时幸存者在其从0开始的编号体系中的位置递推式为f(i)(f(i-1)k) % i其中k是报数上限最终答案是f(n)1。#include stdio.h int main() { int n, k 3, ans 0; scanf(%d, n); for (int i 2; i n; i) { ans (ans k) % i; } printf(%d\n, ans 1); return 0; }这个递推的本质是倒推剩1个人时他的编号一定是0往前推一步他上一轮的编号是(0k)%2再往前推就是(上一轮结果k)%3一直到初始n个人。数学解法的优势是时间O(n)、空间O(1)配合n最大1000000的数据也毫无压力。那为什么还要学队列解法因为递推虽然快但它像一个黑盒跳过了对“报数过程”的理解。队列解法能让你看到每一步谁被淘汰、谁重新回到队尾这比直接套公式更有助于建立数据结构思维。考试的时候如果时间充裕我甚至会先用队列解法写一遍验证结果再用递推公式优化大n测试点。5.2 队列思想在真实系统里的影子猴子选大王并不是一个孤立的脑力游戏它背后使用的FIFO思想在真实系统中到处都是。最常见的例子是消息队列上游服务把请求按顺序塞进队列下游消费者按顺序处理请求先进先出不会乱序也不会互相抢占。另一个例子是打印机队列多个文档同时提交时先提交的文档先被打印。操作系统里的进程调度也有队列的身影时间片轮转算法就是让每个进程轮流使用CPU一小段时间时间片用完就排到队尾等待下一轮这不就是猴子选大王的报数入队重排吗再比如广度优先搜索BFS遍历图时用队列保存待访问节点先加入的节点先被访问保证了按层扩展。这些场景的共同点就是“公平地轮流处理”而队列天生就是为公平处理设计的。下次在项目里遇到“任务排队”“请求排队”的需求第一反应就应该想到队列而不是数组加指针。5.3 一点实战心得最后分享几条我做这道题和这一类题的真实体会。第一条小数据手推永远比直接看代码可靠。我每次调试约瑟夫问题都会拿n5的模拟表对一遍程序输出哪怕代码已经熟了。第二条PTA评测报错时善用printf大法。比如在循环里打印当前队首、报数值、淘汰的是谁输出一比对问题马上浮出水面。第三条代码模板要留好循环队列的head、tail移动和长度计算在很多题目里都能复用值得单独存成自己的工具代码。猴子选大王这道题往小说是一道PTA练习题往大说是你对“队列”这个数据结构理解的试金石。真正动手跑完队列模拟再对比数学递推的代码你对为什么需要数据结构、为什么某些结构适合某些场景会有一个比看书深刻得多的答案。希望这篇拆解能帮你在PTA上顺利AC也顺带把队列的内功练扎实。