去年带的一个考研学生拿了一道题来问我“循环队列当前 front25rear25队列里有几个元素”他旁边的室友脱口而出“一个”理由是 front 和 rear 指向同一个位置要么空、要么有一个元素。结果标准答案既不是“一个”也不是单纯的“0”而是“0 或队列容量”。两个人之所以吵起来是因为他们心里默认的“队列实现约定”根本不一样。这个场景几乎每年都在考研群里重演一遍。队列的 front队头指针和 rear队尾指针指向类题目看起来只是画几个箭头、算几个加减法实际却是数据结构选择题里错误率最高的一类。原因只有一个不同教材、不同题目里front 和 rear 的“指向语义”并不完全一致而元素个数公式、判空判满条件、入队出队写法全都跟着指向语义走。这篇就把这些约定、公式、真题和坑一次性理顺给正在准备考研、期末考、面试的朋友一份能直接对照使用的清单。1. 所有分歧的源头front和rear到底“指着”哪里1.1 三种最常见的指向约定在开始做题之前必须先搞清楚一件事同样叫 front 和 rear不同题目里它们的含义可能完全不同。我把刷题时见过的情况归成三类90% 的题都跑不出这个范围。约定front 指向rear 指向常见出处A队头元素队尾元素的下一个空位严蔚敏版循环队列、多数考研辅导书B队头元素的前一个位置队尾元素部分教材的顺序队列实现C队头元素队尾元素链式队列、部分 C 语言实现题约定 A 是最主流的循环队列写法。初始时 front rear 0入队时先把元素写进 rear 指向的位置然后 rear 向后移动一格出队时先把 front 指向的元素取出来然后 front 向后移动一格。这里的“向后移动一格”在循环队列里就是加一后对数组长度取模。约定 B 常见于一些教材讲解顺序队列的初始阶段。初始时 front rear -1两个指针都不指向任何元素。入队时先把 rear 加一再写入元素出队时先把 front 加一再取出元素。这种写法下front 其实指向的是“队头元素前一个位置”取元素要取 front 1 那个位置。约定 C 则更贴近链表实现front 指向队头结点本身rear 指向队尾结点本身。如果出队front front-next如果入队rear-next 新结点。这种“指针指向元素本身”的约定在顺序存储里也偶有出现属于最容易让人掉坑的一种因为它的元素个数公式和约定 A、B 都不一样。1.2 为什么会有这么多不同的“指法”很多学生不理解就不能统一一下吗为什么教材非要搞出几种约定本质上是因为顺序存储的循环队列是用数组下标来模拟指针的。不同的教材作者在设计“空队列长什么样”“入队操作怎么写最简洁”时做出了不同的取舍。约定 A 的优点是入队出队代码对称判空用 front rear 非常直观约定 B 的优点在于 front 初始为 -1和“指针尚未指向任何元素”的直觉一致约定 C 则是链表实现的自然结果。没有哪一种绝对正确只有“当前题目里用的是哪一种”。这也是为什么我一直强调拿到一道队列指针题第一件事不是套公式而是确认题目里 front 和 rear 的指向语义。1.3 我要求每个学生做题前先写一句话带过的学生里凡是反复在队列指针题上丢分的几乎都有一个共同问题拿到题就开始套“(rear - front MaxSize) % MaxSize”完全不看题目里 front 和 rear 到底指向什么。我的建议很朴素做题前先在草稿纸上写一句话——“本题中 front 指向队头元素rear 指向队尾元素的下一个位置”或者“front 指向队头元素的前一个位置rear 指向队尾元素”。写完再动手。这句话只花十秒钟但能避免至少一半的低级错误。后面所有公式、代码、判断都围绕这句话展开你会发现这类题的准确率立刻上了一个台阶。2. 循环队列的取模运算与元素个数公式2.1 取模运算到底在做什么循环队列的核心思想是“把数组掰成一个环”。假设数组长度为 MaxSize那么下标 MaxSize - 1 的下一个位置应该是 0。这个操作用数学表达就是rear (rear 1) % MaxSize; front (front 1) % MaxSize;为什么要取模你可以把数组想象成一个钟表盘只有 0 到 MaxSize - 1 这 MaxSize 个刻度。指针走到 MaxSize - 1 后再往前走一步本来应该越界取模之后又回到了 0于是数组被循环使用了。在约定 A 下入队和出队的核心代码是这样的// 入队 Q.data[Q.rear] x; Q.rear (Q.rear 1) % MaxSize; // 出队 x Q.data[Q.front]; Q.front (Q.front 1) % MaxSize;注意入队是“先写入后移动”出队是“先取出后移动”。这个顺序必须记牢否则你在分析指针位置时会乱套。2.2 元素个数公式绝不是简单的 rear - front很多同学上来就写“元素个数 rear - front”这在非循环队列里偶尔成立但在循环队列里马上就翻车。因为 rear 完全可能小于 front。比如 MaxSize 6 时front 4rear 2队列里的元素其实是绕着环从下标 4、5、0、1 走的一共 4 个。约定 Arear 指向队尾元素的下一个位置下元素个数分三种情况若 rear front个数 rear - front若 rear front个数 rear - front MaxSize若 rear front队列空个数为 0统一成一个公式就是元素个数 (rear - front MaxSize) % MaxSize这个公式的推导并不复杂。无非是在 rear front 时把 rear 加上一个 MaxSize 看成“下一圈的位置”再减 front。比如 front 4rear 2MaxSize 6那么 (2 - 4 6) % 6 4正好对应下标 4、5、0、1 四个元素。但在约定 C 下front 和 rear 都指向元素本身公式就要变了。此时如果 front 4rear 1MaxSize 6队列中的元素是下标 4、5、0、1 这 4 个元素个数仍然是 4但直接套上一个公式算出来是 (1 - 4 6) % 6 3少了一个。为什么因为 rear 指向的是最后一个元素本身跟 front 之间的“间距”比约定 A 少了 1。所以约定 C 下的个数公式是元素个数 (rear - front 1 MaxSize) % MaxSize约定rear 指向元素个数公式A队尾元素的下一个位置(rear - front MaxSize) % MaxSizeC队尾元素本身(rear - front 1 MaxSize) % MaxSize这个 1 的差距就是无数人丢分的地方。你一定要先确认题目里 rear 指向的是元素本身还是元素的下一个位置否则公式就是错的。2.3 判空判满为什么循环队列要牺牲一个存储单元还有一个绕不开的问题怎么判断队列是空还是满约定 A 下front rear 可以表示空队列。但问题来了队列满的时候是什么状态入队操作是“先写入后移动”如果队列填满了rear 移动一圈后又会追上 front出现 rear front。这和空队列的状态完全一样产生了二义性。为了解决这个矛盾最经典的做法是牺牲一个存储单元让队列最多只能存 MaxSize - 1 个元素。这样满队列时 rear 紧挨着 front 但不等于 front判断条件就是(Q.rear 1) % MaxSize Q.front;策略判空条件判满条件最多元素数牺牲一个存储单元front rear(rear 1) % MaxSize frontMaxSize - 1增设 size 计数front rear 且 size 0front rear 且 size MaxSizeMaxSize增设 tag 标记front rear 且 tag 0front rear 且 tag 1MaxSize牺牲一个存储单元是考研和面试里最常考的方式因为代码最简洁但也最容易让人误以为“队列容量就是 MaxSize”。实际上当题目说“循环队列最多能容纳 MaxSize 个元素”时通常意味着你要额外引入 size 或 tag如果题目没有提这些默认都是牺牲一个单元的写法。3. 三道经典真题拆解从背公式到真正会算3.1 真题一front rear 25队列里到底有几个元素回到开头那道题。设循环队列的存储空间为 Q(1:100)初始状态 front rear 100。经过一系列正常的入队与退队操作后front rear 25此时循环队列中的元素个数为A. 0 B. 1 C. 99 D. 0 或 100正确答案是 D。原因很简单在约定 A 下front rear 可能是空队列也可能是队列刚好填满后指针绕了一圈回到起点。如果题目额外说明了“牺牲一个单元判满”那么 front rear 只能判空但这道题没有说明采用哪种判满策略而“正常的入队与退队操作”并没有排除队列曾经装满的情况。因此 0 和队列容量两种可能都存在。这个题非常典型它考的不是计算而是你有没有意识到“front rear 在循环队列里不能直接断言为空”。很多辅导书把它归类为“二义性问题”本质上就是对前面 2.3 节内容的直接考察。3.2 真题二第一个入队元素必须进 A[0]初始指针怎么设再看一道非常经典的题已知循环队列存储在一维数组 A[0..n-1] 中且队列非空时 front 和 rear 分别指向队头元素和队尾元素。若初始时队列为空且要求第一个进入队列的元素存储在 A[0] 处则初始时 front 和 rear 的值分别是A. 0, 0 B. 0, n-1 C. n-1, 0 D. n-1, n-1正确答案是 Bfront 0rear n-1。这道题的关键在于题目说“队列非空时 front 指向队头元素”也就是说 front 的初始化位置应该正好是第一个元素要存放的位置所以 front 0。rear 的初始化则取决于入队操作的写法。如果入队采用“先移动 rear 指针再写入元素”的方式那么要让第一个元素写进 A[0]rear 必须先停在 n-1那么 (n-1 1) % n 0第一次入队时元素就能顺利存到 A[0]。很多学生选了 A0, 0理由是“初始都指向 0 很自然”。但这样导致的问题是如果入队时先移动 rear第一次入队 rear 变成 1元素存到了 A[1]违背了题目要求。这个坑的本质是指针的初始值不是拍脑袋定的它必须和入队出队操作顺序保持自洽。3.3 真题三双端循环队列的判空判满换个马甲你还能认出来吗有一年的统考真题出了一道类似这样的题循环队列存储在一维数组 A[0..M-1] 中end1 指向队头元素end2 指向队尾元素的下一个位置。队列两端都可以进行入队和出队操作队列最多容纳 M-1 个元素初始时为空。下列判断队空和队满的条件中正确的是A. 队空end1 end2队满end1 (end2 1) mod M B. 队空end1 end2队满end2 (end1 1) mod M这里只要把 end1 看成 front把 end2 看成 rear就立刻发现它们就是最标准的约定 A。空队列自然是 end1 end2满队列则是 rear 再走一步就碰到 front也就是 (end2 1) % M end1等价于 end1 (end2 1) % M所以选 A。这道题难不倒真正理解 aligned 语义的人但对只会死记“front rear 判空”的同学来说换个名字就认不出来了。因此我一直强调背结论没有意义你要能在任何变量名、任何约定下自己推导出判空判满条件。3.4 这三道题背后的共同套路这三道题表面考的东西不同一个考二义性一个考初始值推导一个考变量名翻译但共同点是都必须先确认 front 和 rear 的指向语义再结合入队出队的操作顺序进行推理。千万不要先背答案再找理由而是先分析约定再自然得出结论。4. 链式队列的头尾指针变化与最易忽略的边界4.1 带头结点和不带头结点两种结构两套判空链式队列的指针指向语义相对统一front 指向队头结点rear 指向队尾结点。但有没有头结点会直接影响初始状态和判空条件。带头结点时front 和 rear 初始都指向头结点此时 front rear队列为空。不带头结点时front 和 rear 初始都为 NULL此时用 front NULL 判断空队。两者的差别在代码里很微小但在题目里很容易看漏。结构初始状态判空条件入队第一个元素时的操作带头结点front rear 头结点front rearrear-next 新结点; rear 新结点不带头结点front rear NULLfront NULLfront rear 新结点4.2 入队出队的指针操作一个只动 rear一个可能动两个带头结点的链式队列入队只需要在尾结点后面挂新结点然后移动 rearvoid EnQueue(LinkNode *front, LinkNode *rear, int x) { LinkNode *s (LinkNode *)malloc(sizeof(LinkNode)); s-data x; s-next NULL; rear-next s; rear s; }出队就复杂一些。因为 front 指向的是头结点真正要被移除的是 front-next也就是队列的第一个数据结点bool DeQueue(LinkNode *front, LinkNode *rear, int x) { if (front rear) return false; // 空队列 LinkNode *p front-next; // p 是真正的队头结点 x p-data; front-next p-next; // 绕过 p if (p rear) rear front; // 关键队列只有一个结点时 free(p); return true; }注意这个 if (p rear)。当队列中只有一个数据结点时p 既是队头也是队尾。如果不做这个判断free(p) 之后 rear 还指向一块已释放的内存成了野指针后面再入队或判空都会出错。不带头结点的版本处理方式类似但因为 front 直接指向数据结点出队时 front front-next 即可不过也同样要检查出队后链表是否为空如果空了要把 rear 也置为 NULL。4.3 最容易被忽略的边界删掉最后一个结点时 rear 怎么办我见过太多学生在链式队列这道题上写漏那个 if (p rear) 判断。漏掉的后果不是立刻报错而是“看起来好像也能运行”直到下一次入队或者释放队列时才出现诡异的段错误。这个边界问题的本质是rear 指针在整个入队过程中只被“向后推进”从来没有被“向前指回”的操作。正常出队删的都是中间结点rear 不需要变但当你删掉的是最后一个结点时rear 指向的结点已经不存在了必须手动把它拉回到头结点带头结点或者置为 NULL不带头结点。同理不带头结点的链式队列出队后如果发现 front 变成了 NULL也要记得把 rear 同步置为 NULLbool DeQueue(LinkNode *front, LinkNode *rear, int x) { if (front NULL) return false; LinkNode *p front; x p-data; front front-next; free(p); if (front NULL) rear NULL; // 队列已空rear 也要归位 return true; }4.4 链式队列的“元素个数”为什么反而很简单链式队列不像循环队列那样有取模公式因为它在内存里是离散的不存在“环绕”问题。要求元素个数只能从头结点开始遍历链表数到 NULL 为止时间复杂度是 O(n)。有些题目会问“front 和 rear 指向同一结点时链式队列里有没有元素”。答案是不一定。带头结点时 front rear 表示空队列但如果是不带头结点且队列里只有一个元素front 和 rear 都指向这个唯一的结点此时 front rear 但队列非空。这里又是同一个坑必须先说明用哪种结构再判断状态。5. 指向类题型的四类考法与通用解法5.1 四类常见考法我总结下来所有关于 front 和 rear 指向的题基本跑不出四类给操作序列求指针位置比如“连续入队 3 个元素出队 2 个元素后front 和 rear 各是多少”。这种题就是照着入队出队操作一步步模拟注意取模时机。给指针位置求元素个数或空满状态比如“front 3rear 1MaxSize 6队列里有几个元素”。这种题要套公式但必须先判断使用的是哪种约定。给初始要求求初始指针值比如 3.2 节那种“第一个元素要存到 A[0]”。这种题考的是操作顺序和初始值是否自洽。链式队列删除时的指针维护比如“出队时什么时候需要修改 rear”。这种题考的是边界条件尤其是单元素队列的删除。5.2 一套通用的五步解法无论哪类题我自己总结的解题流程都是五步你可以直接拿去用圈出语义在题目里找出“front 指向____rear 指向____”的描述写成一句话。画出环形结构在草稿纸上画一个数组环标出下标 0 到 MaxSize - 1再把 front 和 rear 的位置画上去。判断公式根据语义选择元素个数公式。rear 指向下一空位用 (rear - front MaxSize) % MaxSizerear 指向队尾元素本身用 (rear - front 1 MaxSize) % MaxSize。逐步模拟入队和出队分别只改变 rear 和 front方向均为顺时针下标递增方向每一步之后重新画位置。边界检查拿到结果后想一下“如果队列为空/满/只有一个元素这个结论还成立吗”。尤其是单元素队列十有八九藏着坑。5.3 用一道综合小题演示这套解法来看一个综合题设循环队列的存储空间为数组 A[0..5]约定 front 指向队头元素rear 指向队尾元素的下一个位置。已知当前 front 4rear 2请回答队列里有几个元素能否继续入队若入队一个元素后 rear 是多少若出队一个元素后 front 是多少按五步走。第一步语义是约定 A。第二步画一个 6 格环front 在 4rear 在 2顺时针数一下元素在下标 4、5、0、1 的位置共 4 个。第三步代公式 (2 - 4 6) % 6 4和数格子的结果一致。第四步如果入队一个元素rear (2 1) % 6 3如果出队一个元素front (4 1) % 6 5。第五步边界检查此时 (rear 1) % 6 4确实等于 front说明入队这个元素之后恰好满队列验证了“还能入队一个”的判断。这五步看起来琐碎但每一步都可以防止特定类型的错误。一旦你知道自己在算什么就不会再把 rear - front 1 里的那个 1 加错位置了。6. 半年刷题下来我最想说的几件小事6.1 先把“本题约定”写出来再动笔这几年带过的学生里能稳定做对指针指向题的人都有一个共同习惯拿笔先写约定。哪怕题目已经说了“front 指向队头元素rear 指向队尾元素的下一个位置”他们也要原样抄一遍再往里面代入数字。这个动作看起来多余实际上是在强制自己不要跳步。人一旦跳过“确认语义”直接开始套公式出错的概率会成倍增加。6.2 画图比背公式更抗干扰考研考场上时间紧张很多人宁愿硬背公式也不画图。但我的体验是公式反而是最容易被干扰记忆污染的部分尤其是那个“加 1 还是不加 1”。画图就不一样——把环画出来front 和 rear 一站元素个数一目了然。画图最多十秒钟但能省下检查答案时的大量时间。我辅导过的一个二战学生之前每次都错在符号上后来养成画图习惯此类题目基本没再失分。6.3 模运算的三个坑第一个坑是在语言里直接对负数取模。C 语言或 Java 里负数 % 正数结果可能是负数比如 (-2) % 6 在部分环境下结果是 -2不是 4。所以公式里一定要先加 MaxSize 再取模。第二个坑是把 MaxSize 和数组最大下标搞混。数组 A[0..5] 的 MaxSize 是 6不是 5取模的基数是 6。第三个坑是算空闲空间时如果用牺牲一个存储单元的方案最多只能放 MaxSize - 1 个元素所以“还能入队几个”不能用 MaxSize 减去当前元素个数而要用 (MaxSize - 1) 减去当前元素个数。6.4 考试和面试里最实用的检查技巧检查这类题我通常用一个非常朴素的技巧把特殊情况代入验证。比如假设队列里只有一个元素看看自己的公式算出来是不是 1假设 front 和 rear 相邻看看自己判断的“空”或“满”是否符合预期。单元素队列是最容易暴露问题的状态因为它在很多约定下会出现 front rear 但队列非空的情况。代入一次就能发现公式、判空条件、代码实现三者之间是不是自洽的。队列指针题归根到底不是计算题而是“约定理解题”。把约定写清楚把操作顺序理顺这类题比大多数数据结构的题目都更容易拿满分。