企业官网建设流程全解析

很多人复习数据结构时，卡住的地方往往不是红黑树，也不是图的最短路径，而是一个看起来不起眼的习题——习题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方案非常适合“空间紧张、要求全部格子可用”的场景，也是不少教材在“队列”章节留下的经典扩展题。

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 = 3，rear = 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、出队三次”。

重点看入队D那一步：入队前front = 1，rear = 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 != rear，tag保持原值就行。这里的原值可能是0也可能是1，但反正不会参与判空判满，留着不影响正确性。当然，如果你想让状态更清晰，也可以在每次入队/出队后统一根据当前状态刷新tag，但效果其实一样。

5.3 入队出队时指针移动顺序反了

入队时应该是“先写base[rear]，再移动rear”；出队时应该是“先取base[front]，再移动front”。反过来的话，第一次操作就可能出错：

入队如果先把rear加1，再写入，第一个元素写到了下标1而不是下标0，front依然为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赋0，front == 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的队列从空到满、再从满到空完整推演两遍，再写代码。推演能过，代码基本不会错；推演卡住，代码细节越抠越乱。这道题值得多花点时间，因为它考察的不是死记硬背的结论，而是你对循环队列状态转移过程的理解深度。