队列这个结构刚学数据结构那会儿我觉得它比栈简单——不就是先进先出嘛能有多难。结果第一次用数组手写循环队列被取模运算绕得头晕第一次用链表实现队列指针操作写反了导致内存泄漏第一次做约瑟夫环用数组模拟报数边界条件调了整整一个下午。这三个东西单独拎出来都不算复杂但放在一起恰好覆盖了线性结构里最核心的几类问题连续存储与离散存储的取舍、循环利用空间的技巧、以及用数据结构解决经典数学问题的建模思路。下面我就按自己踩坑的顺序把顺序队列、链式队列和约瑟夫环的C实现从头到尾捋一遍代码全部实测可跑关键位置我会解释为什么这么写而不是那么写。1. 为什么队列值得单独花时间啃很多人学数据结构有个误区觉得队列太简单看一眼就跳过去把精力全砸在树和图上面。我当初也这么想直到后来做项目时遇到一个消息缓冲的需求才发现自己对队列的理解全是漏洞。队列的本质是受限的线性表——只允许在一端插入另一端删除。这个限制看起来是阉割了线性表的能力但实际上它带来的语义非常明确先来的先被处理。这个语义在操作系统调度、网络数据包缓冲、打印任务排队、广度优先搜索等场景里反复出现。你如果只是背下来先进先出四个字遇到具体问题照样写不对。顺序队列和链式队列解决的是同一个问题但底层存储方式完全不同。顺序队列用一段连续内存靠两个下标front和rear标记队头和队尾链式队列用离散节点靠指针串联。两者各有各的坑顺序队列如果不做循环处理会出现假溢出——明明数组前面有空位但因为rear已经到头了新元素就是插不进去链式队列则要小心指针操作顺序写反一步就是内存泄漏或者段错误。约瑟夫环则是队列的一个经典应用场景。问题描述很简单n个人围成一圈从第一个人开始报数报到m的人出列然后从下一个人继续报数直到所有人出列。用队列来模拟这个过程非常自然——每次把队头元素移到队尾相当于跳过一个人报到m时直接出队相当于淘汰一个人。但真正写起来边界条件、报数起点、剩余人数的处理每一个都可能让你调试半天。我下面会先讲顺序队列的循环实现再讲链式队列的指针操作最后用队列思路解约瑟夫环。每一部分都会给出完整代码、关键逻辑解释以及我在实际调试中总结的注意事项。2. 顺序队列的循环数组实现与假溢出陷阱2.1 顺序队列的基本结构设计顺序队列最直觉的做法是开一个固定大小的数组用front记录队头位置用rear记录队尾位置。入队时把元素放到rear位置然后rear加一出队时取走front位置的元素然后front加一。空队列的条件是front等于rear。这个设计在元素只进不出的情况下没问题但一旦有出队操作front就会往后移动前面空出来的位置就永远浪费了。比如数组大小是5你入队5个元素rear到了5越界此时出队2个元素front变成2数组下标0和1的位置空着但rear已经不能再加了。这就是假溢出——不是真的没空间而是空间没有被循环利用。解决办法是把数组在逻辑上弯成一个环。当rear到达数组末尾时如果前面还有空位就让它绕回到下标0继续存放。实现上就是每次移动下标时做一次取模运算rear (rear 1) % capacity。这样数组的物理存储还是线性的但逻辑上变成了循环的。这里有一个关键细节如何区分队空和队满。如果不做特殊处理队空时front等于rear队满时front也等于rear因为rear绕了一圈追上了front两者条件冲突。常见的解决方案有三种牺牲一个存储单元队满的条件变成(rear 1) % capacity front也就是说当rear的下一个位置是front时就算满实际可用容量是capacity减一。增加一个size变量记录当前元素个数队空时size为0队满时size等于capacity判断简单直接。增加一个tag标记记录最后一次操作是入队还是出队配合front和rear判断。我个人最推荐第二种——加一个size变量。原因很简单代码可读性最好不需要在脑子里绕取模逻辑而且实际项目中队列的容量通常不会卡到极限多一个int变量的开销完全可以忽略。下面给出的实现就用这种方式。2.2 循环队列的完整C实现#include iostream using namespace std; templatetypename T class CircularQueue { private: T* data; // 动态数组 int capacity; // 容量 int front; // 队头下标 int rear; // 队尾下标下一个入队位置 int count; // 当前元素个数 public: CircularQueue(int cap 10) { capacity cap; data new T[capacity]; front 0; rear 0; count 0; } ~CircularQueue() { delete[] data; } bool isEmpty() const { return count 0; } bool isFull() const { return count capacity; } int size() const { return count; } bool enqueue(const T value) { if (isFull()) { return false; // 队列已满入队失败 } data[rear] value; rear (rear 1) % capacity; count; return true; } bool dequeue(T value) { if (isEmpty()) { return false; // 队列为空出队失败 } value data[front]; front (front 1) % capacity; count--; return true; } bool getFront(T value) const { if (isEmpty()) { return false; } value data[front]; return true; } void print() const { if (isEmpty()) { cout 队列为空 endl; return; } cout 队列元素: ; int idx front; for (int i 0; i count; i) { cout data[idx] ; idx (idx 1) % capacity; } cout endl; } };这段代码有几个地方值得展开说。为什么用模板队列里存什么类型的数据是不确定的可能是int、string也可能是自定义的结构体。用模板可以让同一份代码适配所有类型避免为每种类型重复写一遍。如果你暂时不熟悉模板把templatetypename T去掉把所有T换成int逻辑完全一样。为什么用动态数组而不是固定大小数组固定大小数组在编译期就确定了容量不够灵活。用new T[capacity]在堆上分配内存容量可以在构造时指定用完之后在析构函数里delete[]释放。这里要注意如果是存自定义类型T需要有无参构造函数或者你需要在分配时做额外处理不过对于基础类型和标准库类型都没问题。入队和出队的返回值设计我让enqueue和dequeue返回bool表示操作是否成功。这样做的好处是调用方可以明确知道操作结果而不是默默失败。有些教材的实现直接返回void队列满时什么都不做调用方根本不知道数据有没有进去。实际项目中这种沉默失败是灾难性的。取模运算的位置rear (rear 1) % capacity这行代码是循环队列的核心。当rear等于capacity减一时加一变成capacity取模后变成0正好绕回数组开头。front的移动同理。你可以手动模拟一下capacity为5rear从0开始依次变成1、2、3、4、0、1……永远不会越界。2.3 实测中容易踩的三个坑第一个坑取模运算的优先级。C中%的优先级和*、/同级高于和-。所以rear 1 % capacity会被解析成rear (1 % capacity)结果完全错误。必须写成(rear 1) % capacity。我当初就是因为少写了一对括号调试了半个小时才发现问题。第二个坑遍历队列时的下标处理。因为队列是循环的不能简单地从front循环到rear因为rear可能小于front。正确的做法是用count控制循环次数每次下标加一后取模。上面print函数就是这么写的。如果你用for (int i front; i ! rear; i (i 1) % capacity)也可以但要注意队列满时front等于rear这个循环一次都不会执行需要额外处理。第三个坑拷贝构造和赋值运算符。上面的类用了动态内存分配如果直接拷贝对象两个对象会共享同一块内存析构时就会double free。正确的做法是实现拷贝构造函数和赋值运算符深拷贝或者用std::vector代替裸指针。为了代码简洁我这里没有展开但你在实际使用中一定要注意。如果只是局部使用、不涉及对象拷贝问题不大一旦要把队列作为参数传递或者放入容器就必须处理这个问题。提示如果你用的是C11及以上标准可以用std::unique_ptrT[]来管理数组内存这样连析构函数都不用写了而且自动禁止拷贝避免误用。3. 链式队列的指针操作与边界处理3.1 链式队列的节点设计与头尾指针顺序队列的容量是固定的一旦满了就没法再入队。链式队列没有这个问题——每个元素是一个独立的节点用指针串联起来理论上只要内存够就可以一直入队。链式队列需要维护两个指针front指向队头节点rear指向队尾节点。入队在rear后面接一个新节点出队删除front指向的节点。这里有一个设计选择要不要带头节点。带头节点的意思是front指向一个不存数据的哑节点真正的队头元素是front-next。带头的好处是入队和出队的代码可以统一处理不需要单独判断队列是否为空。不带头的代码更直观但空队列时插入第一个元素需要特殊处理。我两种都写过个人更倾向于不带头节点因为代码更短逻辑更直接。但如果你追求代码的对称性和统一性带头节点也是很好的选择。下面给出的实现不带头节点。#include iostream using namespace std; templatetypename T struct Node { T data; Node* next; Node(const T d) : data(d), next(nullptr) {} }; templatetypename T class LinkedQueue { private: NodeT* front; // 队头指针 NodeT* rear; // 队尾指针 int count; // 元素个数 public: LinkedQueue() : front(nullptr), rear(nullptr), count(0) {} ~LinkedQueue() { while (front ! nullptr) { NodeT* temp front; front front-next; delete temp; } } bool isEmpty() const { return front nullptr; } int size() const { return count; } void enqueue(const T value) { NodeT* newNode new NodeT(value); if (isEmpty()) { front rear newNode; } else { rear-next newNode; rear newNode; } count; } bool dequeue(T value) { if (isEmpty()) { return false; } value front-data; NodeT* temp front; front front-next; if (front nullptr) { rear nullptr; // 队列变空rear也要置空 } delete temp; count--; return true; } bool getFront(T value) const { if (isEmpty()) { return false; } value front-data; return true; } void print() const { if (isEmpty()) { cout 队列为空 endl; return; } cout 队列元素: ; NodeT* cur front; while (cur ! nullptr) { cout cur-data ; cur cur-next; } cout endl; } };3.2 入队和出队的指针变化过程链式队列的入队操作分两种情况。如果队列为空新节点既是队头也是队尾所以front rear newNode。如果队列不为空把新节点接到rear的后面然后更新rear指向新节点。注意这里不能先更新rear再连接否则就找不到原来的队尾了。顺序必须是先rear-next newNode再rear newNode。出队操作也分两种情况。如果出队后队列变空front变成了nullptr必须把rear也置为nullptr。这一步非常容易漏掉。如果你漏了rear会指向一个已经被delete的节点下次入队时rear-next newNode就会访问已释放的内存程序可能崩溃或者产生不可预期的行为。我当初就是因为漏了这一行程序在小数据量下运行正常一旦数据量大了就随机崩溃排查了很久才定位到。内存释放的顺序出队时先用temp保存front然后front后移最后delete temp。顺序不能反——如果先delete front再访问front-next就是访问已释放内存。这个错误在初学者代码里非常常见。析构函数的实现析构时需要遍历整个链表逐个delete节点。注意在delete当前节点之前要先把front移到下一个节点否则就找不到后续节点了。上面的析构函数就是这么写的。3.3 链式队列相比顺序队列的取舍链式队列和顺序队列没有绝对的优劣关键看使用场景。我整理了一个对比表格对比维度顺序队列循环数组链式队列内存分配一次性分配连续内存每次入队动态分配节点容量限制固定满了无法入队理论上无限制受内存约束缓存友好度高连续内存访问快低节点分散在堆上入队时间复杂度O(1)O(1)但有new操作开销出队时间复杂度O(1)O(1)但有delete操作开销内存开销仅数组本身每个节点多一个指针域适用场景容量可预估、追求性能容量不确定、频繁增删如果你的队列容量可以预估比如做嵌入式开发时缓冲区大小固定顺序队列更合适——没有动态内存分配不会产生内存碎片访问速度也更快。如果容量完全不可预测比如处理网络请求链式队列更灵活。还有一个实际因素动态内存分配的开销。每次入队都new一个节点每次出队都delete一个节点在高频场景下这个开销不可忽视。有些高性能场景会用内存池来优化预先分配一批节点循环使用避免频繁的系统调用。不过这属于进阶优化初学阶段先把基础实现搞扎实。注意链式队列的enqueue操作如果new失败内存耗尽会抛出std::bad_alloc异常。在资源受限的环境下你可能需要捕获这个异常并做降级处理而不是让程序直接崩溃。4. 约瑟夫环的队列建模与模拟实现4.1 约瑟夫环问题的本质拆解约瑟夫环的描述有很多版本核心逻辑是一样的n个人围成一圈从某个人开始报数每报到m的人出列然后从出列者的下一个人重新开始报数直到所有人出列。要求输出出列的顺序。这个问题的数学模型其实是一个递推问题有O(n)的数学解法。但用队列来模拟是最直观的也是理解队列应用的绝佳案例。用队列模拟的思路是把n个人依次入队。从队头开始每次把队头元素取出并重新入队到队尾相当于这个人报数不是m跳过。当报数到m时队头元素直接出队不再入队这个人被淘汰。重复上述过程直到队列为空。这里的关键是报数计数器的维护。你可以用一个变量从1开始计数每处理一个人就加一当计数器等于m时执行淘汰并重置计数器为1。也可以每轮固定移动m减一次然后淘汰队头。两种写法等价但后者代码更简洁。4.2 用链式队列模拟约瑟夫环#include iostream using namespace std; // 复用上面的LinkedQueue这里简化为int类型 void josephus(int n, int m) { LinkedQueueint q; for (int i 1; i n; i) { q.enqueue(i); } cout 出列顺序: ; int count 0; // 已出列人数 while (!q.isEmpty()) { int cur; q.dequeue(cur); count; if (count % m 0) { // 报到m出列 cout cur ; } else { // 未报到m重新入队 q.enqueue(cur); } } cout endl; } int main() { int n 7, m 3; cout n n , m m endl; josephus(n, m); return 0; }运行结果出列顺序: 3 6 2 7 5 1 4。这个实现非常简洁但有几个细节值得注意。为什么用count % m而不是维护一个独立的报数变量count记录的是当前处理到第几个人包括已经出列和重新入队的每处理一个人count加一。当count能被m整除时说明当前这个人正好是第m个报数的应该出列。这种写法避免了在出列后重置计数器的操作逻辑更统一。出列后为什么不需要特殊处理因为出列的人直接从队列中移除了队列的front自动指向下一个人下一轮循环自然从下一个人开始报数。这正是队列先进先出特性带来的便利——你不需要手动维护下一个人是谁。时间复杂度分析每处理一个人要么出列O(1)要么重新入队O(1)。总共处理的人次数是n乘以m因为每淘汰一个人需要跳过m减一个人所以时间复杂度是O(n*m)。当n和m都很大时这个模拟会非常慢。比如n等于一百万、m等于一百万运算量是万亿级别肯定超时。这时候就需要用数学递推法把时间复杂度降到O(n)。4.3 数学递推法的思路与对比数学递推法的核心是找到出列编号的递推关系。假设f(n, m)表示n个人报数m时最后剩下的人或者第一个出列的人的编号。经过推导可以得到递推公式f(n, m) (f(n-1, m) m) % n其中f(1, m)等于0假设编号从0开始。这个公式的含义是n个人问题的解等于n减一个人问题的解加上m再对n取模。你可以这样理解淘汰一个人之后剩下n减一个人重新围成一圈但起点变了需要做一个偏移映射。用递推法求第一个出列的人int josephusMath(int n, int m) { int result 0; // f(1, m) 0 for (int i 2; i n; i) { result (result m) % i; } return result 1; // 转换回1-based编号 }这个算法的时间复杂度是O(n)空间复杂度是O(1)比队列模拟快得多。但它只能求出最后剩下的人如果要输出完整的出列顺序还是得用模拟法或者更复杂的数学方法。两种方法的适用场景如果只需要知道最后谁留下用数学递推法如果需要完整的出列顺序用队列模拟法。在实际面试中面试官可能会先让你用模拟法写然后问你有没有更优的解法这时候数学递推法就是加分项。提示约瑟夫环的数学解法有多种变体有的求最后剩下的人有的求第k个出列的人。递推公式的初始条件和边界处理略有不同使用前一定要确认清楚问题的具体定义。5. 三个实现串起来看存储方式如何决定代码形态把顺序队列、链式队列和约瑟夫环放在一起看会发现一个有意思的规律底层存储方式直接决定了代码的形态和容易出错的地方。顺序队列的代码里到处都是取模运算因为你要在逻辑上把线性数组弯成环。取模运算的优先级、边界值的处理、队空队满的判断这些坑都源于用连续内存模拟循环这个核心设计。你如果理解了这一点就能预判哪些地方容易出问题——所有涉及下标移动的地方都要检查取模所有涉及front和rear比较的地方都要考虑绕圈的情况。链式队列的代码里到处都是指针操作因为你要手动管理节点的连接和释放。指针操作顺序、空队列的特殊处理、内存泄漏的防范这些坑都源于用离散节点维护顺序关系这个核心设计。你如果理解了这一点就能预判哪些地方容易出问题——所有涉及指针赋值的地方都要考虑顺序所有涉及节点删除的地方都要检查是否有其他指针还指向它。约瑟夫环的代码则体现了数据结构选择对问题建模的影响。用队列来模拟代码不到二十行逻辑清晰到几乎不需要注释。如果用数组来模拟你需要手动维护当前报数位置、标记已出列的人、处理数组越界绕回代码量至少翻倍而且容易出错。这就是数据结构的价值——选对了结构问题本身就变简单了。我在实际编码中总结了一个判断原则如果问题的核心操作是在一端加入、在另一端删除就用队列如果核心操作是在一端加入、在同一端删除就用栈如果核心操作是随机访问任意位置就用数组或链表。约瑟夫环的核心操作是跳过一个人从队头移到队尾和淘汰一个人从队头删除正好符合队列的操作模式所以队列是最自然的选择。再补充一个实际调试中的经验先用小数据量验证逻辑再逐步增大。比如约瑟夫环先用n等于5、m等于2跑一遍手动推演结果确认代码输出和手算一致。然后再用n等于7、m等于3验证。如果小数据量下结果正确大数据量下出错那基本是边界条件或者内存问题如果小数据量下就错了那就是核心逻辑有问题。这个排查思路帮我省了很多时间。最后说一个关于模板类的小坑。上面的顺序队列和链式队列都用了模板如果你把类的声明和实现分开写在.h和.cpp文件里链接时会报未定义引用的错误。原因是模板的实例化需要在编译期完成编译器看不到实现就无法生成代码。解决办法有两个把实现也写在头文件里或者在.cpp文件末尾显式实例化你需要的类型。我一般直接把实现写在头文件里省事。代码这东西看一遍和写一遍完全是两回事。顺序队列的取模、链式队列的指针、约瑟夫环的边界每一个我都建议你亲手敲一遍故意改错几个地方看看会出什么现象。比如把(rear 1) % capacity的括号去掉把出队时的rear nullptr删掉把约瑟夫环的count % m改成count m跑一下看看结果有什么变化。这种故意犯错再修复的练习方式比照着正确代码抄一遍有效得多。 
长河君 · 2026/10/20 12:59:49 · 阅读 1.2k 顺序队列、链式队列与约瑟夫环的C++实现与避坑指南
队列这个结构刚学数据结构那会儿我觉得它比栈简单——不就是先进先出嘛能有多难。结果第一次用数组手写循环队列被取模运算绕得头晕第一次用链表实现队列指针操作写反了导致内存泄漏第一次做约瑟夫环用数组模拟报数边界条件调了整整一个下午。这三个东西单独拎出来都不算复杂但放在一起恰好覆盖了线性结构里最核心的几类问题连续存储与离散存储的取舍、循环利用空间的技巧、以及用数据结构解决经典数学问题的建模思路。下面我就按自己踩坑的顺序把顺序队列、链式队列和约瑟夫环的C实现从头到尾捋一遍代码全部实测可跑关键位置我会解释为什么这么写而不是那么写。1. 为什么队列值得单独花时间啃很多人学数据结构有个误区觉得队列太简单看一眼就跳过去把精力全砸在树和图上面。我当初也这么想直到后来做项目时遇到一个消息缓冲的需求才发现自己对队列的理解全是漏洞。队列的本质是受限的线性表——只允许在一端插入另一端删除。这个限制看起来是阉割了线性表的能力但实际上它带来的语义非常明确先来的先被处理。这个语义在操作系统调度、网络数据包缓冲、打印任务排队、广度优先搜索等场景里反复出现。你如果只是背下来先进先出四个字遇到具体问题照样写不对。顺序队列和链式队列解决的是同一个问题但底层存储方式完全不同。顺序队列用一段连续内存靠两个下标front和rear标记队头和队尾链式队列用离散节点靠指针串联。两者各有各的坑顺序队列如果不做循环处理会出现假溢出——明明数组前面有空位但因为rear已经到头了新元素就是插不进去链式队列则要小心指针操作顺序写反一步就是内存泄漏或者段错误。约瑟夫环则是队列的一个经典应用场景。问题描述很简单n个人围成一圈从第一个人开始报数报到m的人出列然后从下一个人继续报数直到所有人出列。用队列来模拟这个过程非常自然——每次把队头元素移到队尾相当于跳过一个人报到m时直接出队相当于淘汰一个人。但真正写起来边界条件、报数起点、剩余人数的处理每一个都可能让你调试半天。我下面会先讲顺序队列的循环实现再讲链式队列的指针操作最后用队列思路解约瑟夫环。每一部分都会给出完整代码、关键逻辑解释以及我在实际调试中总结的注意事项。2. 顺序队列的循环数组实现与假溢出陷阱2.1 顺序队列的基本结构设计顺序队列最直觉的做法是开一个固定大小的数组用front记录队头位置用rear记录队尾位置。入队时把元素放到rear位置然后rear加一出队时取走front位置的元素然后front加一。空队列的条件是front等于rear。这个设计在元素只进不出的情况下没问题但一旦有出队操作front就会往后移动前面空出来的位置就永远浪费了。比如数组大小是5你入队5个元素rear到了5越界此时出队2个元素front变成2数组下标0和1的位置空着但rear已经不能再加了。这就是假溢出——不是真的没空间而是空间没有被循环利用。解决办法是把数组在逻辑上弯成一个环。当rear到达数组末尾时如果前面还有空位就让它绕回到下标0继续存放。实现上就是每次移动下标时做一次取模运算rear (rear 1) % capacity。这样数组的物理存储还是线性的但逻辑上变成了循环的。这里有一个关键细节如何区分队空和队满。如果不做特殊处理队空时front等于rear队满时front也等于rear因为rear绕了一圈追上了front两者条件冲突。常见的解决方案有三种牺牲一个存储单元队满的条件变成(rear 1) % capacity front也就是说当rear的下一个位置是front时就算满实际可用容量是capacity减一。增加一个size变量记录当前元素个数队空时size为0队满时size等于capacity判断简单直接。增加一个tag标记记录最后一次操作是入队还是出队配合front和rear判断。我个人最推荐第二种——加一个size变量。原因很简单代码可读性最好不需要在脑子里绕取模逻辑而且实际项目中队列的容量通常不会卡到极限多一个int变量的开销完全可以忽略。下面给出的实现就用这种方式。2.2 循环队列的完整C实现#include iostream using namespace std; templatetypename T class CircularQueue { private: T* data; // 动态数组 int capacity; // 容量 int front; // 队头下标 int rear; // 队尾下标下一个入队位置 int count; // 当前元素个数 public: CircularQueue(int cap 10) { capacity cap; data new T[capacity]; front 0; rear 0; count 0; } ~CircularQueue() { delete[] data; } bool isEmpty() const { return count 0; } bool isFull() const { return count capacity; } int size() const { return count; } bool enqueue(const T value) { if (isFull()) { return false; // 队列已满入队失败 } data[rear] value; rear (rear 1) % capacity; count; return true; } bool dequeue(T value) { if (isEmpty()) { return false; // 队列为空出队失败 } value data[front]; front (front 1) % capacity; count--; return true; } bool getFront(T value) const { if (isEmpty()) { return false; } value data[front]; return true; } void print() const { if (isEmpty()) { cout 队列为空 endl; return; } cout 队列元素: ; int idx front; for (int i 0; i count; i) { cout data[idx] ; idx (idx 1) % capacity; } cout endl; } };这段代码有几个地方值得展开说。为什么用模板队列里存什么类型的数据是不确定的可能是int、string也可能是自定义的结构体。用模板可以让同一份代码适配所有类型避免为每种类型重复写一遍。如果你暂时不熟悉模板把templatetypename T去掉把所有T换成int逻辑完全一样。为什么用动态数组而不是固定大小数组固定大小数组在编译期就确定了容量不够灵活。用new T[capacity]在堆上分配内存容量可以在构造时指定用完之后在析构函数里delete[]释放。这里要注意如果是存自定义类型T需要有无参构造函数或者你需要在分配时做额外处理不过对于基础类型和标准库类型都没问题。入队和出队的返回值设计我让enqueue和dequeue返回bool表示操作是否成功。这样做的好处是调用方可以明确知道操作结果而不是默默失败。有些教材的实现直接返回void队列满时什么都不做调用方根本不知道数据有没有进去。实际项目中这种沉默失败是灾难性的。取模运算的位置rear (rear 1) % capacity这行代码是循环队列的核心。当rear等于capacity减一时加一变成capacity取模后变成0正好绕回数组开头。front的移动同理。你可以手动模拟一下capacity为5rear从0开始依次变成1、2、3、4、0、1……永远不会越界。2.3 实测中容易踩的三个坑第一个坑取模运算的优先级。C中%的优先级和*、/同级高于和-。所以rear 1 % capacity会被解析成rear (1 % capacity)结果完全错误。必须写成(rear 1) % capacity。我当初就是因为少写了一对括号调试了半个小时才发现问题。第二个坑遍历队列时的下标处理。因为队列是循环的不能简单地从front循环到rear因为rear可能小于front。正确的做法是用count控制循环次数每次下标加一后取模。上面print函数就是这么写的。如果你用for (int i front; i ! rear; i (i 1) % capacity)也可以但要注意队列满时front等于rear这个循环一次都不会执行需要额外处理。第三个坑拷贝构造和赋值运算符。上面的类用了动态内存分配如果直接拷贝对象两个对象会共享同一块内存析构时就会double free。正确的做法是实现拷贝构造函数和赋值运算符深拷贝或者用std::vector代替裸指针。为了代码简洁我这里没有展开但你在实际使用中一定要注意。如果只是局部使用、不涉及对象拷贝问题不大一旦要把队列作为参数传递或者放入容器就必须处理这个问题。提示如果你用的是C11及以上标准可以用std::unique_ptrT[]来管理数组内存这样连析构函数都不用写了而且自动禁止拷贝避免误用。3. 链式队列的指针操作与边界处理3.1 链式队列的节点设计与头尾指针顺序队列的容量是固定的一旦满了就没法再入队。链式队列没有这个问题——每个元素是一个独立的节点用指针串联起来理论上只要内存够就可以一直入队。链式队列需要维护两个指针front指向队头节点rear指向队尾节点。入队在rear后面接一个新节点出队删除front指向的节点。这里有一个设计选择要不要带头节点。带头节点的意思是front指向一个不存数据的哑节点真正的队头元素是front-next。带头的好处是入队和出队的代码可以统一处理不需要单独判断队列是否为空。不带头的代码更直观但空队列时插入第一个元素需要特殊处理。我两种都写过个人更倾向于不带头节点因为代码更短逻辑更直接。但如果你追求代码的对称性和统一性带头节点也是很好的选择。下面给出的实现不带头节点。#include iostream using namespace std; templatetypename T struct Node { T data; Node* next; Node(const T d) : data(d), next(nullptr) {} }; templatetypename T class LinkedQueue { private: NodeT* front; // 队头指针 NodeT* rear; // 队尾指针 int count; // 元素个数 public: LinkedQueue() : front(nullptr), rear(nullptr), count(0) {} ~LinkedQueue() { while (front ! nullptr) { NodeT* temp front; front front-next; delete temp; } } bool isEmpty() const { return front nullptr; } int size() const { return count; } void enqueue(const T value) { NodeT* newNode new NodeT(value); if (isEmpty()) { front rear newNode; } else { rear-next newNode; rear newNode; } count; } bool dequeue(T value) { if (isEmpty()) { return false; } value front-data; NodeT* temp front; front front-next; if (front nullptr) { rear nullptr; // 队列变空rear也要置空 } delete temp; count--; return true; } bool getFront(T value) const { if (isEmpty()) { return false; } value front-data; return true; } void print() const { if (isEmpty()) { cout 队列为空 endl; return; } cout 队列元素: ; NodeT* cur front; while (cur ! nullptr) { cout cur-data ; cur cur-next; } cout endl; } };3.2 入队和出队的指针变化过程链式队列的入队操作分两种情况。如果队列为空新节点既是队头也是队尾所以front rear newNode。如果队列不为空把新节点接到rear的后面然后更新rear指向新节点。注意这里不能先更新rear再连接否则就找不到原来的队尾了。顺序必须是先rear-next newNode再rear newNode。出队操作也分两种情况。如果出队后队列变空front变成了nullptr必须把rear也置为nullptr。这一步非常容易漏掉。如果你漏了rear会指向一个已经被delete的节点下次入队时rear-next newNode就会访问已释放的内存程序可能崩溃或者产生不可预期的行为。我当初就是因为漏了这一行程序在小数据量下运行正常一旦数据量大了就随机崩溃排查了很久才定位到。内存释放的顺序出队时先用temp保存front然后front后移最后delete temp。顺序不能反——如果先delete front再访问front-next就是访问已释放内存。这个错误在初学者代码里非常常见。析构函数的实现析构时需要遍历整个链表逐个delete节点。注意在delete当前节点之前要先把front移到下一个节点否则就找不到后续节点了。上面的析构函数就是这么写的。3.3 链式队列相比顺序队列的取舍链式队列和顺序队列没有绝对的优劣关键看使用场景。我整理了一个对比表格对比维度顺序队列循环数组链式队列内存分配一次性分配连续内存每次入队动态分配节点容量限制固定满了无法入队理论上无限制受内存约束缓存友好度高连续内存访问快低节点分散在堆上入队时间复杂度O(1)O(1)但有new操作开销出队时间复杂度O(1)O(1)但有delete操作开销内存开销仅数组本身每个节点多一个指针域适用场景容量可预估、追求性能容量不确定、频繁增删如果你的队列容量可以预估比如做嵌入式开发时缓冲区大小固定顺序队列更合适——没有动态内存分配不会产生内存碎片访问速度也更快。如果容量完全不可预测比如处理网络请求链式队列更灵活。还有一个实际因素动态内存分配的开销。每次入队都new一个节点每次出队都delete一个节点在高频场景下这个开销不可忽视。有些高性能场景会用内存池来优化预先分配一批节点循环使用避免频繁的系统调用。不过这属于进阶优化初学阶段先把基础实现搞扎实。注意链式队列的enqueue操作如果new失败内存耗尽会抛出std::bad_alloc异常。在资源受限的环境下你可能需要捕获这个异常并做降级处理而不是让程序直接崩溃。4. 约瑟夫环的队列建模与模拟实现4.1 约瑟夫环问题的本质拆解约瑟夫环的描述有很多版本核心逻辑是一样的n个人围成一圈从某个人开始报数每报到m的人出列然后从出列者的下一个人重新开始报数直到所有人出列。要求输出出列的顺序。这个问题的数学模型其实是一个递推问题有O(n)的数学解法。但用队列来模拟是最直观的也是理解队列应用的绝佳案例。用队列模拟的思路是把n个人依次入队。从队头开始每次把队头元素取出并重新入队到队尾相当于这个人报数不是m跳过。当报数到m时队头元素直接出队不再入队这个人被淘汰。重复上述过程直到队列为空。这里的关键是报数计数器的维护。你可以用一个变量从1开始计数每处理一个人就加一当计数器等于m时执行淘汰并重置计数器为1。也可以每轮固定移动m减一次然后淘汰队头。两种写法等价但后者代码更简洁。4.2 用链式队列模拟约瑟夫环#include iostream using namespace std; // 复用上面的LinkedQueue这里简化为int类型 void josephus(int n, int m) { LinkedQueueint q; for (int i 1; i n; i) { q.enqueue(i); } cout 出列顺序: ; int count 0; // 已出列人数 while (!q.isEmpty()) { int cur; q.dequeue(cur); count; if (count % m 0) { // 报到m出列 cout cur ; } else { // 未报到m重新入队 q.enqueue(cur); } } cout endl; } int main() { int n 7, m 3; cout n n , m m endl; josephus(n, m); return 0; }运行结果出列顺序: 3 6 2 7 5 1 4。这个实现非常简洁但有几个细节值得注意。为什么用count % m而不是维护一个独立的报数变量count记录的是当前处理到第几个人包括已经出列和重新入队的每处理一个人count加一。当count能被m整除时说明当前这个人正好是第m个报数的应该出列。这种写法避免了在出列后重置计数器的操作逻辑更统一。出列后为什么不需要特殊处理因为出列的人直接从队列中移除了队列的front自动指向下一个人下一轮循环自然从下一个人开始报数。这正是队列先进先出特性带来的便利——你不需要手动维护下一个人是谁。时间复杂度分析每处理一个人要么出列O(1)要么重新入队O(1)。总共处理的人次数是n乘以m因为每淘汰一个人需要跳过m减一个人所以时间复杂度是O(n*m)。当n和m都很大时这个模拟会非常慢。比如n等于一百万、m等于一百万运算量是万亿级别肯定超时。这时候就需要用数学递推法把时间复杂度降到O(n)。4.3 数学递推法的思路与对比数学递推法的核心是找到出列编号的递推关系。假设f(n, m)表示n个人报数m时最后剩下的人或者第一个出列的人的编号。经过推导可以得到递推公式f(n, m) (f(n-1, m) m) % n其中f(1, m)等于0假设编号从0开始。这个公式的含义是n个人问题的解等于n减一个人问题的解加上m再对n取模。你可以这样理解淘汰一个人之后剩下n减一个人重新围成一圈但起点变了需要做一个偏移映射。用递推法求第一个出列的人int josephusMath(int n, int m) { int result 0; // f(1, m) 0 for (int i 2; i n; i) { result (result m) % i; } return result 1; // 转换回1-based编号 }这个算法的时间复杂度是O(n)空间复杂度是O(1)比队列模拟快得多。但它只能求出最后剩下的人如果要输出完整的出列顺序还是得用模拟法或者更复杂的数学方法。两种方法的适用场景如果只需要知道最后谁留下用数学递推法如果需要完整的出列顺序用队列模拟法。在实际面试中面试官可能会先让你用模拟法写然后问你有没有更优的解法这时候数学递推法就是加分项。提示约瑟夫环的数学解法有多种变体有的求最后剩下的人有的求第k个出列的人。递推公式的初始条件和边界处理略有不同使用前一定要确认清楚问题的具体定义。5. 三个实现串起来看存储方式如何决定代码形态把顺序队列、链式队列和约瑟夫环放在一起看会发现一个有意思的规律底层存储方式直接决定了代码的形态和容易出错的地方。顺序队列的代码里到处都是取模运算因为你要在逻辑上把线性数组弯成环。取模运算的优先级、边界值的处理、队空队满的判断这些坑都源于用连续内存模拟循环这个核心设计。你如果理解了这一点就能预判哪些地方容易出问题——所有涉及下标移动的地方都要检查取模所有涉及front和rear比较的地方都要考虑绕圈的情况。链式队列的代码里到处都是指针操作因为你要手动管理节点的连接和释放。指针操作顺序、空队列的特殊处理、内存泄漏的防范这些坑都源于用离散节点维护顺序关系这个核心设计。你如果理解了这一点就能预判哪些地方容易出问题——所有涉及指针赋值的地方都要考虑顺序所有涉及节点删除的地方都要检查是否有其他指针还指向它。约瑟夫环的代码则体现了数据结构选择对问题建模的影响。用队列来模拟代码不到二十行逻辑清晰到几乎不需要注释。如果用数组来模拟你需要手动维护当前报数位置、标记已出列的人、处理数组越界绕回代码量至少翻倍而且容易出错。这就是数据结构的价值——选对了结构问题本身就变简单了。我在实际编码中总结了一个判断原则如果问题的核心操作是在一端加入、在另一端删除就用队列如果核心操作是在一端加入、在同一端删除就用栈如果核心操作是随机访问任意位置就用数组或链表。约瑟夫环的核心操作是跳过一个人从队头移到队尾和淘汰一个人从队头删除正好符合队列的操作模式所以队列是最自然的选择。再补充一个实际调试中的经验先用小数据量验证逻辑再逐步增大。比如约瑟夫环先用n等于5、m等于2跑一遍手动推演结果确认代码输出和手算一致。然后再用n等于7、m等于3验证。如果小数据量下结果正确大数据量下出错那基本是边界条件或者内存问题如果小数据量下就错了那就是核心逻辑有问题。这个排查思路帮我省了很多时间。最后说一个关于模板类的小坑。上面的顺序队列和链式队列都用了模板如果你把类的声明和实现分开写在.h和.cpp文件里链接时会报未定义引用的错误。原因是模板的实例化需要在编译期完成编译器看不到实现就无法生成代码。解决办法有两个把实现也写在头文件里或者在.cpp文件末尾显式实例化你需要的类型。我一般直接把实现写在头文件里省事。代码这东西看一遍和写一遍完全是两回事。顺序队列的取模、链式队列的指针、约瑟夫环的边界每一个我都建议你亲手敲一遍故意改错几个地方看看会出什么现象。比如把(rear 1) % capacity的括号去掉把出队时的rear nullptr删掉把约瑟夫环的count % m改成count m跑一下看看结果有什么变化。这种故意犯错再修复的练习方式比照着正确代码抄一遍有效得多。