说实话队列这块的知识点很多初学者最容易栽的地方不是队列本身而是“队头指针”和“队尾指针”到底指向哪。明明代码能背下来一做到选择题让你判断front和rear的值或者问你队满条件是什么就开始发懵。我自己也是从那个阶段过来的考研复习那会儿没少为“front指向队头元素还是队头元素的前一个位置”这种问题跟同学争得面红耳赤。后来刷题多了才发现这类题目其实套路非常固定核心就一条先确认这套题用的是哪套指针约定再套对应的公式和判断条件。一旦把不同方案的初始指向、入队出队后指针的变化规律理清楚不管题目怎么变都是同一个模板。这篇文章我打算把这些队头指针、队尾指针的指向问题进行系统梳理覆盖顺序队列、循环队列、链式队列里最常见的几种定义方式再用具体的例题演示怎么根据操作序列推算指针指向、怎么求元素个数、怎么判断队空队满。最后顺便聊聊这块经典知识在真实工程里的影子比如线程池的阻塞队列、消息队列消费位置管理其实都是同一套思路。适合正在准备考研数据结构、刷算法题或者面试前想快速把队列基础过一遍的朋友。1. 先搞懂队头指针和队尾指针到底指向谁1.1 为什么指针指向是队列题的“题眼”队列的逻辑是先进先出这所有人都知道。但落到代码实现层面“队头”和“队尾”这两个概念其实是有歧义的因为不同教材、不同参考书对front和rear的定义并不完全一致。同样是“队尾指针”有的指向队尾元素本身有的指向队尾元素的下一个空位置。这一点差异直接决定了初始化代码、入队出队的写法、队满判断条件甚至元素个数的计算公式都不一样。所以做队头队尾指针指向类题目第一件事不是急着套公式而是先看题目默认采用哪种约定。很多同学做题出错不是不会算而是拿着A方案的公式去做B方案的题那结果必然对不上。这块说严重点就像平时用厘米量长度考试的时候题目用的是英寸你不换算直接写数字肯定错。1.2 四种常见指针约定方案对比我把刷题过程中见过的题型归纳了一下常见的front和rear指向约定基本就四种其中前两种出现频率最高后两种偶尔考到。先把这几种方案的“初始状态”和“入队出队后怎么变”列出来后续所有题目都是在这个基础上衍生出来的。方案一考研最常见front指向队头元素rear指向队尾元素的下一个位置。也就是说rear指向的是队尾后面那个空位。判断队空时front rear入队时先写数据再让rear后移出队时先取front所指元素再让front后移。很多教材默认用这种方案。方案二front指向队头元素的前一个位置rear指向队尾元素。这种方案下初始化不是从0开始了而是front和rear都指向某个“前哨”位置。入队时rear先移动再写入出队时front先移动再取出。判断队空同样是front rear但含义跟方案一略有不同。方案三front指向队头元素rear指向队尾元素。两个指针都指向实际元素初始化时队空比较特殊一般需要额外的计数器或标志位来区分队空和队满因为当队列满的时候front和rear也会指向首尾元素光靠指针关系区分不了。方案四front指向队头元素的前一个位置rear指向队尾元素的下一个位置。这种约定不多见一般出现在某些特定教材或个别学校的考研真题里属于“看起来不一样算起来更绕”的类型。表格归纳一下方案front指向rear指向初始状态队空判断一队头元素队尾元素的下一个空位front rear 0front rear二队头元素的前一个位置队尾元素front rear 0指向头结点或前哨位front rear三队头元素队尾元素需标志位/计数器辅助靠标志位区分四队头元素的前一个位置队尾元素的下一个位置front rear 0front rear注意方案二在链式队列里还有一个典型体现就是带头结点的链式队列头结点就是front指向的“前一个位置”rear指向最后一个有效结点。这块我在第4部分会专门展开。1.3 不同方案下的入队出队操作差异理解了指向约定入队和出队的操作差异就顺理成章了。以顺序队列为例方案一的入队应该是data[rear] x; rear (rear 1) % MAXSIZE;先往rear指向的空位置写入元素然后rear后移。出队则是x data[front]; front (front 1) % MAXSIZE;先取front指向的队头元素然后front后移。注意这里都是后移动顺序不能反。方案二恰恰相反入队是rear (rear 1) % MAXSIZE; data[rear] x;rear先移动再在新位置上写数据。出队是front (front 1) % MAXSIZE; x data[front];front先移动再从新位置取数据。如果记不住可以这么理解rear指向队尾元素时rear当前指的位置是有数据的要先把rear挪到下一个空位才能写front指向队头元素的前一个位置时front当前指的位置是没用的要先把front挪到队头元素上才能取。这个顺序问题在选择题里非常爱考经常给出四个操作序列让你判断哪个正确。做题的时候别硬背把指针指向的含义想清楚自然就记住了。2. 顺序队列与循环队列指针指向的陷阱与模运算2.1 非循环顺序队列为什么会出现“假溢出”给自己队列分配一段连续的内存空间front指向队头rear指向队尾。随着入队出队的进行rear会一直往后移动直到到达数组末尾。此时即使队列前端明明还有空位rear也无法继续移动这就是“假溢出”。假溢出的本质问题在于连续存储结构下rear只朝一个方向走前面出队释放的空间没有被利用。很多教材在讲到这里的时候都会说“为了解决假溢出引入了循环队列”这句话本身没错但它在队头队尾指针指向问题上引入了一个新的关键点——当指针走到数组末尾时要能回到开头这就是取模运算。2.2 循环队列的核心操作循环队列把数组看成一个环指针移动公式统一变成front (front 1) % MAXSIZE; rear (rear 1) % MAXSIZE;这里我补充一个做题技巧取模运算的本质是“转一圈回到原位置”所以在题目中如果队列容量是m指针每移动m次就会回到原点。计算连续入队出队后指针位置时不要一步一步模拟直接用最终移动次数对m取模。比如队列容量为10初始front0连续出队8次又入队6次front的变化是(0 8) % 10 8rear这边要看rear初始值和入队次数来算跟front是独立的。很多题目把入队出队混在一起问其实front只受出队影响rear只受入队影响——只有一个元素的边界情况除外那个我在后面的例题里会提到。2.3 循环队列元素个数公式的来龙去脉在方案一front指向队头元素rear指向队尾元素下一个位置的前提下循环队列中的元素个数公式是count (rear - front MAXSIZE) % MAXSIZE这个公式很多人背下来就完事但我建议理解一下为什么。rear比front大的时候比如front2, rear7元素个数就是5直接rear减去front就行。那为什么还要加MAXSIZE再取模因为当rear“绕圈”跑到了front前面数值上小于front时直接减出来是负数。最简单的理解方式把rear看作“绝对值”它在逻辑上比front多了若干个MAXSIZE但我们只关心其相对差值所以先加MAXSIZE保证为正再取模还原。做题时如果不想每一步都套公式有一个更快的心算技巧把数组从front位置开始“剪开拉直”rear在前面的就是正常顺序元素个数等于rear减frontrear在后面的说明绕了一圈元素个数等于MAXSIZE减去front到rear的距离。练熟了之后这类题基本都是口算。3. 队空队满判断三道高频题目带你梳理3.1 牺牲一个存储单元法这是教科书和考研真题里用到最多的方式。在方案一下如果不做任何处理front rear这种情况既可能是队空也可能是队满因为队列空和队列满时指针关系一模一样。解决办法有两个大方向一个是人为制造区分点另一个是额外记录状态。牺牲一个存储单元就是前者。具体做法队列容量为MAXSIZE时最多只允许存放MAXSIZE - 1个元素留一个空位不做存储。这样队空时front rear队满时(rear 1) % MAXSIZE front。因为队满时rear紧挨着front两者之间始终空一个格子。这里我特别强调一下这个队满条件的理解它不是说rear指向的位置是空的就不能再存而是我们故意不让它存满用这个空位来区分队空队满。很多初学者误以为这个条件是为了保证rear有地方移动其实不是它就是留作“标志”。理解了这一点后面遇到计数器法和标志位法对比着看就特别清楚。3.2 计数器法计数器法不牺牲存储单元而是在队列结构体里增加一个count变量入队时count加1出队时count减1。判断队空直接看count 0队满直接看count MAXSIZE。这样虽然牺牲了一点空间一个int变量但在方案一下数组空间可以全部利用m个格子能存m个元素。这种方案做题时要注意指针本身此时无法单独区分队空队满题目如果只给front和rear的数值问“队列是空还是满”答案是“无法确定”。这时候要么给它补一个count信息要么补一个操作序列来判断。我见过有些题目在选项里故意设置这个陷阱很多同学下意识套(rear 1) % MAXSIZE front结果明明是计数器法套错了直接白给。3.3 标志位法标志位法的思路是设置一个tag变量初始为0。入队成功后让tag 1出队成功后让tag 0。判断时依然看front rear但它到底代表空还是满取决于flag的值。判断逻辑是如果front rear且tag 0说明是因为出队导致的相等队空如果front rear且tag 1说明是因为入队导致的相等队满。为什么因为无论入队还是出队只要操作成功front和rear都有可能相等这个相等是“操作后”产生的还是“本来就相等”就是tag要记录的信息。做题时标志位法与计数器法容易混淆我总结了个区分口诀计数器法统计的是“到底还有几个”标志位法记录的是“最后一次动作是入还是出”。前者能直接算出元素个数后者只能判断空满但看不出具体数量。3.4 综合例题变式rear指向队尾元素下面这道题是我当年刷题时印象很深的一道因为它把方案二和循环队列的判断方式结合起来了很多人的公式就直接套错了。题目假设循环队列容量为mfront指向队头元素rear指向队尾元素牺牲一个存储单元区分队空队满。初始时front rear 0。问队满条件和元素个数公式。如果不思考直接套方案一的公式(rear 1) % m front那就错了。当rear指向队尾元素时入队操作变为rear (rear 1) % m; data[rear] x;队满条件从(rear 1) % m front变成了(rear 2) % m front。因为rear现在指向的是最后一个元素再往下一个位置是空位再下一个位置才是front要留两个“空格”才能区分。元素个数公式也发生变化不再是(rear - front m) % m而是count (rear - front 1 m) % m你可以在草稿纸上画一个m5的小环验证front0, rear3时按方案二存储的是data[1]、data[2]、data[3]三个元素公式(3 - 0 1 5) % 5 4不对让我重新算一下。注意这个例子front0, rear3时按方案二存储的元素应该是data[1]、data[2]、data[3]共3个。公式(3 - 0 1 5) % 5 4显然不对。我再仔细推一遍。方案二下rear指向队尾元素初始front rear 0队列空。第一次入队rear先移动为1data[1]x此时front0指向队头元素的前一个位置rear1指向队头元素。只有一个元素x在data[1]。此时front0, rear1元素个数是1。如果用公式(rear - front m) % m (1 - 0 5) % 5 1居然是对的。那这个公式在不同初始条件下的形式要统一讨论。实际上当front指向队头前一个位置、rear指向队尾元素时front和rear之间“夹着”的元素个数公式恰好还是(rear - front m) % m。因为front指向的位置不算元素rear指向的位置算元素差值就是元素个数。刚才我那个“1”的推导是错的。我重新理一下方二下的队满条件容量m最多存m-1个元素牺牲一个单元。当队列满时rear指向最后一个元素front指向队头元素的前一个位置。举例front0时队头元素在data[1]队尾元素在data[m-1]假设这时快满了那么front0, rearm-1。判断条件(rear 1) % m front(m-1 1) % m 0确实等于front。那队满条件还是(rear 1) % m front但这里有个前提队列满时front和rear之间只剩下一个空位即front指向的那个“前一个位置”后面的位置。画图验证一下m5front1队头元素在data[2]存了3个元素队尾元素在data[4]剩余空位是data[0]一个。此时rear4(rear1)%5 0不等于front1所以不相等——那不是队满按这条件队里还能再存吗队满应该不能再存。再存一个的话rear (rear1)%m 0data[0] x此时队列满了存了4个元素容量5。此时front1, rear0。(rear1)%m 1等于front确实队满了。所以这个方案下队满条件还是(rear1)%m front但这个“牺牲一个单元”的含义跟方案一不同——方案一满的时候存m-1个方案二这个约定下满的时候存m-1个判断条件形式一样只是初始和入队操作不同。那我之前说“(rear2)”是推错了。我要修正这个部分。让我具体推一遍方案二front指向队头前一个位置rear指向队尾元素牺牲一个单元状态队空 front rear入队rear (rear1)%m; data[rear] x;出队front (front1)%m; x data[front];元素个数count (rear - front m) % m验证m5, front0, rear0, 空。 入arear1, data[1]a, front0。count(1-05)%51 ✓ 入brear2, data[2]b。count2 ✓ 出队front1, 取data[1]a。count(2-15)%51 ✓ 入c,d,erear3,4,0连续存储入c rear3, 入d rear4, 入e rear0。此时front1, rear0, count(0-15)%54 ✓ 队满判断(rear1)%5 1 front ✓ 满。但注意此时实际上存了4个元素b,c,d,e0号data存的是e。按牺牲一个单元的逻辑容量5存4个刚好。所以方案二在牺牲一个单元的前提下公式形式和方案一是完全一样的。我之前推加入“1”是错的应该是保持(rear - front m) % m。也就是说队首队尾指针指向类题目中只要“front指向队头前一个位置、rear指向队尾元素”这个组合被采用并且牺牲一个单元那么核心公式和方案一完全一致。区别只在入队出队的先后顺序上方案一入队先写再移rear、出队先取再移front方案二入队先移rear再写、出队先移front再取。这样实际上更简单。我需要把这个推导过程在文中讲清楚。刚才在思考中发现的内容修正很有价值这种“推着推着发现公式其实一样”的经验正好可以写成博文中的“容易踩坑的地方”。好我在第2章或第3章以这个为素材写。那方案三里提到的“front指向队头元素rear指向队尾元素”呢如果牺牲一个单元判断公式又是怎样的这个组合下初始front0, rear0队空。入队时data[rear] x; rear (rear1)%m; ← 参考循环队列经典实现有一些教材就是这样入队直接写rear所指位置然后rear后移。出队时x data[front]; front (front1)%m;这样其实rear“指向队尾元素”就不太对因为rear在入队后被移到了一个空位置除非说入队前rear指向的是队尾元素的下一个位置。哦所以说“rear指向队尾元素”且入队先写的话写完后rear应该不再移动但为了管理空位通常写成data[rear]x后rear保持不变下一次入队则到下一个位置所以rear又该移动了。这样rear最终在哪取决于具体实现。这就是为什么“front指向队头元素、rear指向队尾元素”配合牺牲单元的方式实际很少单独在顺序循环队列中用因为不好统一。这也是有些教材虽然按“方案三”描述指针但代码里实际上把rear当作“队尾元素的下一个位置”在用。做真题时遇到这种情况要仔细看初始化和操作的描述别看到“rear指向队尾元素”就直接套某个公式。我在文中要提醒这些不同方案本质上都是给“空/满判断”留口子真正的核心是指针移动顺序。只要画图一切都很清晰。现在我需要在正式写正文前把几个容易出错的公式完全理清结论方案一front指向队头元素rear指向队尾元素下一个位置牺牲单元法入队data[rear] x; rear (rear1)%MAX出队x data[front]; front (front1)%MAX队空front rear队满(rear1)%MAX front元素个数(rear-frontMAX)%MAX方案二front指向队头元素前一个位置rear指向队尾元素牺牲单元法入队rear (rear1)%MAX; data[rear] x出队front (front1)%MAX; x data[front]队空front rear队满(rear1)%MAX front元素个数(rear-frontMAX)%MAX跟方案一公式完全一致操作顺序相反。方案三front指向队头元素rear指向队尾元素牺牲单元法这个组合下经典写法有两种取决于入队时怎么移动指针。如果入队data[rear]x; rear(rear1)%MAX那rear实际上是“队尾元素下一个位置”归到方案一如果入队先移rear再写data[rear]x那归到方案二。所以看到“rear指向队尾”要小心。如果真按front指向队头元素、rear指向队尾元素且不额外移动那么需要tag或count才能判断空满牺牲单元法无法自洽。元素个数公式在两种可行方案下都一样这其实是个很好记的结论。好那我第3章的变式题就可以写成题干说“某循环队列的front指向队头元素rear指向队尾元素”然后问判断队空队满及元素个数——先分析它本质上属于哪种可行约定还是需要用标志位。这样既严谨又有内容。不过对于初学者可能看到这里有点晕。写作时我会把“先画图、再确认约定”作为核心方法论贯穿始终。接下来第4章链式队列链式队列主要是带头结点和不带头结点两种。带头结点链式队列typedef struct LinkNode { int data; struct LinkNode *next; } LinkNode; typedef struct { LinkNode *front, *rear; } LinkQueue;初始化front rear (LinkNode*)malloc(sizeof(LinkNode)); front-next NULL; 队空front rear都指向头结点 入队将新结点s链到rear后面rear s 出队删除front后面的结点p如果p是最后一个结点p rear则删除后rear front这里注意出队时如果删的是最后一个元素rear必须更新为front否则rear变成野指针。这个在选择题中常作为判断点。而且“front-next NULL”也可以判断队空不过更直接的是front rear。不带头结点链式队列 初始化front rear NULL 队空front NULL也等价于rear NULL 入队若队空则 front rear s否则 rear-next s; rear s; 出队x front-data; front front-next;若删除后front NULL需要令rear NULL不带头结点的链式队列第一个元素入队时front和rear都要指向它这是很多初学者容易漏掉的处理。链式队列一般不涉及“假溢出”存储空间动态分配只要内存够就能入队所以front和rear通常用NULL来判断空。第5章题目速查我要设计几道具体题目例1容量为8初始front rear 0方案一。依次入队a,b,c,d出队a入队e,f出队b入队g求front和rear。 解入队4次rear4出队1次front1入队2次rear6出队1次front2入队1次rear7。所以front2, rear7, 队列中元素是c,d,e,f,g共5个。验证公式(7-28)%85 ✓例2同容量8历经若干操作后front5, rear2求元素个数及还能入队几个元素。 元素个数(2-58)%85。还能入队几个取决于是否牺牲一个单元。若牺牲一个队满条件是(rear1)%8front即(21)%83front5不相等最多存7个当前5个还能入队2个。但如果用计数器法容量8当前5个还能入队3个。这个差别很重要也可以作为对比。例3链式队列题目 带头结点链式队列 front和rear初始都指向头结点。入队x1入队x2出队x1此时front-next指向x2rear指向x2判断队空答案是front rear不front是头结点rear是x2不相等不为空。再出队x2此时需要执行pfront-nextp是x2front-next p-nextNULL因为p rear所以rear front。此后front rear队空。不带头结点frontrearNULL为空入x1后frontrearx1结点入x2后rear指向x2front仍指向x1出x1后front指向x2出x2后frontNULL必须把rear也置为NULL否则rear仍指向已释放结点。这是一个经典易错点。例4综合指针推算 已知循环队列容量m10front3rear7方案一问元素个数(7-310)%104队是否可再入队牺牲一个单元方案(71)%108front3不相等可以。还可以入队几个最多存9个现有4个最多还能入队5个。验证rear从7到9连续入队能入3个到rear0此时rear0(01)%101front3不相等再入1个rear1(11)%102front3不等再入1个rear2(21)%103front此时满。共入队5个。✓ 这个通过“追击”算也可以队满前空位有(front - rear - 1 m) % m个m10时(3-7-110)%105 ✓好第5章内容很丰富。第6章扩展阻塞队列Java ArrayBlockingQueue 的putIndex/takeIndex就是front/rear的工程版takeIndex取元素就是队头指针putIndex放元素就是队尾指针capacity-1个元素时队满其实就是牺牲一个单元或者用count变量。ArrayBlockingQueue用的是count跟计数器法一模一样。LinkedBlockingQueue头结点是一个哨兵节点跟带头结点链式队列一样入队加在尾部出队从头部剔除。消息队列consumer的offset类似队头指针生产者写入的位置类似队尾指针。消息队列重复消费问题与“消费位点未更新”相关就是offset没有正确推进。想想kafka术语中消费者的position就是队头指针。FreeRTOS队列xQueueSend往队尾写xQueueReceive从队头读内部用uxItemSize、uxMessagesWaiting等字段指针管理思路与循环队列异曲同工。以及提到的stm32cubemx空闲中断串口接收队列也可以稍微提一句本质就是用环形缓冲区管理串口数据队头出队处理队尾入队存储。线程池的阻塞队列选择ArrayBlockingQueue有界、LinkedBlockingQueue可选有界、SynchronousQueue不存储直接传递。Taylor任务队列的peek/take与队头指针关系。第6章只要点到为止不要脱离主题重点是“同一套指针思想”。我还要注意热搜词里有一些“消息队列重复消费问题”、“duke队列”、“bqueues查看队列权限”、“队列换道轨迹规划”等这些并不完全适配“队头指针队尾指针指向类题目”这个主题。不过结构上可以自然衔接到工程场景比如消息队列重复消费问题可以简单提一下消费指针管理不当会导致问题但要控制篇幅不喧宾夺主。现在开始写正文。确保开头 ≥ 200字前100字内融入“队列”“队头指针”“队尾指针”主体 ≥ 5000字至少4个H2我计划6个每个H2下至少2个H3所有H2/H3必须有编号每段至少150字不用emoji不用mermaid不用AI套话最后不做总结式结尾。我直接以个人经验式收尾。好开始输出。 前前后后也带过不少考研和面试的学生每次讲到队列第一个绕不开的点就是“队头指针和队尾指针到底指向谁”。说实话这问题不怪大家发懵因为不同教材、不同题目里的front和rear定义真的不一样。同一个容量为10的循环队列有的题里rear指向队尾元素有的题里rear指向队尾元素的下一个空位理论上来讲这题就完全变成了两道题。我自己当年也是被这种“约定不一致”坑过好几次后来刷题总结出一套方法拿到题目先看front和rear的指向约定再决定套哪套公式几乎不会再错。这篇文章就是想把这套方法完整地交给你。我会把最常见的几种指针约定、对应的入队出队操作顺序、队空队满判断方式、元素个数计算技巧以及链式队列里front和rear的特殊处理全部过一遍最后用具体例题带你再走一遍推算过程。不管你是考研党刷数据结构还是准备面试手撕算法又或者工作中突然需要自己实现一个环形缓冲这套东西都用得上。1. 先搞懂队头指针和队尾指针到底指向谁1.1 为什么指针指向是队列题的“题眼”队列的逻辑很简单——先进先出但“队头”和“队尾”落到代码层面是有歧义的。rear叫队尾指针但有的实现里它指向最后一个元素有的实现里它指向最后一个元素后面的空位front叫队头指针但有的实现里它指向第一个元素有的实现里它指向第一个元素前面的那个“废弃位”。这个差异直接影响三件事初始化时front和rear的值、入队和出队时指针的移动顺序、队空队满的判断条件。题目如果不说清楚front和rear的指向你甚至没法确定答案是哪个选项。很多同学做题出错不是不会算而是拿着A方案的公式去做B方案的题那必然对不上。我自己的经验是面对这类题第一步永远是画图。拿一支笔画出队列的格子标上front和rear指向的位置然后按照题目给的操作序列一步一步推。画完一张图题目的答案基本就出来了。这个习惯我到现在还在用工作中排查环形缓冲区问题也是这么干的。1.2 三种最常用的指针约定方案把市面常见教材和历年真题刷过一遍后我归纳出三种最常用的front和rear约定。方案一front指向队头元素rear指向队尾元素的下一个位置。这是考研大纲和大多数数据结构教材默认的方式。初始化时front rear 0。入队时先把数据写入rear指向的位置再将rear加1出队时先取出front指向的数据再将front加1。队空的判断条件是front rear。牺牲一个存储单元时队满条件是(rear 1) % MAXSIZE front。元素个数是(rear - front MAXSIZE) % MAXSIZE。方案二front指向队头元素的前一个位置rear指向队尾元素。这种方案下front指向的位置实际上是一个“前哨位”不存有效数据。初始化时front rear 0这里的0可以理解为头结点或队头元素的前一个下标。入队时先将rear加1再把数据写入新位置出队时先将front加1再从新位置取出数据。需要通过牺牲一个存储单元来区分空满时判断公式和方案一完全一致但操作顺序正好反过来。方案三front指向队头元素rear指向队尾元素。两个指针都指向实际元素。这种方案最大的问题是队空和队满时front和rear的相对位置关系很难用统一公式区分往往要配合计数器或标志位来使用。有些题目描述中用这种约定但给出的操作序列实际上用的是方案一或方案二做题时一定要留个心眼。我把三种方案的核心差异整理成了一张表方便对比方案front指向rear指向入队顺序出队顺序空满区分一队头元素队尾元素的下一个空位先写data[rear]再rear1先取data[front]再front1可牺牲单元或计数器二队头元素的前一个位置队尾元素先rear1再写data[rear]先front1再取data[front]可牺牲单元或计数器三队头元素队尾元素视实现而定视实现而定必须计数器/标志位1.3 操作顺序怎么记才不会混不同方案下入队出队的先后顺序很容易搞混。我提供一个自己的记忆方法看rear当前指向的位置是不是“能直接写的位置”。方案一中rear指向空位所以一进来就可以写数据方案二中rear指向最后一个有效数据必须先移动指针腾出一个空位再写。front的处理也类似方案一中front指向有效数据所以先取数据再移走方案二中front指向无效位置所以先移到有效位置再取数据。理解了这个逻辑就不用死记“先移动还是后移动”了。做题时只要在草稿纸上标一下“当前这个指针指向的位置有没有有效数据”序就写不错。我还见过一些人把这个总结成口诀“rear空则先写rear实则先动front实则先取front虚则先动”你也可以参考但最靠谱的还是画图。2. 顺序队列与循环队列指针指向的陷阱2.1 非循环顺序队列为什么会出现“假溢出”顺序队列用一段连续数组存元素front和rear都在数组下标范围内移动。每次入队rear后移每次出队front后移。随着操作次数增多rear会一路移向数组末尾到末尾时就无法再入队了——哪怕数组前头空着一大片位置。这就是“假溢出”。队列逻辑上没满物理存储却满了。解决假溢出的主流方案就是把数组“首尾相接”成循环队列让rear走到MAXSIZE - 1后下一步回到0。这样一来tail的移动从单纯的“加1”变成了“加1再对MAXSIZE取模”。循环队列虽然解决了假溢出的问题但也把队头队尾指针的指向问题变得更加隐蔽。因为指针一旦可以绕圈front和rear谁大谁小就不再能直观反映队列里有多少元素了。很多题目专门考这一点。2.2 循环队列指针移动的取模运算循环队列的所有指针移动都遵循这个公式front (front 1) % MAXSIZE; rear (rear 1) % MAXSIZE;做题的时候连续入队出队多次不需要逐步模拟。直接看front总共被加了几次、rear总共被加了几次然后用总数对MAXSIZE取模就行。这里要注意入队只会让rear向前推进出队只会让front向前推进。不要把“入队n次出队m次后”直接算成rear移动n次、front移动m次这个方向别搞反。队列容量为m时指针每移动m次回到原位置所以取模后的结果只和移动总次数有关。举个例子容量为10初始front 0连续出队7次又出队3次后front (0 10) % 10 0。这个式子跟“先7后3”还是“一起10次”无关最终取模看的是总次数。2.3 元素个数公式到底是哪来的在方案一的约定下队列元素个数的标准公式是count (rear - front MAXSIZE) % MAXSIZE很多同学只是背下来没有想过它为什么成立。我来讲一下。当rear大于front时元素个数就是rear - front很直观。当rear小于front时说明rear绕了一圈跑到了front后面此时实际个数是(MAXSIZE - front) rear也就是rear - front MAXSIZE。把这两种情况统一起来就是对MAXSIZE取模。我提供一个心算技巧把数组从front位置剪开拉成一条直线。如果rear在front右边直接减如果rear在front左边就用MAXSIZE减去两者之间的距离。多练几次这种题就是秒算。顺带提醒一个很容易犯的错有人会把公式写成(rear - front) % MAXSIZE少了加MAXSIZE这一步。当rear小于front时这个式子算出来是个负数结果完全错误。所以加MAXSIZE不能省它本质上是把“借一位”这件事显式写了出来。3. 队空队满判断核心题型的分类破解3.1 牺牲一个存储单元法最经典的判空判满方案一下如果不做任何附加处理front rear既可能是队空也可能是队满。为什么会这样因为队列空和队列满时front和rear的相对位置完全相同。为了区分最直接的办法就是人为少存一个元素——把数组容量为m的队列最多只存m - 1个元素留一个空位做标志。队空时front rear队满时(rear 1) % MAXSIZE front。为什么队满条件是“加1等于front”因为队满时rear指向最后一个有效元素的下一个位置而front指向队头元素两者之间恰好空着一个格子。当rear再往前移动一个位置就会碰到front此时说明“如果我继续入队队列就真的满了”。这个判断本身并不是禁止你入队而是告诉你“在这个约定下如果现在入队空满就无法区分了”。这个方案下还有一个衍生考点队列还能容纳多少个元素空位数公式是(front - rear - 1 MAXSIZE) % MAXSIZE。这个我不建议死记画图画多了自然就推出来了。3.2 计数器法用额外变量绕开指针歧义计数器法不牺牲存储空间而是在结构体里加一个count字段。入队成功count加1出队成功count减1。队空条件count 0队满条件count MAXSIZE。数组里的m个格子可以全部用来存数据。这种方案做题时的坑在于题目如果只给front和rear的数值问“队列是空还是满”在计数器法下光靠这两个指针是判断不了的。此时正确答案是“无法确定”除非题干里给出了count的信息。我印象中有些选择题特别喜欢这么挖坑把两种方案混在一道题里先用计数器法描述队列结构问队满条件时又有人下意识写(rear 1) % MAXSIZE front结果错了。做题时看清楚题干里有没有count或者tag字段有的话优先用它们判断。3.3 标志位法用最后一次动作区分空满标志位法同样是为了让m个格子都能存数据。维护一个tag变量初始为0。入队成功后令tag 1出队成功后令tag 0。判断时如果front rear就看tagtag 0说明最后一次操作是出队这个相等是由出队导致的队列为空。tag 1说明最后一次操作是入队这个相等是由入队导致的队列为满。这个方法的核心逻辑是无论入队还是出队操作成功之后指针都有可能相等但这个相等的“原因”不同。之所以能区分是因为队列由空变满的过程中指针相等只能发生在入队之后由满变空的过程中指针相等只能发生在出队之后。与计数器法对比计数器法统计的是“当前到底存了几个”标志位法记录的是“最后一次动作是入还是出”。前者能算出精确数量后者只能判断空满状态但算不出数量。两个方法常被考到区别答题时不要混。3.4 变式题rear指向队尾元素时该怎么算现在我把前面讲的内容综合到一道变式题里。题目描述循环队列容量为mfront指向队头元素的前一个位置rear指向队尾元素初始front rear 0问队空、队满条件和元素个数公式。这道题看着和方案二很像实际确实是方案二的直接应用。入队时由于rear指向的是最后一个有效元素必须先移动rear再写也就是rear (rear 1) % m; data[rear] x;出队时由于front指向的是没有有效数据的前哨位置必须先移动front再取front (front 1) % m; x data[front];请你特别注意这种情况下队空条件和队满公式与方案一完全一致。队空front rear队满条件依然是(rear 1) % m front元素个数依然是(rear - front m) % m。很多同学一看到“rear指向队尾元素”就慌觉得公式肯定要变实际推一遍就会发现并没有变。为什么没变因为front和rear的相对定义虽然和方案一不同但它们的“差值”所包含的元素个数关系保持一致。front前哨位不计数rear本身计数差值恰好等于队列元素个数。这就是我前面强调的推导公式时别靠感觉画图验证最重要。我当时也是推了一遍才彻底放下心来。4. 链式队列的队头队尾指针4.1 带头结点和不带头结点的差异链式队列分为带头结点和不带头结点两种。这两种情况下front和rear的语义差别很大也是链式队列最容易出考点的地方。带头结点的链式队列头结点是一个dummy结点不存有效数据。front始终指向这个头结点rear指向最后一个有效结点。初始化时front rear 头结点地址。判断队空的条件是front rear此时队列里没有任何有效结点。不带头结点的链式队列front直接指向第一个有效结点rear指向最后一个有效结点。初始化时front rear NULL。判断队空的条件是front NULL等价于rear NULL。有一个细节很多人忽略带头结点的链式队列中即便队列里只有一个元素入队时也只需要修改rearfront一直指向头结点不动而不带头结点的队列插入第一个元素时必须同时让front和rear都指向这个新结点因为队列从空变成非空队头也变了。4.2 链式队列入队出队的指针操作细节先看不带头结点的链式队列入队LinkNode *s (LinkNode*)malloc(sizeof(LinkNode)); s-data x; s-next NULL; if (rear NULL) { front rear s; } else { rear-next s; rear s; }注意第一个结点特殊处理如果忘记判断rear NULL直接执行rear-next s就会对空指针解引用程序直接崩溃。再看不带头结点的链式队列出队LinkNode *p front; x p-data; front front-next; free(p); if (front NULL) { rear NULL; }出队后如果队列变成空必须让rear也变成NULL。因为rear之前还指向被删除的那个结点如果不更新后续入队判断rear NULL就失效了。这个点特别容易考到也是实际写代码时经常踩的坑。带头结点的链式队列出队略有不同因为有一个头结点垫底front不会变成NULL所以不需要像不带头结点那样处理空队列。但删除最后一个有效结点时需要重置rear为front否则rear就变成了悬空指针。4.3 链式队列为什么不需要“队满”判断链式队列的空间是动态分配的理论上只要内存足够就能一直入队。所以它天然不存在顺序队列的“假溢出”问题。链式队列一般只需要判断队空不需要判断队满。这是一个和顺序队列很大的区别做题时经常作为判断项出现。如果你在题目里看到“链式队列采用牺牲一个存储单元的方法判断队满”那大概率是错误选项。链式队列的容量根本不由数组限制队列能存多少取决于堆内存。这一点在面试中也经常被问到比如“普通队列和循环队列的区别”或者“链式队列和顺序队列各自适合什么场景”。5. 实战刷题队头队尾指针指向类题目速查5.1 题型一给定操作序列推算front和rear的最终指向这类题核心就是确认方案分清哪些操作影响front、哪些影响rear然后用取模汇总次数。我用一道完整例题演示。循环队列容量MAXSIZE 8采用方案一front指向队头元素rear指向队尾元素的下一个位置初始front rear 0。依次执行入队a、b、c、d出队a入队e、f出队b入队g推算过程入队a、b、c、d共入队4次rear (0 4) % 8 4front不变仍为0。出队a共出队1次front (0 1) % 8 1rear不变仍为4。入队e、f共入队2次rear (4 2) % 8 6front仍为1。出队b共出队1次front (1 1) % 8 2rear仍为6。入队g共入队1次rear (6 1) % 8 7front仍为2。最终front 2rear 7。队列里实际元素是c、d、e、f、g一共5个。用公式验证(7 - 2 8) % 8 5完全一致。这道题如果按“逐步移动”的方式去模拟容易绕晕但把入队次数和出队次数分开统计就非常清爽。做题时可以在草稿纸上写两行“front被加x次rear被加y次”然后对容量取模。5.2 题型二给定front和rear反推元素个数和剩余容量另一类常见题是已知操作后的指针位置反推队列状态。比如容量maxsize 10front 3rear 7方案一问队列元素个数、能否继续入队、还能入队几个元素。元素个数(7 - 3 10) % 10 4。牺牲一个存储单元时最多存9个当前4个所以还能入队5个。验证方式从rear 7出发入队3个后rear 0此时(0 1) % 10 1front 3不相等仍可入队继续入队到rear 2时(2 1) % 10 3与front相等队满。总共在原来基础上又入队了5个。这类题还有另一种考法计数器和标志位方案下同样给出front和rear让你判断空满答案是“无法仅凭指针确定”。一定要看题目有没有额外信息。5.3 题型三链式队列的指针状态判断用一道经典真题变式练手。带头结点的链式队列初始front rear 头结点。依次入队x1、x2再出队x1。问当前front和rear的指向以及队列是否为空。入队x1rear-next x1结点rear指向x1。此时front仍指向头结点rear指向x1两者不相等。 入队x2rear-next x2结点rear指向x2。front仍指向头结点。 出队x1p front-nextp是x1结点front-next p-next此时front-next变成了x2free(p)。因为p不是rear所以rear保持指向x2。 最终front指向头结点头结点的next指向x2rear指向x2。队列不为空因为front ! rear。如果把x2也出队p front-nextp是x2front-next p-next为NULL因为p rear所以必须执行rear front。此时front rear队列为空。这一步就是前面说的“删除最后一个有效结点要复位rear”务必记住。5.4 易错点自查清单我把刷题过程中反复遇到的易错点整理成一个清单你在做题前快速过一遍拿到题先确认front和rear的指向约定不能凭印象默认全教材一致。“rear指向队尾元素”不一定改变元素个数公式要看front指向哪里以及操作顺序怎么定义。入队出队的“先移动、后写入”或者“先读取、后移动”每一步都对应指针当前指向有没有有效数据。链式队列带头结点和不带头结点的队空条件不同两个都要记住。链式队列删除最后一个结点时带头结点要重置rear front不带头结点要重置rear NULL。计数器法和标志位法下不能仅凭front和rear判断队空队满。容量为m、牺牲一个存储单元时最多存储m - 1个元素这个“1”的空位是空满判断的关键。6. 从教科书指针到工程队列同一套思想6.1 阻塞队列里的队头队尾指针如果你用过Java的ArrayBlockingQueue会发现它的内部结构特别眼熟takeIndex对应队头指针putIndex对应队尾指针count计数当前元素数量。这正是教科书里“front指针 rear指针 count计数器”组合的工程实现。LinkedBlockingQueue则更像带头结点的链式队列内部有一个哨兵头结点出队时从头结点后取第一个节点入队时往链表尾部追加。生产者和消费者通过lock和condition协调但底层指针管理思路和我们在第4部分讲的链式队列一模一样。理解了这个关联再看线程池的阻塞队列选择题目就非常清晰了。有界队列用ArrayBlockingQueue是因为需要容量限制避免任务无限堆积无界队列用LinkedBlockingQueue是因为允许任务持续排队。题面换个包装问的还是“队满时怎么办、队空时怎么办”这些老问题。6.2 消息队列的消费位点管理消息队列里也有类似队头指针的概念比如消费者维护的消费位点offset。读消息相当于“从队头取数据”读完提交位点相当于“更新队头指针”。生产端写入的位置则对应队尾指针。“消息队列重复消费问题”为什么会发生本质就是消费位点没有被正确提交队头指针停留在旧位置下次还要再读一次同一批消息。这个问题的解决思路也很像循环队列的约定问题厘清“当前位点指向已经消费的消息还是指向下一条待消费的消息”把约定统一好重复和丢失就能规避。6.3 嵌入式队列和串口缓冲再看嵌入式场景FreeRTOS的消息队列、串口空闲中断接收数据时常用的环形缓冲区本质上都是同一套东西。环形缓冲区的读指针就是队头指针写指针就是队尾指针判空判满条件跟前面公式如出一辙。用STM32CubeMX配置空闲中断加串口接收时很多人把接收缓冲写成环形队列接收中断往队尾写数据主循环从队头读数据。只要队头队尾指针的移动和判断写对了整个收发流程就非常稳。反过来如果指针判断出错就会出现数据覆盖或者漏读这和做数据结构题的“空满判断错误”是一样的后果。我个人在实际使用中最大的体会是队列这种东西如果只停留在做题层面很多细节记了又忘但一旦把它跟工程里的具体场景对照起来比如哪天你自己写一个环形缓冲区再回头看那些front、rear的公式就会觉得理所当然。所以建议你把第3部分的推演过程亲手在草稿纸上画一遍再用第5部分的例题验证一次之后不管题目怎么变都不太容易再被“指向谁”这个问题绊住了。
队列队头队尾指针指向全解析：循环队列与链式队列的判空判满与元素个数
说实话队列这块的知识点很多初学者最容易栽的地方不是队列本身而是“队头指针”和“队尾指针”到底指向哪。明明代码能背下来一做到选择题让你判断front和rear的值或者问你队满条件是什么就开始发懵。我自己也是从那个阶段过来的考研复习那会儿没少为“front指向队头元素还是队头元素的前一个位置”这种问题跟同学争得面红耳赤。后来刷题多了才发现这类题目其实套路非常固定核心就一条先确认这套题用的是哪套指针约定再套对应的公式和判断条件。一旦把不同方案的初始指向、入队出队后指针的变化规律理清楚不管题目怎么变都是同一个模板。这篇文章我打算把这些队头指针、队尾指针的指向问题进行系统梳理覆盖顺序队列、循环队列、链式队列里最常见的几种定义方式再用具体的例题演示怎么根据操作序列推算指针指向、怎么求元素个数、怎么判断队空队满。最后顺便聊聊这块经典知识在真实工程里的影子比如线程池的阻塞队列、消息队列消费位置管理其实都是同一套思路。适合正在准备考研数据结构、刷算法题或者面试前想快速把队列基础过一遍的朋友。1. 先搞懂队头指针和队尾指针到底指向谁1.1 为什么指针指向是队列题的“题眼”队列的逻辑是先进先出这所有人都知道。但落到代码实现层面“队头”和“队尾”这两个概念其实是有歧义的因为不同教材、不同参考书对front和rear的定义并不完全一致。同样是“队尾指针”有的指向队尾元素本身有的指向队尾元素的下一个空位置。这一点差异直接决定了初始化代码、入队出队的写法、队满判断条件甚至元素个数的计算公式都不一样。所以做队头队尾指针指向类题目第一件事不是急着套公式而是先看题目默认采用哪种约定。很多同学做题出错不是不会算而是拿着A方案的公式去做B方案的题那结果必然对不上。这块说严重点就像平时用厘米量长度考试的时候题目用的是英寸你不换算直接写数字肯定错。1.2 四种常见指针约定方案对比我把刷题过程中见过的题型归纳了一下常见的front和rear指向约定基本就四种其中前两种出现频率最高后两种偶尔考到。先把这几种方案的“初始状态”和“入队出队后怎么变”列出来后续所有题目都是在这个基础上衍生出来的。方案一考研最常见front指向队头元素rear指向队尾元素的下一个位置。也就是说rear指向的是队尾后面那个空位。判断队空时front rear入队时先写数据再让rear后移出队时先取front所指元素再让front后移。很多教材默认用这种方案。方案二front指向队头元素的前一个位置rear指向队尾元素。这种方案下初始化不是从0开始了而是front和rear都指向某个“前哨”位置。入队时rear先移动再写入出队时front先移动再取出。判断队空同样是front rear但含义跟方案一略有不同。方案三front指向队头元素rear指向队尾元素。两个指针都指向实际元素初始化时队空比较特殊一般需要额外的计数器或标志位来区分队空和队满因为当队列满的时候front和rear也会指向首尾元素光靠指针关系区分不了。方案四front指向队头元素的前一个位置rear指向队尾元素的下一个位置。这种约定不多见一般出现在某些特定教材或个别学校的考研真题里属于“看起来不一样算起来更绕”的类型。表格归纳一下方案front指向rear指向初始状态队空判断一队头元素队尾元素的下一个空位front rear 0front rear二队头元素的前一个位置队尾元素front rear 0指向头结点或前哨位front rear三队头元素队尾元素需标志位/计数器辅助靠标志位区分四队头元素的前一个位置队尾元素的下一个位置front rear 0front rear注意方案二在链式队列里还有一个典型体现就是带头结点的链式队列头结点就是front指向的“前一个位置”rear指向最后一个有效结点。这块我在第4部分会专门展开。1.3 不同方案下的入队出队操作差异理解了指向约定入队和出队的操作差异就顺理成章了。以顺序队列为例方案一的入队应该是data[rear] x; rear (rear 1) % MAXSIZE;先往rear指向的空位置写入元素然后rear后移。出队则是x data[front]; front (front 1) % MAXSIZE;先取front指向的队头元素然后front后移。注意这里都是后移动顺序不能反。方案二恰恰相反入队是rear (rear 1) % MAXSIZE; data[rear] x;rear先移动再在新位置上写数据。出队是front (front 1) % MAXSIZE; x data[front];front先移动再从新位置取数据。如果记不住可以这么理解rear指向队尾元素时rear当前指的位置是有数据的要先把rear挪到下一个空位才能写front指向队头元素的前一个位置时front当前指的位置是没用的要先把front挪到队头元素上才能取。这个顺序问题在选择题里非常爱考经常给出四个操作序列让你判断哪个正确。做题的时候别硬背把指针指向的含义想清楚自然就记住了。2. 顺序队列与循环队列指针指向的陷阱与模运算2.1 非循环顺序队列为什么会出现“假溢出”给自己队列分配一段连续的内存空间front指向队头rear指向队尾。随着入队出队的进行rear会一直往后移动直到到达数组末尾。此时即使队列前端明明还有空位rear也无法继续移动这就是“假溢出”。假溢出的本质问题在于连续存储结构下rear只朝一个方向走前面出队释放的空间没有被利用。很多教材在讲到这里的时候都会说“为了解决假溢出引入了循环队列”这句话本身没错但它在队头队尾指针指向问题上引入了一个新的关键点——当指针走到数组末尾时要能回到开头这就是取模运算。2.2 循环队列的核心操作循环队列把数组看成一个环指针移动公式统一变成front (front 1) % MAXSIZE; rear (rear 1) % MAXSIZE;这里我补充一个做题技巧取模运算的本质是“转一圈回到原位置”所以在题目中如果队列容量是m指针每移动m次就会回到原点。计算连续入队出队后指针位置时不要一步一步模拟直接用最终移动次数对m取模。比如队列容量为10初始front0连续出队8次又入队6次front的变化是(0 8) % 10 8rear这边要看rear初始值和入队次数来算跟front是独立的。很多题目把入队出队混在一起问其实front只受出队影响rear只受入队影响——只有一个元素的边界情况除外那个我在后面的例题里会提到。2.3 循环队列元素个数公式的来龙去脉在方案一front指向队头元素rear指向队尾元素下一个位置的前提下循环队列中的元素个数公式是count (rear - front MAXSIZE) % MAXSIZE这个公式很多人背下来就完事但我建议理解一下为什么。rear比front大的时候比如front2, rear7元素个数就是5直接rear减去front就行。那为什么还要加MAXSIZE再取模因为当rear“绕圈”跑到了front前面数值上小于front时直接减出来是负数。最简单的理解方式把rear看作“绝对值”它在逻辑上比front多了若干个MAXSIZE但我们只关心其相对差值所以先加MAXSIZE保证为正再取模还原。做题时如果不想每一步都套公式有一个更快的心算技巧把数组从front位置开始“剪开拉直”rear在前面的就是正常顺序元素个数等于rear减frontrear在后面的说明绕了一圈元素个数等于MAXSIZE减去front到rear的距离。练熟了之后这类题基本都是口算。3. 队空队满判断三道高频题目带你梳理3.1 牺牲一个存储单元法这是教科书和考研真题里用到最多的方式。在方案一下如果不做任何处理front rear这种情况既可能是队空也可能是队满因为队列空和队列满时指针关系一模一样。解决办法有两个大方向一个是人为制造区分点另一个是额外记录状态。牺牲一个存储单元就是前者。具体做法队列容量为MAXSIZE时最多只允许存放MAXSIZE - 1个元素留一个空位不做存储。这样队空时front rear队满时(rear 1) % MAXSIZE front。因为队满时rear紧挨着front两者之间始终空一个格子。这里我特别强调一下这个队满条件的理解它不是说rear指向的位置是空的就不能再存而是我们故意不让它存满用这个空位来区分队空队满。很多初学者误以为这个条件是为了保证rear有地方移动其实不是它就是留作“标志”。理解了这一点后面遇到计数器法和标志位法对比着看就特别清楚。3.2 计数器法计数器法不牺牲存储单元而是在队列结构体里增加一个count变量入队时count加1出队时count减1。判断队空直接看count 0队满直接看count MAXSIZE。这样虽然牺牲了一点空间一个int变量但在方案一下数组空间可以全部利用m个格子能存m个元素。这种方案做题时要注意指针本身此时无法单独区分队空队满题目如果只给front和rear的数值问“队列是空还是满”答案是“无法确定”。这时候要么给它补一个count信息要么补一个操作序列来判断。我见过有些题目在选项里故意设置这个陷阱很多同学下意识套(rear 1) % MAXSIZE front结果明明是计数器法套错了直接白给。3.3 标志位法标志位法的思路是设置一个tag变量初始为0。入队成功后让tag 1出队成功后让tag 0。判断时依然看front rear但它到底代表空还是满取决于flag的值。判断逻辑是如果front rear且tag 0说明是因为出队导致的相等队空如果front rear且tag 1说明是因为入队导致的相等队满。为什么因为无论入队还是出队只要操作成功front和rear都有可能相等这个相等是“操作后”产生的还是“本来就相等”就是tag要记录的信息。做题时标志位法与计数器法容易混淆我总结了个区分口诀计数器法统计的是“到底还有几个”标志位法记录的是“最后一次动作是入还是出”。前者能直接算出元素个数后者只能判断空满但看不出具体数量。3.4 综合例题变式rear指向队尾元素下面这道题是我当年刷题时印象很深的一道因为它把方案二和循环队列的判断方式结合起来了很多人的公式就直接套错了。题目假设循环队列容量为mfront指向队头元素rear指向队尾元素牺牲一个存储单元区分队空队满。初始时front rear 0。问队满条件和元素个数公式。如果不思考直接套方案一的公式(rear 1) % m front那就错了。当rear指向队尾元素时入队操作变为rear (rear 1) % m; data[rear] x;队满条件从(rear 1) % m front变成了(rear 2) % m front。因为rear现在指向的是最后一个元素再往下一个位置是空位再下一个位置才是front要留两个“空格”才能区分。元素个数公式也发生变化不再是(rear - front m) % m而是count (rear - front 1 m) % m你可以在草稿纸上画一个m5的小环验证front0, rear3时按方案二存储的是data[1]、data[2]、data[3]三个元素公式(3 - 0 1 5) % 5 4不对让我重新算一下。注意这个例子front0, rear3时按方案二存储的元素应该是data[1]、data[2]、data[3]共3个。公式(3 - 0 1 5) % 5 4显然不对。我再仔细推一遍。方案二下rear指向队尾元素初始front rear 0队列空。第一次入队rear先移动为1data[1]x此时front0指向队头元素的前一个位置rear1指向队头元素。只有一个元素x在data[1]。此时front0, rear1元素个数是1。如果用公式(rear - front m) % m (1 - 0 5) % 5 1居然是对的。那这个公式在不同初始条件下的形式要统一讨论。实际上当front指向队头前一个位置、rear指向队尾元素时front和rear之间“夹着”的元素个数公式恰好还是(rear - front m) % m。因为front指向的位置不算元素rear指向的位置算元素差值就是元素个数。刚才我那个“1”的推导是错的。我重新理一下方二下的队满条件容量m最多存m-1个元素牺牲一个单元。当队列满时rear指向最后一个元素front指向队头元素的前一个位置。举例front0时队头元素在data[1]队尾元素在data[m-1]假设这时快满了那么front0, rearm-1。判断条件(rear 1) % m front(m-1 1) % m 0确实等于front。那队满条件还是(rear 1) % m front但这里有个前提队列满时front和rear之间只剩下一个空位即front指向的那个“前一个位置”后面的位置。画图验证一下m5front1队头元素在data[2]存了3个元素队尾元素在data[4]剩余空位是data[0]一个。此时rear4(rear1)%5 0不等于front1所以不相等——那不是队满按这条件队里还能再存吗队满应该不能再存。再存一个的话rear (rear1)%m 0data[0] x此时队列满了存了4个元素容量5。此时front1, rear0。(rear1)%m 1等于front确实队满了。所以这个方案下队满条件还是(rear1)%m front但这个“牺牲一个单元”的含义跟方案一不同——方案一满的时候存m-1个方案二这个约定下满的时候存m-1个判断条件形式一样只是初始和入队操作不同。那我之前说“(rear2)”是推错了。我要修正这个部分。让我具体推一遍方案二front指向队头前一个位置rear指向队尾元素牺牲一个单元状态队空 front rear入队rear (rear1)%m; data[rear] x;出队front (front1)%m; x data[front];元素个数count (rear - front m) % m验证m5, front0, rear0, 空。 入arear1, data[1]a, front0。count(1-05)%51 ✓ 入brear2, data[2]b。count2 ✓ 出队front1, 取data[1]a。count(2-15)%51 ✓ 入c,d,erear3,4,0连续存储入c rear3, 入d rear4, 入e rear0。此时front1, rear0, count(0-15)%54 ✓ 队满判断(rear1)%5 1 front ✓ 满。但注意此时实际上存了4个元素b,c,d,e0号data存的是e。按牺牲一个单元的逻辑容量5存4个刚好。所以方案二在牺牲一个单元的前提下公式形式和方案一是完全一样的。我之前推加入“1”是错的应该是保持(rear - front m) % m。也就是说队首队尾指针指向类题目中只要“front指向队头前一个位置、rear指向队尾元素”这个组合被采用并且牺牲一个单元那么核心公式和方案一完全一致。区别只在入队出队的先后顺序上方案一入队先写再移rear、出队先取再移front方案二入队先移rear再写、出队先移front再取。这样实际上更简单。我需要把这个推导过程在文中讲清楚。刚才在思考中发现的内容修正很有价值这种“推着推着发现公式其实一样”的经验正好可以写成博文中的“容易踩坑的地方”。好我在第2章或第3章以这个为素材写。那方案三里提到的“front指向队头元素rear指向队尾元素”呢如果牺牲一个单元判断公式又是怎样的这个组合下初始front0, rear0队空。入队时data[rear] x; rear (rear1)%m; ← 参考循环队列经典实现有一些教材就是这样入队直接写rear所指位置然后rear后移。出队时x data[front]; front (front1)%m;这样其实rear“指向队尾元素”就不太对因为rear在入队后被移到了一个空位置除非说入队前rear指向的是队尾元素的下一个位置。哦所以说“rear指向队尾元素”且入队先写的话写完后rear应该不再移动但为了管理空位通常写成data[rear]x后rear保持不变下一次入队则到下一个位置所以rear又该移动了。这样rear最终在哪取决于具体实现。这就是为什么“front指向队头元素、rear指向队尾元素”配合牺牲单元的方式实际很少单独在顺序循环队列中用因为不好统一。这也是有些教材虽然按“方案三”描述指针但代码里实际上把rear当作“队尾元素的下一个位置”在用。做真题时遇到这种情况要仔细看初始化和操作的描述别看到“rear指向队尾元素”就直接套某个公式。我在文中要提醒这些不同方案本质上都是给“空/满判断”留口子真正的核心是指针移动顺序。只要画图一切都很清晰。现在我需要在正式写正文前把几个容易出错的公式完全理清结论方案一front指向队头元素rear指向队尾元素下一个位置牺牲单元法入队data[rear] x; rear (rear1)%MAX出队x data[front]; front (front1)%MAX队空front rear队满(rear1)%MAX front元素个数(rear-frontMAX)%MAX方案二front指向队头元素前一个位置rear指向队尾元素牺牲单元法入队rear (rear1)%MAX; data[rear] x出队front (front1)%MAX; x data[front]队空front rear队满(rear1)%MAX front元素个数(rear-frontMAX)%MAX跟方案一公式完全一致操作顺序相反。方案三front指向队头元素rear指向队尾元素牺牲单元法这个组合下经典写法有两种取决于入队时怎么移动指针。如果入队data[rear]x; rear(rear1)%MAX那rear实际上是“队尾元素下一个位置”归到方案一如果入队先移rear再写data[rear]x那归到方案二。所以看到“rear指向队尾”要小心。如果真按front指向队头元素、rear指向队尾元素且不额外移动那么需要tag或count才能判断空满牺牲单元法无法自洽。元素个数公式在两种可行方案下都一样这其实是个很好记的结论。好那我第3章的变式题就可以写成题干说“某循环队列的front指向队头元素rear指向队尾元素”然后问判断队空队满及元素个数——先分析它本质上属于哪种可行约定还是需要用标志位。这样既严谨又有内容。不过对于初学者可能看到这里有点晕。写作时我会把“先画图、再确认约定”作为核心方法论贯穿始终。接下来第4章链式队列链式队列主要是带头结点和不带头结点两种。带头结点链式队列typedef struct LinkNode { int data; struct LinkNode *next; } LinkNode; typedef struct { LinkNode *front, *rear; } LinkQueue;初始化front rear (LinkNode*)malloc(sizeof(LinkNode)); front-next NULL; 队空front rear都指向头结点 入队将新结点s链到rear后面rear s 出队删除front后面的结点p如果p是最后一个结点p rear则删除后rear front这里注意出队时如果删的是最后一个元素rear必须更新为front否则rear变成野指针。这个在选择题中常作为判断点。而且“front-next NULL”也可以判断队空不过更直接的是front rear。不带头结点链式队列 初始化front rear NULL 队空front NULL也等价于rear NULL 入队若队空则 front rear s否则 rear-next s; rear s; 出队x front-data; front front-next;若删除后front NULL需要令rear NULL不带头结点的链式队列第一个元素入队时front和rear都要指向它这是很多初学者容易漏掉的处理。链式队列一般不涉及“假溢出”存储空间动态分配只要内存够就能入队所以front和rear通常用NULL来判断空。第5章题目速查我要设计几道具体题目例1容量为8初始front rear 0方案一。依次入队a,b,c,d出队a入队e,f出队b入队g求front和rear。 解入队4次rear4出队1次front1入队2次rear6出队1次front2入队1次rear7。所以front2, rear7, 队列中元素是c,d,e,f,g共5个。验证公式(7-28)%85 ✓例2同容量8历经若干操作后front5, rear2求元素个数及还能入队几个元素。 元素个数(2-58)%85。还能入队几个取决于是否牺牲一个单元。若牺牲一个队满条件是(rear1)%8front即(21)%83front5不相等最多存7个当前5个还能入队2个。但如果用计数器法容量8当前5个还能入队3个。这个差别很重要也可以作为对比。例3链式队列题目 带头结点链式队列 front和rear初始都指向头结点。入队x1入队x2出队x1此时front-next指向x2rear指向x2判断队空答案是front rear不front是头结点rear是x2不相等不为空。再出队x2此时需要执行pfront-nextp是x2front-next p-nextNULL因为p rear所以rear front。此后front rear队空。不带头结点frontrearNULL为空入x1后frontrearx1结点入x2后rear指向x2front仍指向x1出x1后front指向x2出x2后frontNULL必须把rear也置为NULL否则rear仍指向已释放结点。这是一个经典易错点。例4综合指针推算 已知循环队列容量m10front3rear7方案一问元素个数(7-310)%104队是否可再入队牺牲一个单元方案(71)%108front3不相等可以。还可以入队几个最多存9个现有4个最多还能入队5个。验证rear从7到9连续入队能入3个到rear0此时rear0(01)%101front3不相等再入1个rear1(11)%102front3不等再入1个rear2(21)%103front此时满。共入队5个。✓ 这个通过“追击”算也可以队满前空位有(front - rear - 1 m) % m个m10时(3-7-110)%105 ✓好第5章内容很丰富。第6章扩展阻塞队列Java ArrayBlockingQueue 的putIndex/takeIndex就是front/rear的工程版takeIndex取元素就是队头指针putIndex放元素就是队尾指针capacity-1个元素时队满其实就是牺牲一个单元或者用count变量。ArrayBlockingQueue用的是count跟计数器法一模一样。LinkedBlockingQueue头结点是一个哨兵节点跟带头结点链式队列一样入队加在尾部出队从头部剔除。消息队列consumer的offset类似队头指针生产者写入的位置类似队尾指针。消息队列重复消费问题与“消费位点未更新”相关就是offset没有正确推进。想想kafka术语中消费者的position就是队头指针。FreeRTOS队列xQueueSend往队尾写xQueueReceive从队头读内部用uxItemSize、uxMessagesWaiting等字段指针管理思路与循环队列异曲同工。以及提到的stm32cubemx空闲中断串口接收队列也可以稍微提一句本质就是用环形缓冲区管理串口数据队头出队处理队尾入队存储。线程池的阻塞队列选择ArrayBlockingQueue有界、LinkedBlockingQueue可选有界、SynchronousQueue不存储直接传递。Taylor任务队列的peek/take与队头指针关系。第6章只要点到为止不要脱离主题重点是“同一套指针思想”。我还要注意热搜词里有一些“消息队列重复消费问题”、“duke队列”、“bqueues查看队列权限”、“队列换道轨迹规划”等这些并不完全适配“队头指针队尾指针指向类题目”这个主题。不过结构上可以自然衔接到工程场景比如消息队列重复消费问题可以简单提一下消费指针管理不当会导致问题但要控制篇幅不喧宾夺主。现在开始写正文。确保开头 ≥ 200字前100字内融入“队列”“队头指针”“队尾指针”主体 ≥ 5000字至少4个H2我计划6个每个H2下至少2个H3所有H2/H3必须有编号每段至少150字不用emoji不用mermaid不用AI套话最后不做总结式结尾。我直接以个人经验式收尾。好开始输出。 前前后后也带过不少考研和面试的学生每次讲到队列第一个绕不开的点就是“队头指针和队尾指针到底指向谁”。说实话这问题不怪大家发懵因为不同教材、不同题目里的front和rear定义真的不一样。同一个容量为10的循环队列有的题里rear指向队尾元素有的题里rear指向队尾元素的下一个空位理论上来讲这题就完全变成了两道题。我自己当年也是被这种“约定不一致”坑过好几次后来刷题总结出一套方法拿到题目先看front和rear的指向约定再决定套哪套公式几乎不会再错。这篇文章就是想把这套方法完整地交给你。我会把最常见的几种指针约定、对应的入队出队操作顺序、队空队满判断方式、元素个数计算技巧以及链式队列里front和rear的特殊处理全部过一遍最后用具体例题带你再走一遍推算过程。不管你是考研党刷数据结构还是准备面试手撕算法又或者工作中突然需要自己实现一个环形缓冲这套东西都用得上。1. 先搞懂队头指针和队尾指针到底指向谁1.1 为什么指针指向是队列题的“题眼”队列的逻辑很简单——先进先出但“队头”和“队尾”落到代码层面是有歧义的。rear叫队尾指针但有的实现里它指向最后一个元素有的实现里它指向最后一个元素后面的空位front叫队头指针但有的实现里它指向第一个元素有的实现里它指向第一个元素前面的那个“废弃位”。这个差异直接影响三件事初始化时front和rear的值、入队和出队时指针的移动顺序、队空队满的判断条件。题目如果不说清楚front和rear的指向你甚至没法确定答案是哪个选项。很多同学做题出错不是不会算而是拿着A方案的公式去做B方案的题那必然对不上。我自己的经验是面对这类题第一步永远是画图。拿一支笔画出队列的格子标上front和rear指向的位置然后按照题目给的操作序列一步一步推。画完一张图题目的答案基本就出来了。这个习惯我到现在还在用工作中排查环形缓冲区问题也是这么干的。1.2 三种最常用的指针约定方案把市面常见教材和历年真题刷过一遍后我归纳出三种最常用的front和rear约定。方案一front指向队头元素rear指向队尾元素的下一个位置。这是考研大纲和大多数数据结构教材默认的方式。初始化时front rear 0。入队时先把数据写入rear指向的位置再将rear加1出队时先取出front指向的数据再将front加1。队空的判断条件是front rear。牺牲一个存储单元时队满条件是(rear 1) % MAXSIZE front。元素个数是(rear - front MAXSIZE) % MAXSIZE。方案二front指向队头元素的前一个位置rear指向队尾元素。这种方案下front指向的位置实际上是一个“前哨位”不存有效数据。初始化时front rear 0这里的0可以理解为头结点或队头元素的前一个下标。入队时先将rear加1再把数据写入新位置出队时先将front加1再从新位置取出数据。需要通过牺牲一个存储单元来区分空满时判断公式和方案一完全一致但操作顺序正好反过来。方案三front指向队头元素rear指向队尾元素。两个指针都指向实际元素。这种方案最大的问题是队空和队满时front和rear的相对位置关系很难用统一公式区分往往要配合计数器或标志位来使用。有些题目描述中用这种约定但给出的操作序列实际上用的是方案一或方案二做题时一定要留个心眼。我把三种方案的核心差异整理成了一张表方便对比方案front指向rear指向入队顺序出队顺序空满区分一队头元素队尾元素的下一个空位先写data[rear]再rear1先取data[front]再front1可牺牲单元或计数器二队头元素的前一个位置队尾元素先rear1再写data[rear]先front1再取data[front]可牺牲单元或计数器三队头元素队尾元素视实现而定视实现而定必须计数器/标志位1.3 操作顺序怎么记才不会混不同方案下入队出队的先后顺序很容易搞混。我提供一个自己的记忆方法看rear当前指向的位置是不是“能直接写的位置”。方案一中rear指向空位所以一进来就可以写数据方案二中rear指向最后一个有效数据必须先移动指针腾出一个空位再写。front的处理也类似方案一中front指向有效数据所以先取数据再移走方案二中front指向无效位置所以先移到有效位置再取数据。理解了这个逻辑就不用死记“先移动还是后移动”了。做题时只要在草稿纸上标一下“当前这个指针指向的位置有没有有效数据”序就写不错。我还见过一些人把这个总结成口诀“rear空则先写rear实则先动front实则先取front虚则先动”你也可以参考但最靠谱的还是画图。2. 顺序队列与循环队列指针指向的陷阱2.1 非循环顺序队列为什么会出现“假溢出”顺序队列用一段连续数组存元素front和rear都在数组下标范围内移动。每次入队rear后移每次出队front后移。随着操作次数增多rear会一路移向数组末尾到末尾时就无法再入队了——哪怕数组前头空着一大片位置。这就是“假溢出”。队列逻辑上没满物理存储却满了。解决假溢出的主流方案就是把数组“首尾相接”成循环队列让rear走到MAXSIZE - 1后下一步回到0。这样一来tail的移动从单纯的“加1”变成了“加1再对MAXSIZE取模”。循环队列虽然解决了假溢出的问题但也把队头队尾指针的指向问题变得更加隐蔽。因为指针一旦可以绕圈front和rear谁大谁小就不再能直观反映队列里有多少元素了。很多题目专门考这一点。2.2 循环队列指针移动的取模运算循环队列的所有指针移动都遵循这个公式front (front 1) % MAXSIZE; rear (rear 1) % MAXSIZE;做题的时候连续入队出队多次不需要逐步模拟。直接看front总共被加了几次、rear总共被加了几次然后用总数对MAXSIZE取模就行。这里要注意入队只会让rear向前推进出队只会让front向前推进。不要把“入队n次出队m次后”直接算成rear移动n次、front移动m次这个方向别搞反。队列容量为m时指针每移动m次回到原位置所以取模后的结果只和移动总次数有关。举个例子容量为10初始front 0连续出队7次又出队3次后front (0 10) % 10 0。这个式子跟“先7后3”还是“一起10次”无关最终取模看的是总次数。2.3 元素个数公式到底是哪来的在方案一的约定下队列元素个数的标准公式是count (rear - front MAXSIZE) % MAXSIZE很多同学只是背下来没有想过它为什么成立。我来讲一下。当rear大于front时元素个数就是rear - front很直观。当rear小于front时说明rear绕了一圈跑到了front后面此时实际个数是(MAXSIZE - front) rear也就是rear - front MAXSIZE。把这两种情况统一起来就是对MAXSIZE取模。我提供一个心算技巧把数组从front位置剪开拉成一条直线。如果rear在front右边直接减如果rear在front左边就用MAXSIZE减去两者之间的距离。多练几次这种题就是秒算。顺带提醒一个很容易犯的错有人会把公式写成(rear - front) % MAXSIZE少了加MAXSIZE这一步。当rear小于front时这个式子算出来是个负数结果完全错误。所以加MAXSIZE不能省它本质上是把“借一位”这件事显式写了出来。3. 队空队满判断核心题型的分类破解3.1 牺牲一个存储单元法最经典的判空判满方案一下如果不做任何附加处理front rear既可能是队空也可能是队满。为什么会这样因为队列空和队列满时front和rear的相对位置完全相同。为了区分最直接的办法就是人为少存一个元素——把数组容量为m的队列最多只存m - 1个元素留一个空位做标志。队空时front rear队满时(rear 1) % MAXSIZE front。为什么队满条件是“加1等于front”因为队满时rear指向最后一个有效元素的下一个位置而front指向队头元素两者之间恰好空着一个格子。当rear再往前移动一个位置就会碰到front此时说明“如果我继续入队队列就真的满了”。这个判断本身并不是禁止你入队而是告诉你“在这个约定下如果现在入队空满就无法区分了”。这个方案下还有一个衍生考点队列还能容纳多少个元素空位数公式是(front - rear - 1 MAXSIZE) % MAXSIZE。这个我不建议死记画图画多了自然就推出来了。3.2 计数器法用额外变量绕开指针歧义计数器法不牺牲存储空间而是在结构体里加一个count字段。入队成功count加1出队成功count减1。队空条件count 0队满条件count MAXSIZE。数组里的m个格子可以全部用来存数据。这种方案做题时的坑在于题目如果只给front和rear的数值问“队列是空还是满”在计数器法下光靠这两个指针是判断不了的。此时正确答案是“无法确定”除非题干里给出了count的信息。我印象中有些选择题特别喜欢这么挖坑把两种方案混在一道题里先用计数器法描述队列结构问队满条件时又有人下意识写(rear 1) % MAXSIZE front结果错了。做题时看清楚题干里有没有count或者tag字段有的话优先用它们判断。3.3 标志位法用最后一次动作区分空满标志位法同样是为了让m个格子都能存数据。维护一个tag变量初始为0。入队成功后令tag 1出队成功后令tag 0。判断时如果front rear就看tagtag 0说明最后一次操作是出队这个相等是由出队导致的队列为空。tag 1说明最后一次操作是入队这个相等是由入队导致的队列为满。这个方法的核心逻辑是无论入队还是出队操作成功之后指针都有可能相等但这个相等的“原因”不同。之所以能区分是因为队列由空变满的过程中指针相等只能发生在入队之后由满变空的过程中指针相等只能发生在出队之后。与计数器法对比计数器法统计的是“当前到底存了几个”标志位法记录的是“最后一次动作是入还是出”。前者能算出精确数量后者只能判断空满状态但算不出数量。两个方法常被考到区别答题时不要混。3.4 变式题rear指向队尾元素时该怎么算现在我把前面讲的内容综合到一道变式题里。题目描述循环队列容量为mfront指向队头元素的前一个位置rear指向队尾元素初始front rear 0问队空、队满条件和元素个数公式。这道题看着和方案二很像实际确实是方案二的直接应用。入队时由于rear指向的是最后一个有效元素必须先移动rear再写也就是rear (rear 1) % m; data[rear] x;出队时由于front指向的是没有有效数据的前哨位置必须先移动front再取front (front 1) % m; x data[front];请你特别注意这种情况下队空条件和队满公式与方案一完全一致。队空front rear队满条件依然是(rear 1) % m front元素个数依然是(rear - front m) % m。很多同学一看到“rear指向队尾元素”就慌觉得公式肯定要变实际推一遍就会发现并没有变。为什么没变因为front和rear的相对定义虽然和方案一不同但它们的“差值”所包含的元素个数关系保持一致。front前哨位不计数rear本身计数差值恰好等于队列元素个数。这就是我前面强调的推导公式时别靠感觉画图验证最重要。我当时也是推了一遍才彻底放下心来。4. 链式队列的队头队尾指针4.1 带头结点和不带头结点的差异链式队列分为带头结点和不带头结点两种。这两种情况下front和rear的语义差别很大也是链式队列最容易出考点的地方。带头结点的链式队列头结点是一个dummy结点不存有效数据。front始终指向这个头结点rear指向最后一个有效结点。初始化时front rear 头结点地址。判断队空的条件是front rear此时队列里没有任何有效结点。不带头结点的链式队列front直接指向第一个有效结点rear指向最后一个有效结点。初始化时front rear NULL。判断队空的条件是front NULL等价于rear NULL。有一个细节很多人忽略带头结点的链式队列中即便队列里只有一个元素入队时也只需要修改rearfront一直指向头结点不动而不带头结点的队列插入第一个元素时必须同时让front和rear都指向这个新结点因为队列从空变成非空队头也变了。4.2 链式队列入队出队的指针操作细节先看不带头结点的链式队列入队LinkNode *s (LinkNode*)malloc(sizeof(LinkNode)); s-data x; s-next NULL; if (rear NULL) { front rear s; } else { rear-next s; rear s; }注意第一个结点特殊处理如果忘记判断rear NULL直接执行rear-next s就会对空指针解引用程序直接崩溃。再看不带头结点的链式队列出队LinkNode *p front; x p-data; front front-next; free(p); if (front NULL) { rear NULL; }出队后如果队列变成空必须让rear也变成NULL。因为rear之前还指向被删除的那个结点如果不更新后续入队判断rear NULL就失效了。这个点特别容易考到也是实际写代码时经常踩的坑。带头结点的链式队列出队略有不同因为有一个头结点垫底front不会变成NULL所以不需要像不带头结点那样处理空队列。但删除最后一个有效结点时需要重置rear为front否则rear就变成了悬空指针。4.3 链式队列为什么不需要“队满”判断链式队列的空间是动态分配的理论上只要内存足够就能一直入队。所以它天然不存在顺序队列的“假溢出”问题。链式队列一般只需要判断队空不需要判断队满。这是一个和顺序队列很大的区别做题时经常作为判断项出现。如果你在题目里看到“链式队列采用牺牲一个存储单元的方法判断队满”那大概率是错误选项。链式队列的容量根本不由数组限制队列能存多少取决于堆内存。这一点在面试中也经常被问到比如“普通队列和循环队列的区别”或者“链式队列和顺序队列各自适合什么场景”。5. 实战刷题队头队尾指针指向类题目速查5.1 题型一给定操作序列推算front和rear的最终指向这类题核心就是确认方案分清哪些操作影响front、哪些影响rear然后用取模汇总次数。我用一道完整例题演示。循环队列容量MAXSIZE 8采用方案一front指向队头元素rear指向队尾元素的下一个位置初始front rear 0。依次执行入队a、b、c、d出队a入队e、f出队b入队g推算过程入队a、b、c、d共入队4次rear (0 4) % 8 4front不变仍为0。出队a共出队1次front (0 1) % 8 1rear不变仍为4。入队e、f共入队2次rear (4 2) % 8 6front仍为1。出队b共出队1次front (1 1) % 8 2rear仍为6。入队g共入队1次rear (6 1) % 8 7front仍为2。最终front 2rear 7。队列里实际元素是c、d、e、f、g一共5个。用公式验证(7 - 2 8) % 8 5完全一致。这道题如果按“逐步移动”的方式去模拟容易绕晕但把入队次数和出队次数分开统计就非常清爽。做题时可以在草稿纸上写两行“front被加x次rear被加y次”然后对容量取模。5.2 题型二给定front和rear反推元素个数和剩余容量另一类常见题是已知操作后的指针位置反推队列状态。比如容量maxsize 10front 3rear 7方案一问队列元素个数、能否继续入队、还能入队几个元素。元素个数(7 - 3 10) % 10 4。牺牲一个存储单元时最多存9个当前4个所以还能入队5个。验证方式从rear 7出发入队3个后rear 0此时(0 1) % 10 1front 3不相等仍可入队继续入队到rear 2时(2 1) % 10 3与front相等队满。总共在原来基础上又入队了5个。这类题还有另一种考法计数器和标志位方案下同样给出front和rear让你判断空满答案是“无法仅凭指针确定”。一定要看题目有没有额外信息。5.3 题型三链式队列的指针状态判断用一道经典真题变式练手。带头结点的链式队列初始front rear 头结点。依次入队x1、x2再出队x1。问当前front和rear的指向以及队列是否为空。入队x1rear-next x1结点rear指向x1。此时front仍指向头结点rear指向x1两者不相等。 入队x2rear-next x2结点rear指向x2。front仍指向头结点。 出队x1p front-nextp是x1结点front-next p-next此时front-next变成了x2free(p)。因为p不是rear所以rear保持指向x2。 最终front指向头结点头结点的next指向x2rear指向x2。队列不为空因为front ! rear。如果把x2也出队p front-nextp是x2front-next p-next为NULL因为p rear所以必须执行rear front。此时front rear队列为空。这一步就是前面说的“删除最后一个有效结点要复位rear”务必记住。5.4 易错点自查清单我把刷题过程中反复遇到的易错点整理成一个清单你在做题前快速过一遍拿到题先确认front和rear的指向约定不能凭印象默认全教材一致。“rear指向队尾元素”不一定改变元素个数公式要看front指向哪里以及操作顺序怎么定义。入队出队的“先移动、后写入”或者“先读取、后移动”每一步都对应指针当前指向有没有有效数据。链式队列带头结点和不带头结点的队空条件不同两个都要记住。链式队列删除最后一个结点时带头结点要重置rear front不带头结点要重置rear NULL。计数器法和标志位法下不能仅凭front和rear判断队空队满。容量为m、牺牲一个存储单元时最多存储m - 1个元素这个“1”的空位是空满判断的关键。6. 从教科书指针到工程队列同一套思想6.1 阻塞队列里的队头队尾指针如果你用过Java的ArrayBlockingQueue会发现它的内部结构特别眼熟takeIndex对应队头指针putIndex对应队尾指针count计数当前元素数量。这正是教科书里“front指针 rear指针 count计数器”组合的工程实现。LinkedBlockingQueue则更像带头结点的链式队列内部有一个哨兵头结点出队时从头结点后取第一个节点入队时往链表尾部追加。生产者和消费者通过lock和condition协调但底层指针管理思路和我们在第4部分讲的链式队列一模一样。理解了这个关联再看线程池的阻塞队列选择题目就非常清晰了。有界队列用ArrayBlockingQueue是因为需要容量限制避免任务无限堆积无界队列用LinkedBlockingQueue是因为允许任务持续排队。题面换个包装问的还是“队满时怎么办、队空时怎么办”这些老问题。6.2 消息队列的消费位点管理消息队列里也有类似队头指针的概念比如消费者维护的消费位点offset。读消息相当于“从队头取数据”读完提交位点相当于“更新队头指针”。生产端写入的位置则对应队尾指针。“消息队列重复消费问题”为什么会发生本质就是消费位点没有被正确提交队头指针停留在旧位置下次还要再读一次同一批消息。这个问题的解决思路也很像循环队列的约定问题厘清“当前位点指向已经消费的消息还是指向下一条待消费的消息”把约定统一好重复和丢失就能规避。6.3 嵌入式队列和串口缓冲再看嵌入式场景FreeRTOS的消息队列、串口空闲中断接收数据时常用的环形缓冲区本质上都是同一套东西。环形缓冲区的读指针就是队头指针写指针就是队尾指针判空判满条件跟前面公式如出一辙。用STM32CubeMX配置空闲中断加串口接收时很多人把接收缓冲写成环形队列接收中断往队尾写数据主循环从队头读数据。只要队头队尾指针的移动和判断写对了整个收发流程就非常稳。反过来如果指针判断出错就会出现数据覆盖或者漏读这和做数据结构题的“空满判断错误”是一样的后果。我个人在实际使用中最大的体会是队列这种东西如果只停留在做题层面很多细节记了又忘但一旦把它跟工程里的具体场景对照起来比如哪天你自己写一个环形缓冲区再回头看那些front、rear的公式就会觉得理所当然。所以建议你把第3部分的推演过程亲手在草稿纸上画一遍再用第5部分的例题验证一次之后不管题目怎么变都不太容易再被“指向谁”这个问题绊住了。
