队头指针、队尾指针类题目说句实话是数据结构笔试、考研和面试里最容易被秒杀也最容易被秒杀反杀的题型。说它简单是因为队列的框架就那么点东西说它阴险是因为不同教材、不同题目对 front 和 rear 的指向定义完全可能不一样——你在这一题里 rear 指向队尾元素换一题里 rear 指向队尾元素的下一个位置公式没变结果全变。很多同学来问我这类题不是不会队列入队出队而是被“指向定义”和“判空判满方式”绕晕了。这篇文章就把我这些年刷题、讲题过程中积累的队头指针队尾指针类题目做一个完整总结从最基础的指向概念到循环队列三种判空判满方案再到链式队列的指针操作和典型例题最后延伸到实际工程里消息队列、阻塞队列的同类思想。内容是一路从易到难排的建议按顺序读。1. 先搞清楚front 和 rear 到底指向谁1.1 队列的两种基本存储结构队列的逻辑结构是先进先出FIFO这个大家都熟悉。但物理上用顺序表实现还是用链表实现直接决定了 front 和 rear 指针的含义和移动方式。用顺序存储的时候队列用一个一维数组和两个整型变量来维护。数组存放元素front 指向队头rear 指向队尾入队时 rear 移动出队时 front 移动。这里最容易出问题的是出队时 front 向后移动后数组前面的空间就空出来了但 rear 只能往后走走到数组末尾时即使数组前面还有大量空闲也插不进新元素了。这就是经典的“假溢出”。顺序队列做不做成循环结构是这类题目的第一个分岔口。用链式存储的时候队列就是一条单链表front 指针指向第一个元素节点rear 指向最后一个元素节点。入队就是尾插出队就是头删。链式队列没有假溢出的问题但因为多了一个指针的维护细节题反而更多比如“不带头结点的链队出队时要注意什么”“front 和 rear 都为空时空不空”等等。1.2 指向定义的差异一切公式的地基做题之前必须先做一件事看题目里 front 和 rear 的初始化定义。我梳理了一下常见定义无非这四种front 指向队头元素rear 指向队尾元素的下一个位置教材经典款front 指向队头元素rear 指向队尾元素另一种经典款front 指向队头元素的前一个位置rear 指向队尾元素考研部分教材款front 和 rear 初始化为和数组下标有关的偏移量比如 -1 或 0配合特定操作逻辑定义不同入队出队时指针的移动方式完全不同计算元素个数的公式也不同。很多同学死记“队空条件是 front rear”结果遇到“front 指向队头元素的前一个位置”的定义就翻车因为那种定义下队空可能是 front rear队满也可能是 front (rear 1) % maxsize但元素个数公式却变成了 (rear - front maxsize) % maxsize。我给个实操建议拿到任何一道队列题目第一件事不是看题目问什么而是先判断 front 和 rear 的指向定义。如果是选择题题目里通常会写如果是简答题你需要在答案开头就说明自己采用的约定。这样至少能挽回一半分数。1.3 队空和队满判断的本质逻辑不管哪种存储结构、哪种指针定义判空判满的本质都是用指针之间的关系来表达“队列里还能不能放元素”和“队列里还有没有元素”这两个状态。顺序队列里最朴素的做法是 front rear 表示队空rear maxsize 表示队满假溢出。这种结构实现简单但浪费前面空出来的空间所以实际考试和工程里基本都是循环队列。循环队列里队空是 front rear队满则要看方案。为什么不能也让队满等于 front rear因为那样的话“队空”和“队满”就完全分不清了同一个条件两套意义。除非额外引入计数器或标志位否则单靠两个指针的值无法区分这两种状态。“区分不了就牺牲一个存储单元用来做约定”这就是牺牲一格方案的核心逻辑。后面两章会逐个展开。2. 循环队列的三套主流方案循环队列本质上就是用取模运算把数组的头尾接起来让 rear 到达数组末尾后能通过 (rear 1) % maxsize 回到数组开头。这样一来假溢出问题被解决代价是判空判满的条件需要重新设计。目前最主流的方案有三套我把它们的判断逻辑、元素个数公式、适用场景都拆开讲。2.1 牺牲一个存储单元方案考研/笔试最常用约定 rear 指向队尾元素的下一个位置front 指向队头元素。队列初始化时 front rear 0。入队时执行if ( (rear 1) % maxsize front ) // 队满 else { arr[rear] x; rear (rear 1) % maxsize; }出队时if ( front rear ) // 队空 else { x arr[front]; front (front 1) % maxsize; }队满条件是 (rear 1) % maxsize front。因为 rear 指向的地方不能再存元素必须预留一个空位来区分队满和队空所以该方案下队列最多能存 maxsize - 1 个元素。元素个数公式是 (rear - front maxsize) % maxsize。我解释一下为什么这里要加 maxsize 再取模。循环队列里 rear 可能已经越过数组末尾回到前面比如 front 5rear 2物理上 rear front直接相减是负数。加一个 maxsize 让差值为正再取模得到真实元素个数。这个公式是整个循环队列题目的核心工具务必做到看到 front 和 rear 就能写出来。2.2 增设 size 计数方案牺牲一个存储单元总觉得有点浪费尤其是数组大小刚好等于需求上限时。更优雅的方案是给队列结构体加一个 size 字段专门记录当前元素个数。结构体定义类似typedef struct { int data[maxsize]; int front; // 队头下标 int rear; // 队尾下标指向队尾元素的下一个位置也可以指向队尾元素只要操作统一 int size; // 当前元素个数 } sqQueue;初始化时 front rear 0size 0。入队时先判断 size maxsize 就队满否则 data[rear] xrear (rear 1) % maxsizesize。出队时先判断 size 0 就队空否则 x data[front]front (front 1) % maxsizesize--。这套方案最大的优点不需要牺牲存储单元队列可以存满 maxsize 个元素。判空 condition size 0判满 condition size maxsize直观且不会混淆。代价就是多维护一个变量出队入队时都要同步更新 size。2.3 增设 tag 标志位方案还有一个思路是加 tag 标志位。核心逻辑是虽然 front rear 这个条件既能表示队空也能表示队满但我们可以用 tag 来记录最后一次操作是入队还是出队。如果最后一次操作是入队导致 front rear那必然是队满如果是出队导致的 front rear那必然是队空。具体实现typedef struct { int data[maxsize]; int front; int rear; int tag; // 0 表示最近一次是出队1 表示最近一次是入队 } sqQueue;入队if ( front rear tag 1 ) // 队满 else { data[rear] x; rear (rear 1) % maxsize; tag 1; }出队if ( front rear tag 0 ) // 队空 else { x data[front]; front (front 1) % maxsize; tag 0; }这套方案的判断条件比牺牲一格方案稍微绕一点但比 size 方案省一个整型字段。说实话tag 方案在考研真题里出现的频率不如牺牲一格方案但在面试题里偶尔会看到因为它考察的是对“状态区分”本质的理解。如果你能把三套方案的原理都吃透这类题目基本逃不出你手心。2.4 不同方案下判空判满和元素个数总结我把三种方案的核心要点整理成了一张表做题时直接对标方案初始化队空条件队满条件元素个数最多能存元素数牺牲一格frontrear0front rear(rear1)%maxsize front(rear-frontmaxsize)%maxsizemaxsize-1增设sizefrontrear0, size0size 0size maxsizesizemaxsize增设tagfrontrear0, tag0frontrear tag0frontrear tag1(rear-frontmaxsize)%maxsizemaxsize注意这张表默认的是“front 指向队头元素rear 指向队尾元素的下一个位置”。如果题目改成了别的指向定义判断条件和元素个数公式要跟着调整。我在第 4 章会专门讲这种变式题。3. 链式队列的 front 和 rear 操作顺序队列讲完链式队列也不能看轻。链队从逻辑上说是单链表front 是头指针rear 是尾指针。区别只在“带头结点”还是“不带头结点”这两个版本的操作细节和边界处理不一样。3.1 带头结点的链队带头结点意味着有一个哨兵节点front 始终指向这个头结点不存储真实数据。初始化时front (LinkNode*)malloc(sizeof(LinkNode)); rear front; rear-next NULL;此时 front rear队空。入队时创建新节点 p让 rear-next prear p。出队时由于第一个数据节点是 front-next如果 front-next NULL说明队列空否则保存 front-next 的节点front-next 那个节点的 next如果删的是最后一个节点还要把 rear 指回 front否则 rear 会指向一个已经释放的内存。带头结点版本的好处是出队操作统一不需要判断“删掉的是不是最后一个节点”时额外处理 rear 指向 NULL 的情况——不其实还是需要的。因为删除最后一个节点后rear 仍然指向被删除节点必须把 rear 拉回 front。这个细节特别适合出选择题入队、出队后 rear 和 front 分别指向哪里。3.2 不带头结点的链队不带头结点的链队front 直接指向第一个数据节点rear 指向最后一个数据节点。初始化时 front rear NULL。队空条件就是 front NULL rear NULL或者 front NULL因为 front 为 NULL 时 rear 也一定为 NULL反过来不成立吗实际上如果队列非空 front 肯定不空如果队空两者都该是 NULL。入队时如果原来队空要让 front 和 rear 都指向新节点否则在尾部执行 rear-next newnode; rear newnode。出队时用临时指针保存当前 front 节点front front-next如果 front 变成 NULL说明队列已经空了此时还要把 rear NULL。这一步是新手最容易漏的。我在实际教学中发现不带头结点版本最容易出的错就是删除最后一个节点后rear 还指向那个已经被释放的节点导致后续入队时往野指针后面挂节点轻则数据错乱重则直接段错误。排查链队问题第一步永远都是检查 rear 是否兜底复位。3.3 链队出队入队的细节和边界题链队虽然不是本篇文章题目的绝对主角但“队头指针、队尾指针指向类题目”在链队里有一个非常经典的考法给出一个链式队列的初始状态几个节点front 指向哪rear 指向哪连续执行若干次入队操作再连续执行若干次出队操作问最终 front 和 rear 指向哪里队列里有哪些元素这种题本质就是模拟链表的尾插和头删。我给大家一个做题标准流程画出链表图把每个节点标上编号a1、a2、a3……用箭头画出 front 和 rear 当前指向的位置每做一次入队操作在链表尾部增加一个节点移动 rear每做一次出队操作删除头部节点移动 front特别注意出队导致队列空时rear 也要变成 NULL不带头结点场景按这个流程走链队题基本不可能错。另外注意链队不像循环队列有判满的概念理论上只要内存够就能一直入队所以链队题目一般只考“空不空”和“指针指向哪里”不考“满不满”。4. 实战题解从易到难过一遍典型题目这一章我把网上和书上常见的“队头指针、队尾指针指向类题目”做了个归类每类配一两个典型题带完整推导过程。你们做题时如果卡住了回来对照这一类题型的解题套路基本能秒杀。4.1 入队出队后指针变化类题目例题 1设循环队列的数组容量为 6初始 front rear 2。依次执行入队 a、b、c、d再执行出队两次然后入队 e。使用牺牲一个存储单元方案问最终 front 和 rear 分别等于多少队列中剩余元素是什么。解牺牲一格方案下队满条件是 (rear 1) % 6 front所以这个循环队列最多能存 5 个元素。初始front 2rear 2队空入队 aarray[2] arear (2 1) % 6 3入队 barray[3] brear (3 1) % 6 4入队 carray[4] crear (4 1) % 6 5入队 darray[5] drear (5 1) % 6 0此时 front 2rear 0元素有 a、b、c、d共 4 个验证一下 (0 - 2 6) % 6 4正确出队第一次取出 array[2] afront (2 1) % 6 3出队第二次取出 array[3] bfront (3 1) % 6 4入队 earray[0] erear (0 1) % 6 1最终 front 4rear 1队列中元素是 c下标4、d下标5、e下标0共 3 个验证元素个数(1 - 4 6) % 6 3正确。这类题的核心就是两步先根据入队出队动态更新指针最后用元素个数公式校验一遍。我强烈建议每次算完都要用公式校验因为选择题一旦错一步后面全错但用公式能从整体上确认指针变化是否合理。4.2 循环队列元素个数计算类题目例题 2用牺牲一格方案实现循环队列maxsize 20当前 front 8rear 3问队列中有多少个元素代入公式(rear - front maxsize) % maxsize (3 - 8 20) % 20 15 % 20 15。这里解释一下为什么答案是 15 而不是“rear 在 front 前面所以没元素”。因为 rear 已经通过取模绕到前面了物理上它指向的位置在 front 后面的地址空间里没有元素但逻辑上队列是从 front 位置到 rear 位置沿着循环方向的所有元素也就是下标 8 到 19 的元素再加上下标 0 到 2 的元素正好 15 个。这个题几乎是循环队列必考题公式理解到位就行。如果题目改成“rear 指向队尾元素front 指向队头元素的前一个位置”那元素个数公式需要变成 (rear - front maxsize) % maxsize 吗其实还是一样的只要两个指针在循环数组上且移动方向一致这个公式就成立。真正的区别在于判空判满条件不同以及最大容纳量是否要减一。4.3 变式陷阱题rear 指向队尾元素场景例题 3一个循环队列front 指向队头元素rear 指向队尾元素初始 front rear 0 表示队空。数组容量为 10问队满条件是什么最多能存几个元素这个定义下入队和出队的移动顺序要反过来。入队时先移动 rear 再赋值不对因为 rear 指向队尾元素插入前 rear 指向最后一个元素插入后 rear 要指向新元素。初始时队列为空front rear 0此时没有队尾元素第一次插入必须特殊处理不然 front 和 rear 的指向就乱了。我推荐采用的方案是初始化 front rear 0 表示队空入队时若队空data[0] xfront 和 rear 都保持 0 不动不对rear 应该指到新插入元素的下标。更常见的做法是初始化 front 0rear maxsize - 1或者 front rear -1 表示空。如果初始化 front rear 0 又要表示空那么插入第一个元素时 data[0] xrear 不移动还是 0因为 rear 本来就指向第 0 个元素。这样第二个元素插入时先 rear (rear 1) % maxsize再 data[rear] x。这样定位后队空条件仍然是 front rear但这和初始状态 front rear 0 的来源不同一个是真正的空一个是有 1 个元素时 rear 恰好还在 0……这就引出了又一个坑如果队里只有一个元素front 指向它rear 也指向它front rear 成立但队列并不空。所以这种定义下判空条件 front rear 不成立必须另外加计数器或标志位来区分“一个元素”和“空”。这正是考研题里常埋的变式rear 指向队尾元素时单单 front rear 不能作为判空条件。有些教材为了规避这个问题就把初始化改成 front 0rear maxsize - 1插入时先移动 rear这样空状态时 front 和 rear 不相等非空时有可能相等。但判空就成了 rear (front - 1 maxsize) % maxsize。我做题时遇到 rear 指向队尾元素这种定义统一的做法是初始化 front 0rear maxsize - 1入队先 rear (rear 1) % maxsize 再赋值出队先取 front 位置的元素再 front (front 1) % maxsize。这样队空rear (front - 1 maxsize) % maxsize 不对初始化 front0rearmaxsize-1 时front 指向第一个元素rear 指向最后一个元素差值为 rear (front - 1 maxsize) % maxsize 时队列为空即 rear 在 front 的前一个位置。队满rear 再移动一步就追上 front即 (rear 1) % maxsize front。最多容纳 maxsize 个元素因为不需要牺牲一格front 和 rear 之间允许完全绕一圈填满。为了不让大家混乱我总结成一句话先用题目的文字判断 rear 是“指向队尾元素”还是“指向队尾元素的下一个位置”然后反推对应的初始化方式和判空判满条件不要背某一个固定结论就硬套。这是所有队头指针队尾指针类题目中最重要的做题习惯。4.4 栈和队列对比中的指针题栈和队列对比类题目也经常围绕“指针指向”展开。比如问若用两个栈模拟一个队列入队操作怎么做、出队操作怎么做。这种题虽然题目里没有 front 和 rear但本质上“栈底充当队尾、栈顶充当队头”的思维就是指针指向思想的另一种表达。这类题目我在面试辅导时总结的口诀是入队尽可能往入栈塞出队时先把入栈元素全部弹到出栈再从出栈弹出。核心点在于“只能从出栈弹元素”是队头“只能往入栈放元素”是队尾。每次操作后两个栈里元素的分布就对应着 front 和 rear 的动态变化经常作为链队/循环队列题目的变形出现。5. 从考研题到工程实践队列思想的延伸5.1 C STL queue 和 priority_queue 的底层实现C STL 的 queue 默认底层容器是 deque不是顺序数组也不是链表而是一个双端队列。deque 的内部结构是一段段连续空间拼接起来的start 和 finish 两个迭代器分别指向队头和队尾的边界本质上就是 front 和 rear 指针的工程化实现。priority_queue 默认是大顶堆底层是 vector。它没有传统意义上的 front、rear 指针而是通过堆的下标关系维护优先级。很多初学者把 priority_queue 误当成普通队列来理解面试如果问到“队头指针队尾指针指向”就更晕了。我的建议是遇到 priority_queue 题目先忘掉 front 和 rear转用“完全二叉树数组下标”的思维来解决它是堆结构不是队列结构只是名字叫 queue 而已。CTM 和考研真题里很少出现 priority_queue 的指针指向题但如果问到“用数组实现堆的入堆、出堆时下标如何变化”其实和队列的 front/rear 计算遵循同一种底层逻辑用下标维护一个可变范围的存储窗口。5.2 阻塞队列与线程池的线程安全队列实际工程里线程池的任务队列常常是一个有界阻塞队列比如 Java 的 ArrayBlockingQueue、LinkedBlockingQueue。ArrayBlockingQueue 底层就是循环数组putIndex 和 takeIndex 分别对应 rear 和 frontcount 对应 size。它采用的正是我上文说的“伤害加 size”方案用 count 区分队空和队满通过 ReentrantLock 和 Condition 实现阻塞唤醒。面试题经常会问“线程池的阻塞队列怎么选”这其实就是在考循环队列的指针模型。有界队列ArrayBlockingQueue适合资源受限场景无界队列LinkedBlockingQueue 默认无界适合任务量波动大的场景。下面这张表是我整理的选型对照队列类型底层结构是否可能有界队头/队尾维护方式适用场景ArrayBlockingQueue循环数组是putIndex/takeIndex 取模移动固定大小线程池防止任务堆积LinkedBlockingQueue链表可无界可有界head/last 节点指针任务波动大吞吐优先SynchronousQueue无缓存逻辑上有界不存储元素直接交接高并发、快速传递任务PriorityBlockingQueue堆可无界数组下标维护堆序任务带优先级需重排序你看ArrayBlockingQueue 的 putIndex 和 takeIndex跟循环队列里的 rear 和 front 几乎是一模一样的思路连取模操作都一致。只不过多了一个锁和两个 Condition把“队满时入队线程等待”“队空时出队线程等待”这两件事做了阻塞管理。5.3 消息队列的消费进度与重复消费问题消息队列里的“消费偏移量”其实也是一种队头指针思想。比如 Kafka 的 consumer group 里有一个 offset记录消费者当前消费到的位置这个 offset 就相当于 front 指针生产者不断追加消息到 log 末尾对应的是队尾指针不断前进。消费者手动提交 offset 还是自动提交决定了消息是“已经读了”还是“已确认”。重复消费问题在工程面试里特别高频。为什么消息会被重复消费从队列模型角度看就是消费者读取消息后本地处理完了但 offset 还没来得及更新提交此时队列认为这条消息还没被消费就重新分配给了另一个消费者于是同一份数据被处理两次。解决办法无非是“保证 offset 提交的时机和消息处理的幂等性”比如处理完业务后异步提交 offset或者业务逻辑天然幂等。这类面试题表面上叫“消息队列重复消费问题”落到数据结构底层其实仍然是队头指针消费 offset和队尾指针生产位点之间的游标管理问题。你如果能把循环队列里 front 和 rear 的“滞后追平”想明白面试答消息队列的 offset 提交机制就会比别人顺。这个跨知识点迁移是我带学生时反复强调的也是很多选手从“会做题”到“真理解”的分水岭。6. 常见错误与自查清单6.1 队头队尾指针题目的高频翻车点错误一拿到题目没确认 front 和 rear 的指向定义直接套公式。比如牺牲一格方案的元素个数公式 (rear-frontmaxsize)%maxsize在“rear 指向队尾元素”定义下也成立但判空判满条件变了很多人套错。错误二循环队列取模时忘记“环境”。front 8rear 3 时直接算 3-8 得负数然后不知道怎么办。正确处理是加上 maxsize 再取模抵消循环回绕的影响。错误三链式队列删除最后一个元素后没有把 rear 置空。无论是带头结点还是不带头结点删除最后一个节点后 rear 都会变成野指针必须重新赋值。错误四循环队列用 size 方案时size 更新和指针移动顺序搞反。入队一定是先放数据再动指针再 size出队一定是先取出数据再动指针再 size--。顺序不是唯一但必须统一否则考场上一紧张就一边定义一个样代码就废了。错误五把“队空”和“队满”混为一谈尤其是 front rear 时忘记后面还要判断 tag 或者 size。任何一个判空判满题都要从“上一次操作是入队还是出队”的角度再验证一遍这是一个很好的自查习惯。我把这些错误做成了一张速查表错误类型错误表现正确思路自查方法定义未确认直接套公式先判断 front/rear 指向定义读题后先写下指针含义再动笔取模为负直接报负数或溢出加 maxsize 再取模任何 front、rear 相减后先加 maxsize链队野指针删完最后一个节点后 rear 无用判断 front 为空时同步把 rear 置空每次出队后检查 rear 是否悬空判空判满混淆frontrear 直接判空或判满配套 tag/size/牺牲一格规则从最后一次操作的类型反推状态入队出队顺序错size 和指针刷新逻辑不一致操作顺序统一固定写代码时手动模拟一轮入队出队6.2 实测有效的做题冲刺步骤针对“队头指针、队尾指针指向类题目”我总结了一套做题步骤分享给正在备考的朋友第一步读题后先在草稿纸上画出一个状态图标出数组下标或链表节点用箭头画出 front 和 rear 当前位置。这一步能把抽象问题具象化避免对着题目空想。第二步确认题目的指针定义和队满队空方案的约定是牺牲一格、size 还是 tag。如果题目没有写默认按牺牲一格方案考研题最常见但要在最终答案里注明。第三步依次执行入队、出队操作每执行一步就刷新画图里的指针位置。不要只在脑子里算一定要手写记录。尤其是操作超过三次的时候画图能避免记忆错乱。第四步用元素个数公式逆向验证最终状态。如果最后要求的是 front 和 rear那就用元素个数是否符合操作次数来验证。比如一共入队6次出队4次最后应该剩2个元素套进公式如果结果不是2说明前面某步指针移动错了回头检查。第五步如果题目是代码填空题或手写题写完代码后在注释中补充说明“本代码采用 front 指向队头元素、rear 指向队尾元素下一个位置的定义”杜绝歧义。这一条在考试阅卷和面试中都有用能体现你是真懂而不是背模板。这个步骤我在模拟面试和辅导中带人用了几十遍正确率提升非常明显。核心原因就是它把“记忆驱动”变成了“推导驱动“每一步都有据可查。6.3 做得多了以后你会发现这些题其实都在考同一件事队头指针、队尾指针指向类题目无论换成循环队列、链式队列、循环数组、阻塞队列还是消息队列 offset本质核心都是同一个问题在一个有限或无限的空间里用两个游标维护一个先进先出的窗口窗口的左边界是队头右边界是队尾入队出队只是左右边界在移动而一切判断空、满、长度都是边界位置关系的某个函数表达。我自己刷题时最喜欢用这种方式给题目重新归类而不是按“题目来源”“教科书章节”去背。因为这样归类之后任何一道新题到你面前都可以迅速映射到某个熟悉的模型里比如一看是循环数组加 count立刻想到 ArrayBlockingQueue一看是 front 和 rear 都指向节点立刻想到不带头结点的链队入队操作。这种迁移能力才是做这类总结的最终收获。另外特别提醒一句网上不少文章把“front 指向队头元素”和“front 指向队头元素的前一个位置”混在一起讲看着像做起来细节全不同。你如果发现某本教材的例题和你的答案对不上不要先怀疑自己先回头确认它用的是哪种定义。我踩过这个坑当年复习时一度被“同一道题两个答案”折腾到怀疑人生后来才发现是两本书的 rear 约定不一样。最后再分享一个小技巧考试或面试时遇到队列相关的题目最好在草稿纸上先写出 “rear (rear 1) % maxsize” 和 “front (front 1) % maxsize” 这两行伪代码再开始推导。这两个式子是所有循环队列题的骨架把骨架立起来往里填判空判满条件就不容易乱。不管是日常做题还是给其他同学讲题我都用这套方法论效果一直很稳定。 
长河君 · 2026/9/13 21:18:17 · 阅读 1.2k 队头指针队尾指针全面总结：循环队列、链式队列与工程实践
队头指针、队尾指针类题目说句实话是数据结构笔试、考研和面试里最容易被秒杀也最容易被秒杀反杀的题型。说它简单是因为队列的框架就那么点东西说它阴险是因为不同教材、不同题目对 front 和 rear 的指向定义完全可能不一样——你在这一题里 rear 指向队尾元素换一题里 rear 指向队尾元素的下一个位置公式没变结果全变。很多同学来问我这类题不是不会队列入队出队而是被“指向定义”和“判空判满方式”绕晕了。这篇文章就把我这些年刷题、讲题过程中积累的队头指针队尾指针类题目做一个完整总结从最基础的指向概念到循环队列三种判空判满方案再到链式队列的指针操作和典型例题最后延伸到实际工程里消息队列、阻塞队列的同类思想。内容是一路从易到难排的建议按顺序读。1. 先搞清楚front 和 rear 到底指向谁1.1 队列的两种基本存储结构队列的逻辑结构是先进先出FIFO这个大家都熟悉。但物理上用顺序表实现还是用链表实现直接决定了 front 和 rear 指针的含义和移动方式。用顺序存储的时候队列用一个一维数组和两个整型变量来维护。数组存放元素front 指向队头rear 指向队尾入队时 rear 移动出队时 front 移动。这里最容易出问题的是出队时 front 向后移动后数组前面的空间就空出来了但 rear 只能往后走走到数组末尾时即使数组前面还有大量空闲也插不进新元素了。这就是经典的“假溢出”。顺序队列做不做成循环结构是这类题目的第一个分岔口。用链式存储的时候队列就是一条单链表front 指针指向第一个元素节点rear 指向最后一个元素节点。入队就是尾插出队就是头删。链式队列没有假溢出的问题但因为多了一个指针的维护细节题反而更多比如“不带头结点的链队出队时要注意什么”“front 和 rear 都为空时空不空”等等。1.2 指向定义的差异一切公式的地基做题之前必须先做一件事看题目里 front 和 rear 的初始化定义。我梳理了一下常见定义无非这四种front 指向队头元素rear 指向队尾元素的下一个位置教材经典款front 指向队头元素rear 指向队尾元素另一种经典款front 指向队头元素的前一个位置rear 指向队尾元素考研部分教材款front 和 rear 初始化为和数组下标有关的偏移量比如 -1 或 0配合特定操作逻辑定义不同入队出队时指针的移动方式完全不同计算元素个数的公式也不同。很多同学死记“队空条件是 front rear”结果遇到“front 指向队头元素的前一个位置”的定义就翻车因为那种定义下队空可能是 front rear队满也可能是 front (rear 1) % maxsize但元素个数公式却变成了 (rear - front maxsize) % maxsize。我给个实操建议拿到任何一道队列题目第一件事不是看题目问什么而是先判断 front 和 rear 的指向定义。如果是选择题题目里通常会写如果是简答题你需要在答案开头就说明自己采用的约定。这样至少能挽回一半分数。1.3 队空和队满判断的本质逻辑不管哪种存储结构、哪种指针定义判空判满的本质都是用指针之间的关系来表达“队列里还能不能放元素”和“队列里还有没有元素”这两个状态。顺序队列里最朴素的做法是 front rear 表示队空rear maxsize 表示队满假溢出。这种结构实现简单但浪费前面空出来的空间所以实际考试和工程里基本都是循环队列。循环队列里队空是 front rear队满则要看方案。为什么不能也让队满等于 front rear因为那样的话“队空”和“队满”就完全分不清了同一个条件两套意义。除非额外引入计数器或标志位否则单靠两个指针的值无法区分这两种状态。“区分不了就牺牲一个存储单元用来做约定”这就是牺牲一格方案的核心逻辑。后面两章会逐个展开。2. 循环队列的三套主流方案循环队列本质上就是用取模运算把数组的头尾接起来让 rear 到达数组末尾后能通过 (rear 1) % maxsize 回到数组开头。这样一来假溢出问题被解决代价是判空判满的条件需要重新设计。目前最主流的方案有三套我把它们的判断逻辑、元素个数公式、适用场景都拆开讲。2.1 牺牲一个存储单元方案考研/笔试最常用约定 rear 指向队尾元素的下一个位置front 指向队头元素。队列初始化时 front rear 0。入队时执行if ( (rear 1) % maxsize front ) // 队满 else { arr[rear] x; rear (rear 1) % maxsize; }出队时if ( front rear ) // 队空 else { x arr[front]; front (front 1) % maxsize; }队满条件是 (rear 1) % maxsize front。因为 rear 指向的地方不能再存元素必须预留一个空位来区分队满和队空所以该方案下队列最多能存 maxsize - 1 个元素。元素个数公式是 (rear - front maxsize) % maxsize。我解释一下为什么这里要加 maxsize 再取模。循环队列里 rear 可能已经越过数组末尾回到前面比如 front 5rear 2物理上 rear front直接相减是负数。加一个 maxsize 让差值为正再取模得到真实元素个数。这个公式是整个循环队列题目的核心工具务必做到看到 front 和 rear 就能写出来。2.2 增设 size 计数方案牺牲一个存储单元总觉得有点浪费尤其是数组大小刚好等于需求上限时。更优雅的方案是给队列结构体加一个 size 字段专门记录当前元素个数。结构体定义类似typedef struct { int data[maxsize]; int front; // 队头下标 int rear; // 队尾下标指向队尾元素的下一个位置也可以指向队尾元素只要操作统一 int size; // 当前元素个数 } sqQueue;初始化时 front rear 0size 0。入队时先判断 size maxsize 就队满否则 data[rear] xrear (rear 1) % maxsizesize。出队时先判断 size 0 就队空否则 x data[front]front (front 1) % maxsizesize--。这套方案最大的优点不需要牺牲存储单元队列可以存满 maxsize 个元素。判空 condition size 0判满 condition size maxsize直观且不会混淆。代价就是多维护一个变量出队入队时都要同步更新 size。2.3 增设 tag 标志位方案还有一个思路是加 tag 标志位。核心逻辑是虽然 front rear 这个条件既能表示队空也能表示队满但我们可以用 tag 来记录最后一次操作是入队还是出队。如果最后一次操作是入队导致 front rear那必然是队满如果是出队导致的 front rear那必然是队空。具体实现typedef struct { int data[maxsize]; int front; int rear; int tag; // 0 表示最近一次是出队1 表示最近一次是入队 } sqQueue;入队if ( front rear tag 1 ) // 队满 else { data[rear] x; rear (rear 1) % maxsize; tag 1; }出队if ( front rear tag 0 ) // 队空 else { x data[front]; front (front 1) % maxsize; tag 0; }这套方案的判断条件比牺牲一格方案稍微绕一点但比 size 方案省一个整型字段。说实话tag 方案在考研真题里出现的频率不如牺牲一格方案但在面试题里偶尔会看到因为它考察的是对“状态区分”本质的理解。如果你能把三套方案的原理都吃透这类题目基本逃不出你手心。2.4 不同方案下判空判满和元素个数总结我把三种方案的核心要点整理成了一张表做题时直接对标方案初始化队空条件队满条件元素个数最多能存元素数牺牲一格frontrear0front rear(rear1)%maxsize front(rear-frontmaxsize)%maxsizemaxsize-1增设sizefrontrear0, size0size 0size maxsizesizemaxsize增设tagfrontrear0, tag0frontrear tag0frontrear tag1(rear-frontmaxsize)%maxsizemaxsize注意这张表默认的是“front 指向队头元素rear 指向队尾元素的下一个位置”。如果题目改成了别的指向定义判断条件和元素个数公式要跟着调整。我在第 4 章会专门讲这种变式题。3. 链式队列的 front 和 rear 操作顺序队列讲完链式队列也不能看轻。链队从逻辑上说是单链表front 是头指针rear 是尾指针。区别只在“带头结点”还是“不带头结点”这两个版本的操作细节和边界处理不一样。3.1 带头结点的链队带头结点意味着有一个哨兵节点front 始终指向这个头结点不存储真实数据。初始化时front (LinkNode*)malloc(sizeof(LinkNode)); rear front; rear-next NULL;此时 front rear队空。入队时创建新节点 p让 rear-next prear p。出队时由于第一个数据节点是 front-next如果 front-next NULL说明队列空否则保存 front-next 的节点front-next 那个节点的 next如果删的是最后一个节点还要把 rear 指回 front否则 rear 会指向一个已经释放的内存。带头结点版本的好处是出队操作统一不需要判断“删掉的是不是最后一个节点”时额外处理 rear 指向 NULL 的情况——不其实还是需要的。因为删除最后一个节点后rear 仍然指向被删除节点必须把 rear 拉回 front。这个细节特别适合出选择题入队、出队后 rear 和 front 分别指向哪里。3.2 不带头结点的链队不带头结点的链队front 直接指向第一个数据节点rear 指向最后一个数据节点。初始化时 front rear NULL。队空条件就是 front NULL rear NULL或者 front NULL因为 front 为 NULL 时 rear 也一定为 NULL反过来不成立吗实际上如果队列非空 front 肯定不空如果队空两者都该是 NULL。入队时如果原来队空要让 front 和 rear 都指向新节点否则在尾部执行 rear-next newnode; rear newnode。出队时用临时指针保存当前 front 节点front front-next如果 front 变成 NULL说明队列已经空了此时还要把 rear NULL。这一步是新手最容易漏的。我在实际教学中发现不带头结点版本最容易出的错就是删除最后一个节点后rear 还指向那个已经被释放的节点导致后续入队时往野指针后面挂节点轻则数据错乱重则直接段错误。排查链队问题第一步永远都是检查 rear 是否兜底复位。3.3 链队出队入队的细节和边界题链队虽然不是本篇文章题目的绝对主角但“队头指针、队尾指针指向类题目”在链队里有一个非常经典的考法给出一个链式队列的初始状态几个节点front 指向哪rear 指向哪连续执行若干次入队操作再连续执行若干次出队操作问最终 front 和 rear 指向哪里队列里有哪些元素这种题本质就是模拟链表的尾插和头删。我给大家一个做题标准流程画出链表图把每个节点标上编号a1、a2、a3……用箭头画出 front 和 rear 当前指向的位置每做一次入队操作在链表尾部增加一个节点移动 rear每做一次出队操作删除头部节点移动 front特别注意出队导致队列空时rear 也要变成 NULL不带头结点场景按这个流程走链队题基本不可能错。另外注意链队不像循环队列有判满的概念理论上只要内存够就能一直入队所以链队题目一般只考“空不空”和“指针指向哪里”不考“满不满”。4. 实战题解从易到难过一遍典型题目这一章我把网上和书上常见的“队头指针、队尾指针指向类题目”做了个归类每类配一两个典型题带完整推导过程。你们做题时如果卡住了回来对照这一类题型的解题套路基本能秒杀。4.1 入队出队后指针变化类题目例题 1设循环队列的数组容量为 6初始 front rear 2。依次执行入队 a、b、c、d再执行出队两次然后入队 e。使用牺牲一个存储单元方案问最终 front 和 rear 分别等于多少队列中剩余元素是什么。解牺牲一格方案下队满条件是 (rear 1) % 6 front所以这个循环队列最多能存 5 个元素。初始front 2rear 2队空入队 aarray[2] arear (2 1) % 6 3入队 barray[3] brear (3 1) % 6 4入队 carray[4] crear (4 1) % 6 5入队 darray[5] drear (5 1) % 6 0此时 front 2rear 0元素有 a、b、c、d共 4 个验证一下 (0 - 2 6) % 6 4正确出队第一次取出 array[2] afront (2 1) % 6 3出队第二次取出 array[3] bfront (3 1) % 6 4入队 earray[0] erear (0 1) % 6 1最终 front 4rear 1队列中元素是 c下标4、d下标5、e下标0共 3 个验证元素个数(1 - 4 6) % 6 3正确。这类题的核心就是两步先根据入队出队动态更新指针最后用元素个数公式校验一遍。我强烈建议每次算完都要用公式校验因为选择题一旦错一步后面全错但用公式能从整体上确认指针变化是否合理。4.2 循环队列元素个数计算类题目例题 2用牺牲一格方案实现循环队列maxsize 20当前 front 8rear 3问队列中有多少个元素代入公式(rear - front maxsize) % maxsize (3 - 8 20) % 20 15 % 20 15。这里解释一下为什么答案是 15 而不是“rear 在 front 前面所以没元素”。因为 rear 已经通过取模绕到前面了物理上它指向的位置在 front 后面的地址空间里没有元素但逻辑上队列是从 front 位置到 rear 位置沿着循环方向的所有元素也就是下标 8 到 19 的元素再加上下标 0 到 2 的元素正好 15 个。这个题几乎是循环队列必考题公式理解到位就行。如果题目改成“rear 指向队尾元素front 指向队头元素的前一个位置”那元素个数公式需要变成 (rear - front maxsize) % maxsize 吗其实还是一样的只要两个指针在循环数组上且移动方向一致这个公式就成立。真正的区别在于判空判满条件不同以及最大容纳量是否要减一。4.3 变式陷阱题rear 指向队尾元素场景例题 3一个循环队列front 指向队头元素rear 指向队尾元素初始 front rear 0 表示队空。数组容量为 10问队满条件是什么最多能存几个元素这个定义下入队和出队的移动顺序要反过来。入队时先移动 rear 再赋值不对因为 rear 指向队尾元素插入前 rear 指向最后一个元素插入后 rear 要指向新元素。初始时队列为空front rear 0此时没有队尾元素第一次插入必须特殊处理不然 front 和 rear 的指向就乱了。我推荐采用的方案是初始化 front rear 0 表示队空入队时若队空data[0] xfront 和 rear 都保持 0 不动不对rear 应该指到新插入元素的下标。更常见的做法是初始化 front 0rear maxsize - 1或者 front rear -1 表示空。如果初始化 front rear 0 又要表示空那么插入第一个元素时 data[0] xrear 不移动还是 0因为 rear 本来就指向第 0 个元素。这样第二个元素插入时先 rear (rear 1) % maxsize再 data[rear] x。这样定位后队空条件仍然是 front rear但这和初始状态 front rear 0 的来源不同一个是真正的空一个是有 1 个元素时 rear 恰好还在 0……这就引出了又一个坑如果队里只有一个元素front 指向它rear 也指向它front rear 成立但队列并不空。所以这种定义下判空条件 front rear 不成立必须另外加计数器或标志位来区分“一个元素”和“空”。这正是考研题里常埋的变式rear 指向队尾元素时单单 front rear 不能作为判空条件。有些教材为了规避这个问题就把初始化改成 front 0rear maxsize - 1插入时先移动 rear这样空状态时 front 和 rear 不相等非空时有可能相等。但判空就成了 rear (front - 1 maxsize) % maxsize。我做题时遇到 rear 指向队尾元素这种定义统一的做法是初始化 front 0rear maxsize - 1入队先 rear (rear 1) % maxsize 再赋值出队先取 front 位置的元素再 front (front 1) % maxsize。这样队空rear (front - 1 maxsize) % maxsize 不对初始化 front0rearmaxsize-1 时front 指向第一个元素rear 指向最后一个元素差值为 rear (front - 1 maxsize) % maxsize 时队列为空即 rear 在 front 的前一个位置。队满rear 再移动一步就追上 front即 (rear 1) % maxsize front。最多容纳 maxsize 个元素因为不需要牺牲一格front 和 rear 之间允许完全绕一圈填满。为了不让大家混乱我总结成一句话先用题目的文字判断 rear 是“指向队尾元素”还是“指向队尾元素的下一个位置”然后反推对应的初始化方式和判空判满条件不要背某一个固定结论就硬套。这是所有队头指针队尾指针类题目中最重要的做题习惯。4.4 栈和队列对比中的指针题栈和队列对比类题目也经常围绕“指针指向”展开。比如问若用两个栈模拟一个队列入队操作怎么做、出队操作怎么做。这种题虽然题目里没有 front 和 rear但本质上“栈底充当队尾、栈顶充当队头”的思维就是指针指向思想的另一种表达。这类题目我在面试辅导时总结的口诀是入队尽可能往入栈塞出队时先把入栈元素全部弹到出栈再从出栈弹出。核心点在于“只能从出栈弹元素”是队头“只能往入栈放元素”是队尾。每次操作后两个栈里元素的分布就对应着 front 和 rear 的动态变化经常作为链队/循环队列题目的变形出现。5. 从考研题到工程实践队列思想的延伸5.1 C STL queue 和 priority_queue 的底层实现C STL 的 queue 默认底层容器是 deque不是顺序数组也不是链表而是一个双端队列。deque 的内部结构是一段段连续空间拼接起来的start 和 finish 两个迭代器分别指向队头和队尾的边界本质上就是 front 和 rear 指针的工程化实现。priority_queue 默认是大顶堆底层是 vector。它没有传统意义上的 front、rear 指针而是通过堆的下标关系维护优先级。很多初学者把 priority_queue 误当成普通队列来理解面试如果问到“队头指针队尾指针指向”就更晕了。我的建议是遇到 priority_queue 题目先忘掉 front 和 rear转用“完全二叉树数组下标”的思维来解决它是堆结构不是队列结构只是名字叫 queue 而已。CTM 和考研真题里很少出现 priority_queue 的指针指向题但如果问到“用数组实现堆的入堆、出堆时下标如何变化”其实和队列的 front/rear 计算遵循同一种底层逻辑用下标维护一个可变范围的存储窗口。5.2 阻塞队列与线程池的线程安全队列实际工程里线程池的任务队列常常是一个有界阻塞队列比如 Java 的 ArrayBlockingQueue、LinkedBlockingQueue。ArrayBlockingQueue 底层就是循环数组putIndex 和 takeIndex 分别对应 rear 和 frontcount 对应 size。它采用的正是我上文说的“伤害加 size”方案用 count 区分队空和队满通过 ReentrantLock 和 Condition 实现阻塞唤醒。面试题经常会问“线程池的阻塞队列怎么选”这其实就是在考循环队列的指针模型。有界队列ArrayBlockingQueue适合资源受限场景无界队列LinkedBlockingQueue 默认无界适合任务量波动大的场景。下面这张表是我整理的选型对照队列类型底层结构是否可能有界队头/队尾维护方式适用场景ArrayBlockingQueue循环数组是putIndex/takeIndex 取模移动固定大小线程池防止任务堆积LinkedBlockingQueue链表可无界可有界head/last 节点指针任务波动大吞吐优先SynchronousQueue无缓存逻辑上有界不存储元素直接交接高并发、快速传递任务PriorityBlockingQueue堆可无界数组下标维护堆序任务带优先级需重排序你看ArrayBlockingQueue 的 putIndex 和 takeIndex跟循环队列里的 rear 和 front 几乎是一模一样的思路连取模操作都一致。只不过多了一个锁和两个 Condition把“队满时入队线程等待”“队空时出队线程等待”这两件事做了阻塞管理。5.3 消息队列的消费进度与重复消费问题消息队列里的“消费偏移量”其实也是一种队头指针思想。比如 Kafka 的 consumer group 里有一个 offset记录消费者当前消费到的位置这个 offset 就相当于 front 指针生产者不断追加消息到 log 末尾对应的是队尾指针不断前进。消费者手动提交 offset 还是自动提交决定了消息是“已经读了”还是“已确认”。重复消费问题在工程面试里特别高频。为什么消息会被重复消费从队列模型角度看就是消费者读取消息后本地处理完了但 offset 还没来得及更新提交此时队列认为这条消息还没被消费就重新分配给了另一个消费者于是同一份数据被处理两次。解决办法无非是“保证 offset 提交的时机和消息处理的幂等性”比如处理完业务后异步提交 offset或者业务逻辑天然幂等。这类面试题表面上叫“消息队列重复消费问题”落到数据结构底层其实仍然是队头指针消费 offset和队尾指针生产位点之间的游标管理问题。你如果能把循环队列里 front 和 rear 的“滞后追平”想明白面试答消息队列的 offset 提交机制就会比别人顺。这个跨知识点迁移是我带学生时反复强调的也是很多选手从“会做题”到“真理解”的分水岭。6. 常见错误与自查清单6.1 队头队尾指针题目的高频翻车点错误一拿到题目没确认 front 和 rear 的指向定义直接套公式。比如牺牲一格方案的元素个数公式 (rear-frontmaxsize)%maxsize在“rear 指向队尾元素”定义下也成立但判空判满条件变了很多人套错。错误二循环队列取模时忘记“环境”。front 8rear 3 时直接算 3-8 得负数然后不知道怎么办。正确处理是加上 maxsize 再取模抵消循环回绕的影响。错误三链式队列删除最后一个元素后没有把 rear 置空。无论是带头结点还是不带头结点删除最后一个节点后 rear 都会变成野指针必须重新赋值。错误四循环队列用 size 方案时size 更新和指针移动顺序搞反。入队一定是先放数据再动指针再 size出队一定是先取出数据再动指针再 size--。顺序不是唯一但必须统一否则考场上一紧张就一边定义一个样代码就废了。错误五把“队空”和“队满”混为一谈尤其是 front rear 时忘记后面还要判断 tag 或者 size。任何一个判空判满题都要从“上一次操作是入队还是出队”的角度再验证一遍这是一个很好的自查习惯。我把这些错误做成了一张速查表错误类型错误表现正确思路自查方法定义未确认直接套公式先判断 front/rear 指向定义读题后先写下指针含义再动笔取模为负直接报负数或溢出加 maxsize 再取模任何 front、rear 相减后先加 maxsize链队野指针删完最后一个节点后 rear 无用判断 front 为空时同步把 rear 置空每次出队后检查 rear 是否悬空判空判满混淆frontrear 直接判空或判满配套 tag/size/牺牲一格规则从最后一次操作的类型反推状态入队出队顺序错size 和指针刷新逻辑不一致操作顺序统一固定写代码时手动模拟一轮入队出队6.2 实测有效的做题冲刺步骤针对“队头指针、队尾指针指向类题目”我总结了一套做题步骤分享给正在备考的朋友第一步读题后先在草稿纸上画出一个状态图标出数组下标或链表节点用箭头画出 front 和 rear 当前位置。这一步能把抽象问题具象化避免对着题目空想。第二步确认题目的指针定义和队满队空方案的约定是牺牲一格、size 还是 tag。如果题目没有写默认按牺牲一格方案考研题最常见但要在最终答案里注明。第三步依次执行入队、出队操作每执行一步就刷新画图里的指针位置。不要只在脑子里算一定要手写记录。尤其是操作超过三次的时候画图能避免记忆错乱。第四步用元素个数公式逆向验证最终状态。如果最后要求的是 front 和 rear那就用元素个数是否符合操作次数来验证。比如一共入队6次出队4次最后应该剩2个元素套进公式如果结果不是2说明前面某步指针移动错了回头检查。第五步如果题目是代码填空题或手写题写完代码后在注释中补充说明“本代码采用 front 指向队头元素、rear 指向队尾元素下一个位置的定义”杜绝歧义。这一条在考试阅卷和面试中都有用能体现你是真懂而不是背模板。这个步骤我在模拟面试和辅导中带人用了几十遍正确率提升非常明显。核心原因就是它把“记忆驱动”变成了“推导驱动“每一步都有据可查。6.3 做得多了以后你会发现这些题其实都在考同一件事队头指针、队尾指针指向类题目无论换成循环队列、链式队列、循环数组、阻塞队列还是消息队列 offset本质核心都是同一个问题在一个有限或无限的空间里用两个游标维护一个先进先出的窗口窗口的左边界是队头右边界是队尾入队出队只是左右边界在移动而一切判断空、满、长度都是边界位置关系的某个函数表达。我自己刷题时最喜欢用这种方式给题目重新归类而不是按“题目来源”“教科书章节”去背。因为这样归类之后任何一道新题到你面前都可以迅速映射到某个熟悉的模型里比如一看是循环数组加 count立刻想到 ArrayBlockingQueue一看是 front 和 rear 都指向节点立刻想到不带头结点的链队入队操作。这种迁移能力才是做这类总结的最终收获。另外特别提醒一句网上不少文章把“front 指向队头元素”和“front 指向队头元素的前一个位置”混在一起讲看着像做起来细节全不同。你如果发现某本教材的例题和你的答案对不上不要先怀疑自己先回头确认它用的是哪种定义。我踩过这个坑当年复习时一度被“同一道题两个答案”折腾到怀疑人生后来才发现是两本书的 rear 约定不一样。最后再分享一个小技巧考试或面试时遇到队列相关的题目最好在草稿纸上先写出 “rear (rear 1) % maxsize” 和 “front (front 1) % maxsize” 这两行伪代码再开始推导。这两个式子是所有循环队列题的骨架把骨架立起来往里填判空判满条件就不容易乱。不管是日常做题还是给其他同学讲题我都用这套方法论效果一直很稳定。