很多人复习数据结构时卡住的地方往往不是红黑树也不是图的最短路径而是一个看起来不起眼的习题——习题3.12另类循环队列。它不涉及复杂算法也没有刁钻的链表操作却让不少人在纸上推演时反复翻车。核心问题就一句话循环队列能不能在不浪费一个存储空间的前提下仍然正确区分“队空”和“队满”答案就是给队列加一个标志位tag。今天我把这道题拆开讲从题目背景、存储设计到入队出队的每一步细节、完整代码和那些只有真正写过才会踩到的坑一次说清楚。不管你是准备期末、考研复试还是单纯想把循环队列吃透这份笔记都能直接拿来参考。1. 习题拆解从标准循环队列到带tag的另类实现1.1 你熟悉的循环队列为什么总是牺牲一个格子先回忆一下标准循环队列的样子。它用一维数组模拟环形结构维护两个指针front指向队头元素rear指向队尾元素的下一个位置。入队时元素写到base[rear]然后rear往后挪出队时从base[front]取元素然后front往后挪。指针走到数组末尾时通过取模运算绕回开头形成一个环。标准循环队列最大的问题是空和满的判定冲突。当队列为空时front和rear相等当队列正好存满时front和rear也会相等。这两个状态仅凭两个指针无法区分所以教科书普遍采用“牺牲一个存储单元”的办法规定当(rear 1) % MAXSIZE front时算队满。这样一来一个容量为MAXSIZE的数组实际最多只能存MAXSIZE - 1个元素。这个做法的代价很直观白白浪费一个格子。如果MAXSIZE很大多留一个空位似乎无所谓但如果数组小、或者每个元素都是重量级结构体浪费的那一个单元就不能忽略。习题3.12的“另类”正是冲着这个问题来的。1.2 “另类”到底另类在哪给队列加一个状态开关习题3.12给出的方案是在循环队列结构里增加一个标志域tag专门用来区分front和rear相等时的两种状态tag 0表示front等于rear是因为队列为空tag 1表示front等于rear是因为队列已满。有了这个标志队空与否就不再需要牺牲数组空间来判断整个数组的每一个位置都能用来存放元素。也就是说容量为MAXSIZE的循环队列可以真正存下MAXSIZE元素而不是MAXSIZE - 1。这里的“另类”可以这样理解普通循环队列用“空间换判断”另类循环队列用“一个额外的标志位换空间”。两者没有绝对的对错但tag方案非常适合“空间紧张、要求全部格子可用”的场景也是不少教材在“队列”章节留下的经典扩展题。对比项标准循环队列另类循环队列tag方案区分空/满的依据(rear1)%MAX frontfrontrear 且 tag 为 0/1最大元素个数MAXSIZE - 1MAXSIZE额外存储代价无一个整型或布尔型 tag空满判断逻辑相对简单多一步 tag 维护适用场景空间不敏感、代码求稳空间紧张、要求阵列全用1.3 一来一回的取模运算环形队列的数学基础要理解另类循环队列绕不开取模运算。数组下标范围是0到MAXSIZE-1指针加1之后如果等于MAXSIZE就通过% MAXSIZE回到0。这就像钟表走到12点后重新从1开始本质上是把“直线数组”卷成一个“逻辑圆环”。常见公式入队后移动队尾rear (rear 1) % MAXSIZE出队后移动队头front (front 1) % MAXSIZE队列长度非空非满时(rear - front MAXSIZE) % MAXSIZE第三个公式很多人不理解为什么末尾要加MAXSIZE再取模因为当rear小于front时如果不加MAXSIZE会得到负数。例如front 3rear 1真实长度应该是3下标3、0、1各有一个元素而1 - 3 -2加MAXSIZE假设MAXSIZE 5后变成3再取模还是3。加MAXSIZE这步本质上是在借位把环形上的“跨过0点”变成连续区间上的正向距离。明白了这个环形模型再看tag标志的更新逻辑就不容易出错了。2. 核心数据结构设计tag标志怎么用才不出错2.1 结构体定义与字段职责另类循环队列的结构体和标准循环队列几乎一样只多了一个tag成员#define MAXQSIZE 5 #define OK 1 #define ERROR 0 typedef int QElemType; typedef int Status; typedef struct { QElemType *base; // 动态分配的数组空间 int front; // 队头指针指向队头元素 int rear; // 队尾指针指向下一个入队位置 int tag; // 标志0表示空1表示满 } SqQueue;先明确两个指针的语义后面所有操作都依赖这个语义front始终指向当前队头元素的位置rear始终指向下一个新元素将要写入的位置队列元素在逻辑上位于[front, rear)这个左闭右开区间内。为什么要约定成左闭右开因为rear天然指向“空的写入点”而不是“最后一个元素”。入队时先把元素写到base[rear]再让rear后移这样区间[front, rear)始终准确描述有效元素。出队时front后移区间随之缩小。这种约定和标准循环队列一致不容易造成混乱。2.2 队空、队满判定的唯一准则另类循环队列的判定规则可以浓缩成两条判断队空Q.front Q.rear Q.tag 0 队满Q.front Q.rear Q.tag 1关键点在于tag不是全局的空满标签它只在front等于rear时才有意义。当front不等于rear时队列既非空也未满tag的值是什么都不影响判断。为什么tag能一直保持正确因为每次入队后只有rear移动到与front重合时才说明“刚刚放进的这个元素把整个队列塞满了”此时置tag 1每次出队后只有front移动到与rear重合时才说明“刚刚取出的元素是最后一个队列变空了”此时置tag 0。换句话说tag记录的是最近一次导致front与rear重合的操作结果。这个细节必须刻在脑子里。很多错误代码会在入队时无条件写tag 1这样队列明明没满tag却一直为1后面一入队就误判满再也没法正常操作。2.3 初始化时最容易忽略的细节初始化函数很简单但tag 0这一步容易漏掉Status InitQueue(SqQueue *Q) { Q-base (QElemType *)malloc(MAXQSIZE * sizeof(QElemType)); if (Q-base NULL) { return ERROR; } Q-front 0; Q-rear 0; Q-tag 0; // 初始状态front rear 且 tag 0表示空 return OK; }初始化之后front、rear都为0二者相等。如果tag没置0或者随机值第一个入队判断队满时可能出错第一个出队判断队空时也可能出错。这里还藏着一个分配问题必须分配MAXQSIZE个元素而不是MAXQSIZE - 1个。标准循环队列通常写MAXQSIZE - 1来计算可用容量有些同学惯性延续结果到tag方案里就白白少了一块空间甚至写入时越界。3. 入队出队操作实现每一步都要有依据3.1 入队先判满后写入再移动rear入队操作的完整逻辑Status EnQueue(SqQueue *Q, QElemType e) { if (Q-front Q-rear Q-tag 1) { return ERROR; // 队满入队失败 } Q-base[Q-rear] e; // 元素写入当前rear指向的位置 Q-rear (Q-rear 1) % MAXQSIZE; // rear后移 if (Q-front Q-rear) { Q-tag 1; // 新元素把队列填满了 } return OK; }顺序必须严格为“先判满再写入后移动最后更新tag”。为什么不能先把rear加1再写入如果rear先移动新元素写入位置就变成了加1后的下标而front没变这会破坏[front, rear)的区间语义。一次入队也许看不出问题连续入队后第一个元素位置和队列内容全乱出队取到的就不是最先入队的元素。为什么更新tag要放在last step因为要移动完rear之后才能知道新rear是否与front重合。如果插入后front和rear确实重合说明这个元素是第MAXQSIZE个队列到达最大容量必须置tag 1如果插入后front和rear不重合说明还有空闲位置不能置tag 1。3.2 出队先判空后取值再移动front出队操作对应如下Status DeQueue(SqQueue *Q, QElemType *e) { if (Q-front Q-rear Q-tag 0) { return ERROR; // 队空出队失败 } *e Q-base[Q-front]; // 取队头元素 Q-front (Q-front 1) % MAXQSIZE; // front后移 if (Q-front Q-rear) { Q-tag 0; // 最后一个元素被取出队列变空 } return OK; }出队判空条件要特别注意当front rear且tag 0时才是真正空如果front rear且tag 1说明队列处于满状态里面仍有MAXQSIZE个元素完全可以出队。满状态下front和rear重合这时取出base[front]再让front后移一步front就会离开rear队列变为非满如果此时队列里原来只有一个元素front后移后会再次与rear重合tag随之置0。有些同学把出队写成“若front rear直接报错”这在标准循环队列里是对的但在另类循环队列里就是严重误判。tag加入后front rear不再是空队列的充分条件。3.3 取队头与队列长度别把读和删混在一起取队头元素GetHead和出队DeQueue不是一回事。取队头只读不改不能移动front指针出队会真正删除元素。有的考试代码为了省事取队头时直接调用DeQueue这是不允许的因为会破坏队列状态。Status GetHead(SqQueue Q, QElemType *e) { if (Q.front Q.rear Q.tag 0) { return ERROR; // 空队列没有队头可取 } *e Q.base[Q.front]; return OK; }求队列长度时情况要分三类int QueueLength(SqQueue Q) { if (Q.front Q.rear Q.tag 0) { return 0; // 空 } if (Q.front Q.rear Q.tag 1) { return MAXQSIZE; // 满 } return (Q.rear - Q.front MAXQSIZE) % MAXQSIZE; }直接用(rear - front MAX) % MAX求出的结果只在front ! rear时有效。当队列满时这个公式会返回0必须用tag单独处理。这是另类循环队列里最容易被忽略的“公式失效点”。4. 完整C代码与测试用例可直接抄走4.1 一个可直接运行的C实现把上面几个函数合并成一个完整文件再加一个简单的打印函数和主函数就可以在本地直接跑#include stdio.h #include stdlib.h #define MAXQSIZE 3 #define OK 1 #define ERROR 0 typedef int QElemType; typedef int Status; typedef struct { QElemType *base; int front; int rear; int tag; } SqQueue; Status InitQueue(SqQueue *Q) { Q-base (QElemType *)malloc(MAXQSIZE * sizeof(QElemType)); if (!Q-base) return ERROR; Q-front Q-rear 0; Q-tag 0; return OK; } Status EnQueue(SqQueue *Q, QElemType e) { if (Q-front Q-rear Q-tag 1) return ERROR; Q-base[Q-rear] e; Q-rear (Q-rear 1) % MAXQSIZE; if (Q-front Q-rear) Q-tag 1; return OK; } Status DeQueue(SqQueue *Q, QElemType *e) { if (Q-front Q-rear Q-tag 0) return ERROR; *e Q-base[Q-front]; Q-front (Q-front 1) % MAXQSIZE; if (Q-front Q-rear) Q-tag 0; return OK; } Status GetHead(SqQueue Q, QElemType *e) { if (Q.front Q.rear Q.tag 0) return ERROR; *e Q.base[Q.front]; return OK; } int QueueLength(SqQueue Q) { if (Q.front Q.rear Q.tag 0) return 0; if (Q.front Q.rear Q.tag 1) return MAXQSIZE; return (Q.rear - Q.front MAXQSIZE) % MAXQSIZE; } void PrintQueue(SqQueue Q) { printf(front%d rear%d tag%d length%d\n, Q.front, Q.rear, Q.tag, QueueLength(Q)); } int main(void) { SqQueue Q; QElemType e; InitQueue(Q); printf(空队列状态); PrintQueue(Q); printf(入队 10); EnQueue(Q, 10); PrintQueue(Q); printf(入队 20); EnQueue(Q, 20); PrintQueue(Q); printf(入队 30); EnQueue(Q, 30); PrintQueue(Q); printf(再入队 40应该失败); if (EnQueue(Q, 40) ERROR) { printf(入队失败队列已满。\n); } PrintQueue(Q); printf(取队头); if (GetHead(Q, e) OK) { printf(队头元素%d\n, e); } printf(出队); if (DeQueue(Q, e) OK) { printf(取出元素%d\n, e); } PrintQueue(Q); printf(入队 40); EnQueue(Q, 40); PrintQueue(Q); printf(出队); if (DeQueue(Q, e) OK) { printf(取出元素%d\n, e); } PrintQueue(Q); printf(出队); if (DeQueue(Q, e) OK) { printf(取出元素%d\n, e); } PrintQueue(Q); printf(出队); if (DeQueue(Q, e) OK) { printf(取出元素%d\n, e); } PrintQueue(Q); printf(空队列出队应该失败); if (DeQueue(Q, e) ERROR) { printf(出队失败队列为空。\n); } PrintQueue(Q); return 0; }这里为了便于观察MAXQSIZE设成了3方便手工推演。实际题目里可能是5逻辑完全一样。4.2 用手工推演验证逻辑你可以按下面这个序列在纸上画一个长度为3的环形数组逐步执行“入A、入B、出A、入C、入D、出队三次”。操作frontreartag队列内容从front开始环形读说明初始000空空队列入队A010A正常入队B020A、B正常出队取A120B正常入队C100B、Crear从2绕回0入队D111B、C、D写满frontrear且tag1出队取B210C、D满变非满出队取C010D正常出队取D110空frontrear且tag0重点看入队D那一步入队前front 1rear 0队列长度是2还差一个空位。元素D写入base[0]rear变成1。此时front和rear都等于1队列满所以立刻把tag置1。如果没有这一步后面虽然能继续入队但队列多塞一个元素数组被覆盖逻辑彻底崩掉。4.3 自动化验证让程序自己证明自己是错的手工推演能验证简单序列但考场上时间有限最好养成写自动化检查的习惯。思路不复杂在main里维护一个普通数组作为“影子队列”另类循环队列每执行一次入队或出队影子队列也同步执行每一步都断言二者的长度相等、队头元素相同。更简单的验证逻辑可以写成这样初始化后断言QueueLength 0连续入队MAXQSIZE次每次都返回OK长度从1递增到MAXQSIZE第MAXQSIZE 1次入队必须返回ERROR连续出队MAXQSIZE次每次都返回OK长度递减到0第MAXQSIZE 1次出队必须返回ERROR中途用GetHead读取队头验证与出队取出的值一致。这套断言跑一遍能兜住大多数“漏更新tag”和“判空判满写反”的问题。我在自己调试时发现大部分隐藏错误都会在第4步以后暴露因为那时队列已经循环绕回front和rear的关系不再直观。5. 高频错误自查清单考前必看5.1 沿用标准循环队列的判满条件最典型的错误是把入队判满写成if ((Q-rear 1) % MAXQSIZE Q-front) return ERROR;这是标准循环队列的判满方法在另类循环队列里会造成极大的浪费——明明还能放一个元素却提前判满。改正后应该是if (Q-front Q-rear Q-tag 1) return ERROR;判断“空”同理不能再简单写if (Q-front Q-rear)。5.2 tag更新的时机反了我见过不少同学在入队后无条件写Q-tag 1在出队后无条件写Q-tag 0。直接把tag当成“刚才做了一次入队”的标志而忘记了它真正的职责是“当前front与rear重合时队列是空还是满”。正确时机只有两个入队后如果front rear说明满了置tag 1出队后如果front rear说明空了置tag 0。如果front ! reartag保持原值就行。这里的原值可能是0也可能是1但反正不会参与判空判满留着不影响正确性。当然如果你想让状态更清晰也可以在每次入队/出队后统一根据当前状态刷新tag但效果其实一样。5.3 入队出队时指针移动顺序反了入队时应该是“先写base[rear]再移动rear”出队时应该是“先取base[front]再移动front”。反过来的话第一次操作就可能出错入队如果先把rear加1再写入第一个元素写到了下标1而不是下标0front依然为0元素区间[front, rear)变成了[0, 1)但实际上base[0]是空的base[1]才有元素。出队取front位置会取到垃圾值。出队如果先把front加1再取元素取到的就是第二个元素队头元素被跳过且永久丢失。5.4 取队头操作被误写成了出队考试里常见两种错误写法// 错误写法1改动front破坏队列 Status GetHead(SqQueue *Q, QElemType *e) { *e Q-base[Q-front]; Q-front (Q-front 1) % MAXQSIZE; return OK; } // 错误写法2不判空空队列时取到无效值 Status GetHead(SqQueue Q, QElemType *e) { *e Q.base[Q.front]; return OK; }正确版本要同时做到只读值、不移动front、先判空。很多题目的判分点就藏在这个小函数里。5.5 几个低级但常见的崩溃点分配空间时用了MAXQSIZE - 1导致明明数组可以存5个元素代码却只允许4个而且第5次入队写入越界。初始化后忘记给tag赋0front rear且tag为随机值程序一运行就判满或判空。malloc之后没有判空内存不足时直接使用空指针。修改tag时用了if (Q-rear Q-front)少写一个等号变成赋值这个错误极其隐蔽浪费过我一个下午。队列长度函数里只写了(rear - front MAX) % MAX没处理front rear且tag 1的情况满队列会显示长度0。6. 从习题到实战另类循环队列还能这么用6.1 空间利用率100%的价值与代价tag方案的直接收益是循环队列的数组空间被100%利用。在嵌入式、通信协议、图像处理这类内存紧张的场景里一块环形缓冲区可能只有几十个字节浪费一个字节都可能影响性能更不用说浪费一个元素空间。用一个int型tag换一个完整元素位通常很划算。代价也很明确每次入队、出队都要维护tag逻辑比标准循环队列多一步。如果队列容量极大MAXQSIZE 100000牺牲的一个空间几乎可以忽略标准循环队列反而更简洁、更不容易出错。所以不要抱着“tag方案一定更好”的念头实际选型要看场景。6.2 另一种“另类”方案count计数除了tag另类循环队列还有一个常见流派增加一个计数器count记录当前元素个数。typedef struct { QElemType *base; int front; int rear; int count; // 当前元素个数 } CountQueue;判空count 0判满count MAXQSIZE。入队后count出队后count--。这样也能让数组全量利用而且求队列长度直接返回count连公式都省了。缺点是每个队列对象多占用一个计数变量并且所有操作都要多维护一次count。对比下来tag方案适合“只关心空/满不太需要实时长度”的场景count方案适合“频繁查长度希望判断条件更直观”的场景。如果只能选一种写到答卷上我建议熟练掌握tag方案因为习题3.12明确考查的就是它但两种思路都应该知道。6.3 工程中选哪种队列一点个人经验我在实际项目里写环形缓冲区时用得比较多的是count方案因为它让我一眼就能看到当前积压了多少数据配合日志、监控都方便。但看底层一些性能敏感模块的源码时也见过用tag或者直接用读写指针加掩码实现的锁-free队列。它们本质上都在解决同一个问题如何让环形结构知道自己是空还是满。回到这道习题我的体会是tag方案难不在代码而在理解“tag是front与rear重合时才有效”这个隐含约定。只要把入队后置满、出队后置空这两步和指针移动顺序绑定清楚后面的一切都是顺水推舟。如果你正在备考建议在纸上把长度为3的队列从空到满、再从满到空完整推演两遍再写代码。推演能过代码基本不会错推演卡住代码细节越抠越乱。这道题值得多花点时间因为它考察的不是死记硬背的结论而是你对循环队列状态转移过程的理解深度。
