最近在辅导几位刚入门数据结构的同学时发现大家对“队列”这个基础但至关重要的数据结构普遍存在理解上的断层。很多教程要么只讲抽象概念要么代码片段零散导致同学们自己动手实现时总是卡在“结构体怎么设计”、“循环队列判空判满为什么这么绕”这些具体环节。明明理解了“先进先出”的原理一写代码就漏洞百出。本文正是为了解决这个问题。我将以 C 语言为例手把手带你从零实现一个完整的队列涵盖结构体设计、初始化、判空、判满、入队、出队等所有核心操作。更重要的是我们会深入探讨循环队列这一工程中更常用的实现方式并彻底理清其判空与判满的经典难题。无论你是正在备考数据结构期末考试的学生还是希望夯实基础的开发者这篇近万字的实战笔记都能让你获得一套可直接复用的代码模板和清晰无误的底层逻辑。1. 队列核心概念与应用场景在开始写代码之前我们必须先统一思想队列到底是什么以及我们为什么需要它。队列Queue是一种操作受限的线性表。它只允许在表的一端进行插入操作在另一端进行删除操作。这就像现实生活中的排队后来的人排在队尾插入先来的人从队头离开删除。这种规则被称为先进先出First In First Out, FIFO。为什么需要队列想象一下如果没有队列多个任务同时请求同一个资源比如打印机、CPU时间片会怎样结果必然是混乱的。队列提供了一种公平、有序的调度机制。在计算机科学中队列的应用无处不在操作系统进程调度、消息传递、键盘缓冲区。网络通信数据包排队发送与接收。异步编程消息队列如 RabbitMQ, Kafka解耦生产者和消费者。算法树的层次遍历广度优先搜索 BFS、图的广度优先遍历。与栈的对比初学者常混淆队列和栈。记住一个简单的比喻栈是电梯后进先出LIFO队列是排队先进先出FIFO。栈只在同一端栈顶进行插入和删除而队列在两端进行。理解了队列的“道”接下来我们开始研究实现它的“术”。2. 环境准备与项目结构我们将使用最经典的 C 语言来实现队列这能让我们抛开高级语言库的封装直面数据结构的本质。你只需要一个能编译 C 语言的开发环境即可。操作系统Windows, macOS, Linux 均可。编译器GCC (MinGW)、Clang 或 Visual Studio 的 MSVC。代码编辑器VS Code, CLion, 甚至记事本都可以。项目结构为了清晰我们创建两个文件queue.h存放队列的结构体定义和所有函数的声明接口。queue.c存放所有队列操作函数的具体实现。main.c用于测试我们实现的队列。在开始编码前建议先在本地创建一个名为queue_demo的文件夹并在其中创建这三个文件。3. 队列的结构体设计与基础实现实现一个数据结构首先要设计它的“蓝图”在 C 语言中就是结构体。3.1 顺序队列的结构体设计队列可以用数组实现顺序存储也可以用链表实现链式存储。我们先从更直观的数组实现开始它被称为顺序队列。一个顺序队列需要跟踪哪些信息存储数据的数组一块连续的内存空间。队头索引front指向队列中第一个有效元素的位置。队尾索引rear指向队列中下一个可以插入元素的位置通常指向空位。队列的最大容量capacity数组能存储的最大元素个数。因此我们的结构体设计如下// 文件queue.h #ifndef QUEUE_H // 防止头文件被重复包含 #define QUEUE_H #define MAX_SIZE 100 // 预定义队列的最大容量 typedef int ElementType; // 定义队列中元素的类型这里以int为例可轻松改为其他类型 // 顺序队列的结构体 typedef struct { ElementType data[MAX_SIZE]; // 静态数组存储元素 int front; // 队头指针索引 int rear; // 队尾指针索引 } SeqQueue; // 函数声明 void InitQueue(SeqQueue *q); int IsEmpty(SeqQueue *q); int IsFull(SeqQueue *q); int EnQueue(SeqQueue *q, ElementType value); int DeQueue(SeqQueue *q, ElementType *value); void PrintQueue(SeqQueue *q); #endif // QUEUE_H关键点解析#ifndef...#define...#endif这是标准的头文件保护宏防止同一个源文件多次包含同一个头文件导致重复定义错误。MAX_SIZE使用宏定义容量方便后续修改。但这也是静态数组的局限性——创建后大小固定。ElementType使用typedef定义元素类型提高了代码的通用性。如果想存储字符或结构体只需修改这一处。front和rear的语义这是最容易出错的地方。我们约定front指向队头元素rear指向队尾元素的下一个位置即下一个入队位置。这个约定直接影响后续所有操作的实现。3.2 队列的初始化、判空与判满有了结构体接下来实现最基础的三个操作。// 文件queue.c #include stdio.h #include “queue.h” // 引入我们自己的头文件 // 1. 初始化队列 void InitQueue(SeqQueue *q) { if (q NULL) { printf(“错误队列指针为空\n”); return; } q-front 0; q-rear 0; // 注意此时 data 数组里的内容是未定义的垃圾值但队列逻辑为空 } // 2. 判断队列是否为空 int IsEmpty(SeqQueue *q) { if (q NULL) return 1; // 通常认为空指针也代表空队列或错误 return (q-front q-rear); // 队头等于队尾时队列为空 } // 3. 判断队列是否已满 int IsFull(SeqQueue *q) { if (q NULL) return 1; // 空指针视为已满防止非法操作 return (q-rear MAX_SIZE); // 队尾指针到达数组末尾 }代码逻辑剖析初始化将front和rear都置为 0表示队列起始为空。rear指向的位置就是下一个元素该放入的地方。判空根据我们的约定rear指向下一个插入位当front rear时队头和队尾重合队列中自然没有元素。判满当rear移动到数组最后一个位置的下一个即MAX_SIZE时表示数组的可用空间已用完。注意数组下标从 0 到MAX_SIZE-1所以rear MAX_SIZE是越界的代表已满。3.3 入队与出队操作现在实现队列的核心功能添加元素入队和移除元素出队。// 文件queue.c (续) // 4. 入队操作向队尾添加一个元素 int EnQueue(SeqQueue *q, ElementType value) { if (q NULL) { printf(“错误队列指针为空\n”); return 0; // 失败 } if (IsFull(q)) { printf(“警告队列已满无法入队元素 %d\n”, value); return 0; // 失败 } q-data[q-rear] value; // 将元素放入 rear 指向的位置 q-rear; // rear 指针后移指向下一个空位 return 1; // 成功 } // 5. 出队操作从队头移除一个元素并通过指针参数返回其值 int DeQueue(SeqQueue *q, ElementType *value) { if (q NULL || value NULL) { printf(“错误指针参数为空\n”); return 0; } if (IsEmpty(q)) { printf(“警告队列为空无法出队\n”); return 0; } *value q-data[q-front]; // 取出队头元素 q-front; // front 指针后移原队头元素逻辑上被移除 return 1; } // 6. 打印队列当前状态辅助函数便于调试 void PrintQueue(SeqQueue *q) { if (q NULL) return; if (IsEmpty(q)) { printf(“队列为空 []\n”); return; } printf(“队列内容 (front%d, rear%d): [”, q-front, q-rear); for (int i q-front; i q-rear; i) { printf(“%d”, q-data[i]); if (i q-rear - 1) printf(“, “); } printf(“]\n”); }操作流程详解入队EnQueue检查队列是否已满。将新元素value放入data[rear]。将rear指针加 1指向下一个空闲位置。出队DeQueue检查队列是否为空。将data[front]的值保存到*value中返回给调用者。将front指针加 1逻辑上丢弃了原队头元素。这里隐藏着一个严重问题让我们写个main.c测试一下// 文件main.c #include stdio.h #include “queue.h” int main() { SeqQueue q; ElementType val; InitQueue(q); printf(“初始化后队列是否空 %s\n”, IsEmpty(q) ? “是” : “否”); // 入队 5 个元素 for (int i 1; i 5; i) { EnQueue(q, i * 10); } PrintQueue(q); // 出队 3 个元素 for (int i 0; i 3; i) { if (DeQueue(q, val)) { printf(“出队元素%d\n”, val); } } PrintQueue(q); // 再尝试入队直到‘满’ printf(“\n尝试填满队列...\n”); while (EnQueue(q, 99)) { // 循环入队直到失败 } printf(“队列已满 rear %d\n”, q.rear); PrintQueue(q); // 此时 front3, rearMAX_SIZE return 0; }如果你将MAX_SIZE设为 10 并运行会发现一个现象在执行了多次出队操作后front指针已经移到了数组中间比如位置 3。虽然数组data[0],data[1],data[2]的位置已经空闲但由于rear已经到达MAX_SIZE程序仍然会判断队列为“满”拒绝新的入队请求。这就是顺序队列的“假溢出”问题数组前端有可用空间但后端已到边界导致空间无法被充分利用。为了解决这个问题我们必须引入循环队列。4. 循环队列解决假溢出的优雅方案循环队列的核心思想是把线性数组想象成一个首尾相接的环。当指针移动到数组末尾时不是停止而是绕回到数组开头。4.1 循环队列的结构体调整结构体本身不需要改变但我们对front和rear指针的操作逻辑以及判满判空的判断条件需要彻底改变。首先在queue.h中我们可能需要一个更清晰的方式来表示容量但结构体不变。// 文件queue.h (循环队列版本结构体可不变但理解变了) typedef struct { ElementType data[MAX_SIZE]; int front; int rear; } SeqQueue; // 现在我们把它当作循环队列来实现4.2 循环队列的判空与判满这是循环队列最核心也最容易混淆的部分。有几种常见的判断方法我们采用最通用的一种牺牲一个数组单元。规则队空条件front rear队满条件(rear 1) % MAX_SIZE front为什么牺牲一个单元如果不用牺牲单元的方法当队列满时rear和front也相等这就和队列空的条件冲突了无法区分。牺牲一个存储单元换来判断逻辑的清晰和简单在大多数情况下是值得的。这意味着一个声明大小为MAX_SIZE的循环队列实际最多只能存储MAX_SIZE - 1个元素。让我们更新queue.c中的函数// 文件queue.c (循环队列版本) #include stdio.h #include “queue.h” // 初始化不变 void InitQueue(SeqQueue *q) { if (q NULL) return; q-front 0; q-rear 0; } // 循环队列-判空条件不变 int IsEmpty(SeqQueue *q) { if (q NULL) return 1; return (q-front q-rear); } // 循环队列-判满新条件 int IsFull(SeqQueue *q) { if (q NULL) return 1; // 关键rear的下一个位置是front则队满 return ((q-rear 1) % MAX_SIZE q-front); } // 循环队列-入队 int EnQueue(SeqQueue *q, ElementType value) { if (q NULL) return 0; if (IsFull(q)) { printf(“队列已满入队%d失败\n”, value); return 0; } q-data[q-rear] value; // 1. 存值 q-rear (q-rear 1) % MAX_SIZE; // 2. rear循环后移 return 1; } // 循环队列-出队 int DeQueue(SeqQueue *q, ElementType *value) { if (q NULL || value NULL) return 0; if (IsEmpty(q)) { printf(“队列为空出队失败\n”); return 0; } *value q-data[q-front]; // 1. 取值 q-front (q-front 1) % MAX_SIZE; // 2. front循环后移 return 1; } // 获取队列当前元素个数 int GetQueueLength(SeqQueue *q) { if (q NULL) return 0; // 计算元素个数考虑循环 return (q-rear - q-front MAX_SIZE) % MAX_SIZE; } // 打印循环队列 (需要更复杂的逻辑) void PrintQueue(SeqQueue *q) { if (q NULL) return; if (IsEmpty(q)) { printf(“队列为空 []\n”); return; } printf(“队列内容 (front%d, rear%d, len%d): [”, q-front, q-rear, GetQueueLength(q)); int i q-front; // 从front开始遍历直到遇到rear while (i ! q-rear) { printf(“%d”, q-data[i]); i (i 1) % MAX_SIZE; // 循环递增 if (i ! q-rear) printf(“, “); } printf(“]\n”); }核心变化解读指针移动rear (rear 1) % MAX_SIZE和front (front 1) % MAX_SIZE。取模运算%是实现“循环”的关键。当指针在末尾MAX_SIZE-1时加1再取模就回到了 0。判满逻辑(rear 1) % MAX_SIZE front。检查rear的下一个位置是不是front如果是说明再入队就会覆盖front即队头此时队列已满。计算长度(rear - front MAX_SIZE) % MAX_SIZE。因为rear可能小于front循环了一圈所以需要加上MAX_SIZE再取模来得到正确的正数差值。4.3 循环队列实战测试让我们用新的main.c来验证循环队列解决了“假溢出”问题。// 文件main.c (测试循环队列) #include stdio.h #include “queue.h” int main() { SeqQueue q; ElementType val; int capacity MAX_SIZE; // 假设 MAX_SIZE 5 以便观察 printf(“ 循环队列测试 \n”); InitQueue(q); printf(“初始队列空%s 满%s\n”, IsEmpty(q)?“是”:“否”, IsFull(q)?“是”:“否”); // 入队直到队满 printf(“\n1. 入队元素直到队满理论最大容量 %d:\n”, MAX_SIZE-1); for (int i 1; i MAX_SIZE; i) { // 尝试入队 MAX_SIZE 次 if (EnQueue(q, i*10)) { printf(“ 入队 %d 成功。”, i*10); PrintQueue(q); } else { printf(“ 入队 %d 失败预期中队列应已满。\n”, i*10); } } // 此时队列应满有 MAX_SIZE-1 个元素 printf(“队列长度: %d\n”, GetQueueLength(q)); // 出队两个元素释放空间 printf(“\n2. 出队两个元素:\n”); DeQueue(q, val); printf(“ 出队: %d\n”, val); DeQueue(q, val); printf(“ 出队: %d\n”, val); PrintQueue(q); // 再次入队验证空间可循环使用 printf(“\n3. 再次入队新元素验证循环利用:\n”); EnQueue(q, 100); printf(“ 入队 100\n”); EnQueue(q, 200); printf(“ 入队 200\n”); PrintQueue(q); // 此时再入队一个应该会满 if (!EnQueue(q, 300)) { printf(“ 入队 300 失败队列已满正确。\n”); } // 复杂遍历测试 printf(“\n4. 复杂操作交替入队出队\n”); while (!IsEmpty(q)) { DeQueue(q, val); printf(“ 出队: %d, “, val); PrintQueue(q); } printf(“最终队列为空。\n”); return 0; }将MAX_SIZE定义为 5 并运行此程序你会清晰地看到队列最多容纳 4 个元素牺牲一个单元。出队后数组前端的空间被释放。新的元素入队时rear指针会从数组末尾“绕回”到开头填充之前释放的空间。完美解决了“假溢出”问题。5. 常见问题与深度排查在实现和使用队列时下面这些“坑”几乎每个初学者都会遇到。5.1 指针移动与取模运算问题为什么是(rear 1) % MAX_SIZE而不是rear解答rear是线性移动到达数组末尾后无法回头。取模运算%实现了“环形”移动。当rear为MAX_SIZE-1最后一个下标时(MAX_SIZE-1 1) % MAX_SIZE 0指针回到了起点。陷阱MAX_SIZE必须是队列数组的实际长度。如果你定义data[100]那么MAX_SIZE应该是 100取模运算才正确。5.2 判空判满条件混淆这是循环队列最经典的错误来源。我们总结一个对比表条件线性队列 (有假溢出)循环队列 (牺牲单元法)说明初始化front rear 0front rear 0一致队空front rearfront rear一致队满rear MAX_SIZE(rear 1) % MAX_SIZE front本质区别指针后移rear,frontrear (rear1)%MAX_SIZEfront (front1)%MAX_SIZE本质区别记忆口诀空则相等满则追尾。队列空时头尾指针重合队列满时尾指针再走一步就会撞上等于头指针。5.3 元素类型与内存管理我们的示例使用typedef int ElementType。在实际项目中你可能需要存储更复杂的类型。存储结构体直接修改ElementType的定义即可。注意入队时是值拷贝。存储指针如果存储的是malloc分配的内存地址你需要在出队或销毁队列时负责释放这些内存否则会造成内存泄漏。这通常意味着你需要实现一个DestroyQueue函数。// 示例存储字符串指针 typedef char* ElementType; // 存储动态字符串 int EnQueueString(SeqQueue *q, const char* str) { char *new_str strdup(str); // 复制字符串 if (new_str NULL) return 0; if (!EnQueue(q, new_str)) { // 调用通用的EnQueue free(new_str); return 0; } return 1; } int DeQueueString(SeqQueue *q, char **str) { char *temp; if (!DeQueue(q, temp)) return 0; // 调用通用的DeQueue *str temp; return 1; } // 必须有一个函数来清理队列中剩余的所有字符串 void ClearQueue(SeqQueue *q) { char *str; while (DeQueueString(q, str)) { free(str); } }5.4 多线程环境下的安全问题我们实现的队列是非线程安全的。如果多个线程同时调用EnQueue或DeQueue对front/rear和data数组的读写会产生竞争条件导致数据错乱或指针异常。解决方案互斥锁Mutex在操作队列前加锁操作后解锁。这是最简单的方法但会影响性能。无锁队列使用 CASCompare-And-Swap等原子操作实现性能高但实现复杂。C11 标准提供了stdatomic.h库可用于实现。// 简单的互斥锁包装示例伪代码需链接 pthread 库 #include pthread.h typedef struct { SeqQueue queue; pthread_mutex_t lock; } ThreadSafeQueue; void InitTSQueue(ThreadSafeQueue *tsq) { InitQueue(tsq-queue); pthread_mutex_init(tsq-lock, NULL); } int EnQueueTS(ThreadSafeQueue *tsq, ElementType value) { pthread_mutex_lock(tsq-lock); int result EnQueue(tsq-queue, value); pthread_mutex_unlock(tsq-lock); return result; } // ... 其他操作类似6. 工程实践与扩展建议掌握了基础的循环队列后我们可以思考如何让它更健壮、更通用。6.1 动态扩容队列静态数组的固定大小是硬伤。我们可以用动态数组malloc/realloc实现一个能自动扩容的队列。设计思路结构体中用指针ElementType *data代替静态数组。初始化时动态分配初始容量。在EnQueue发现队列满时不是返回失败而是 a. 分配一个更大的新数组通常是原容量的 1.5 或 2 倍。 b. 将旧数组中的有效元素从front到rear-1考虑循环复制到新数组的头部并重置front0,rear元素个数。 c. 释放旧数组将指针指向新数组。// 动态循环队列结构体草图 typedef struct { ElementType *data; // 指向动态数组的指针 int capacity; // 数组总容量 int front; int rear; } DynSeqQueue; int EnQueueDyn(DynSeqQueue *q, ElementType value) { if (IsFull(q)) { // 扩容逻辑 int new_capacity q-capacity * 2; // 翻倍 ElementType *new_data (ElementType*)malloc(new_capacity * sizeof(ElementType)); if (!new_data) return 0; // 分配失败 // 复制元素... // 更新指针和容量... } // ... 正常入队逻辑 }6.2 泛型队列C 语言没有模板但我们可以使用void*指针来实现泛型存储任意类型数据的地址。typedef struct { void **data; // 存储 void* 指针的数组 int capacity; int front; int rear; size_t elem_size; // 每个元素的大小用于拷贝 } GenericQueue; // 入队时需要传入元素地址和大小 int EnQueueGeneric(GenericQueue *q, const void *elem, size_t size) { if (IsFull(q)) return 0; // 为元素分配内存并拷贝 void *new_elem malloc(size); if (!new_elem) return 0; memcpy(new_elem, elem, size); q-data[q-rear] new_elem; q-rear (q-rear 1) % q-capacity; return 1; } // 出队时需要用户提供缓冲区来接收数据 int DeQueueGeneric(GenericQueue *q, void *buffer, size_t size) { if (IsEmpty(q)) return 0; void *elem q-data[q-front]; memcpy(buffer, elem, size); free(elem); // 释放队列内部分配的内存 q-front (q-front 1) % q-capacity; return 1; }注意泛型队列的内存管理更复杂使用者必须清楚何时分配、何时释放。6.3 链式队列简介除了顺序存储数组队列也可以用链表实现称为链队列。它本质上是一个带有头尾指针的单链表。优点理论上可以无限扩容直到内存耗尽没有“假溢出”和“牺牲单元”的问题。缺点每个元素都需要额外的指针空间内存访问不如数组连续缓存不友好。// 链队列节点 typedef struct QueueNode { ElementType data; struct QueueNode *next; } QueueNode; // 链队列结构体包含头尾指针 typedef struct { QueueNode *front; // 指向头节点非数据节点或直接指向第一个数据节点 QueueNode *rear; // 指向最后一个节点 } LinkedQueue;链队列的入队就是在链表尾部插入节点出队就是删除链表头部节点。判空条件是front NULL或front rear取决于实现。7. 从理论到应用队列在算法中的身影学习数据结构最终是为了解决问题。队列的一个经典算法应用是广度优先搜索BFS。BFS 常用于寻找最短路径在无权图中、层次遍历树等场景。其核心就是使用队列来管理待访问的节点。BFS 伪代码框架1. 将起始节点入队并标记为已访问。 2. while (队列非空) { 3. 当前节点 出队(); 4. 处理当前节点例如打印。 5. for (当前节点的每个未访问的邻居节点) { 6. 标记邻居为已访问 7. 将邻居节点入队 8. } 9. }这个框架清晰体现了队列“先进先出”的特性先被发现的节点先被处理从而保证了搜索是按“层次”或“距离”由近及远展开的。纸上得来终觉浅绝知此事要躬行。队列作为数据结构中的基石其思想渗透在计算机世界的各个角落。从操作系统的任务调度到网络框架的请求缓冲再到日常算法解题理解并熟练实现一个健壮的队列是每个程序员的基本功。建议你合上文章后亲自在 IDE 里敲一遍所有代码尝试修改MAX_SIZE观察不同操作下front和rear的变化甚至挑战实现动态扩容或链式队列。当你不再需要死记硬背“判满公式”而是能自然推导出它时才算真正掌握了循环队列的精髓。
最近在辅导几位刚入门数据结构的同学时发现大家对“队列”这个基础但至关重要的数据结构普遍存在理解上的断层。很多教程要么只讲抽象概念要么代码片段零散导致同学们自己动手实现时总是卡在“结构体怎么设计”、“循环队列判空判满为什么这么绕”这些具体环节。明明理解了“先进先出”的原理一写代码就漏洞百出。本文正是为了解决这个问题。我将以 C 语言为例手把手带你从零实现一个完整的队列涵盖结构体设计、初始化、判空、判满、入队、出队等所有核心操作。更重要的是我们会深入探讨循环队列这一工程中更常用的实现方式并彻底理清其判空与判满的经典难题。无论你是正在备考数据结构期末考试的学生还是希望夯实基础的开发者这篇近万字的实战笔记都能让你获得一套可直接复用的代码模板和清晰无误的底层逻辑。1. 队列核心概念与应用场景在开始写代码之前我们必须先统一思想队列到底是什么以及我们为什么需要它。队列Queue是一种操作受限的线性表。它只允许在表的一端进行插入操作在另一端进行删除操作。这就像现实生活中的排队后来的人排在队尾插入先来的人从队头离开删除。这种规则被称为先进先出First In First Out, FIFO。为什么需要队列想象一下如果没有队列多个任务同时请求同一个资源比如打印机、CPU时间片会怎样结果必然是混乱的。队列提供了一种公平、有序的调度机制。在计算机科学中队列的应用无处不在操作系统进程调度、消息传递、键盘缓冲区。网络通信数据包排队发送与接收。异步编程消息队列如 RabbitMQ, Kafka解耦生产者和消费者。算法树的层次遍历广度优先搜索 BFS、图的广度优先遍历。与栈的对比初学者常混淆队列和栈。记住一个简单的比喻栈是电梯后进先出LIFO队列是排队先进先出FIFO。栈只在同一端栈顶进行插入和删除而队列在两端进行。理解了队列的“道”接下来我们开始研究实现它的“术”。2. 环境准备与项目结构我们将使用最经典的 C 语言来实现队列这能让我们抛开高级语言库的封装直面数据结构的本质。你只需要一个能编译 C 语言的开发环境即可。操作系统Windows, macOS, Linux 均可。编译器GCC (MinGW)、Clang 或 Visual Studio 的 MSVC。代码编辑器VS Code, CLion, 甚至记事本都可以。项目结构为了清晰我们创建两个文件queue.h存放队列的结构体定义和所有函数的声明接口。queue.c存放所有队列操作函数的具体实现。main.c用于测试我们实现的队列。在开始编码前建议先在本地创建一个名为queue_demo的文件夹并在其中创建这三个文件。3. 队列的结构体设计与基础实现实现一个数据结构首先要设计它的“蓝图”在 C 语言中就是结构体。3.1 顺序队列的结构体设计队列可以用数组实现顺序存储也可以用链表实现链式存储。我们先从更直观的数组实现开始它被称为顺序队列。一个顺序队列需要跟踪哪些信息存储数据的数组一块连续的内存空间。队头索引front指向队列中第一个有效元素的位置。队尾索引rear指向队列中下一个可以插入元素的位置通常指向空位。队列的最大容量capacity数组能存储的最大元素个数。因此我们的结构体设计如下// 文件queue.h #ifndef QUEUE_H // 防止头文件被重复包含 #define QUEUE_H #define MAX_SIZE 100 // 预定义队列的最大容量 typedef int ElementType; // 定义队列中元素的类型这里以int为例可轻松改为其他类型 // 顺序队列的结构体 typedef struct { ElementType data[MAX_SIZE]; // 静态数组存储元素 int front; // 队头指针索引 int rear; // 队尾指针索引 } SeqQueue; // 函数声明 void InitQueue(SeqQueue *q); int IsEmpty(SeqQueue *q); int IsFull(SeqQueue *q); int EnQueue(SeqQueue *q, ElementType value); int DeQueue(SeqQueue *q, ElementType *value); void PrintQueue(SeqQueue *q); #endif // QUEUE_H关键点解析#ifndef...#define...#endif这是标准的头文件保护宏防止同一个源文件多次包含同一个头文件导致重复定义错误。MAX_SIZE使用宏定义容量方便后续修改。但这也是静态数组的局限性——创建后大小固定。ElementType使用typedef定义元素类型提高了代码的通用性。如果想存储字符或结构体只需修改这一处。front和rear的语义这是最容易出错的地方。我们约定front指向队头元素rear指向队尾元素的下一个位置即下一个入队位置。这个约定直接影响后续所有操作的实现。3.2 队列的初始化、判空与判满有了结构体接下来实现最基础的三个操作。// 文件queue.c #include stdio.h #include “queue.h” // 引入我们自己的头文件 // 1. 初始化队列 void InitQueue(SeqQueue *q) { if (q NULL) { printf(“错误队列指针为空\n”); return; } q-front 0; q-rear 0; // 注意此时 data 数组里的内容是未定义的垃圾值但队列逻辑为空 } // 2. 判断队列是否为空 int IsEmpty(SeqQueue *q) { if (q NULL) return 1; // 通常认为空指针也代表空队列或错误 return (q-front q-rear); // 队头等于队尾时队列为空 } // 3. 判断队列是否已满 int IsFull(SeqQueue *q) { if (q NULL) return 1; // 空指针视为已满防止非法操作 return (q-rear MAX_SIZE); // 队尾指针到达数组末尾 }代码逻辑剖析初始化将front和rear都置为 0表示队列起始为空。rear指向的位置就是下一个元素该放入的地方。判空根据我们的约定rear指向下一个插入位当front rear时队头和队尾重合队列中自然没有元素。判满当rear移动到数组最后一个位置的下一个即MAX_SIZE时表示数组的可用空间已用完。注意数组下标从 0 到MAX_SIZE-1所以rear MAX_SIZE是越界的代表已满。3.3 入队与出队操作现在实现队列的核心功能添加元素入队和移除元素出队。// 文件queue.c (续) // 4. 入队操作向队尾添加一个元素 int EnQueue(SeqQueue *q, ElementType value) { if (q NULL) { printf(“错误队列指针为空\n”); return 0; // 失败 } if (IsFull(q)) { printf(“警告队列已满无法入队元素 %d\n”, value); return 0; // 失败 } q-data[q-rear] value; // 将元素放入 rear 指向的位置 q-rear; // rear 指针后移指向下一个空位 return 1; // 成功 } // 5. 出队操作从队头移除一个元素并通过指针参数返回其值 int DeQueue(SeqQueue *q, ElementType *value) { if (q NULL || value NULL) { printf(“错误指针参数为空\n”); return 0; } if (IsEmpty(q)) { printf(“警告队列为空无法出队\n”); return 0; } *value q-data[q-front]; // 取出队头元素 q-front; // front 指针后移原队头元素逻辑上被移除 return 1; } // 6. 打印队列当前状态辅助函数便于调试 void PrintQueue(SeqQueue *q) { if (q NULL) return; if (IsEmpty(q)) { printf(“队列为空 []\n”); return; } printf(“队列内容 (front%d, rear%d): [”, q-front, q-rear); for (int i q-front; i q-rear; i) { printf(“%d”, q-data[i]); if (i q-rear - 1) printf(“, “); } printf(“]\n”); }操作流程详解入队EnQueue检查队列是否已满。将新元素value放入data[rear]。将rear指针加 1指向下一个空闲位置。出队DeQueue检查队列是否为空。将data[front]的值保存到*value中返回给调用者。将front指针加 1逻辑上丢弃了原队头元素。这里隐藏着一个严重问题让我们写个main.c测试一下// 文件main.c #include stdio.h #include “queue.h” int main() { SeqQueue q; ElementType val; InitQueue(q); printf(“初始化后队列是否空 %s\n”, IsEmpty(q) ? “是” : “否”); // 入队 5 个元素 for (int i 1; i 5; i) { EnQueue(q, i * 10); } PrintQueue(q); // 出队 3 个元素 for (int i 0; i 3; i) { if (DeQueue(q, val)) { printf(“出队元素%d\n”, val); } } PrintQueue(q); // 再尝试入队直到‘满’ printf(“\n尝试填满队列...\n”); while (EnQueue(q, 99)) { // 循环入队直到失败 } printf(“队列已满 rear %d\n”, q.rear); PrintQueue(q); // 此时 front3, rearMAX_SIZE return 0; }如果你将MAX_SIZE设为 10 并运行会发现一个现象在执行了多次出队操作后front指针已经移到了数组中间比如位置 3。虽然数组data[0],data[1],data[2]的位置已经空闲但由于rear已经到达MAX_SIZE程序仍然会判断队列为“满”拒绝新的入队请求。这就是顺序队列的“假溢出”问题数组前端有可用空间但后端已到边界导致空间无法被充分利用。为了解决这个问题我们必须引入循环队列。4. 循环队列解决假溢出的优雅方案循环队列的核心思想是把线性数组想象成一个首尾相接的环。当指针移动到数组末尾时不是停止而是绕回到数组开头。4.1 循环队列的结构体调整结构体本身不需要改变但我们对front和rear指针的操作逻辑以及判满判空的判断条件需要彻底改变。首先在queue.h中我们可能需要一个更清晰的方式来表示容量但结构体不变。// 文件queue.h (循环队列版本结构体可不变但理解变了) typedef struct { ElementType data[MAX_SIZE]; int front; int rear; } SeqQueue; // 现在我们把它当作循环队列来实现4.2 循环队列的判空与判满这是循环队列最核心也最容易混淆的部分。有几种常见的判断方法我们采用最通用的一种牺牲一个数组单元。规则队空条件front rear队满条件(rear 1) % MAX_SIZE front为什么牺牲一个单元如果不用牺牲单元的方法当队列满时rear和front也相等这就和队列空的条件冲突了无法区分。牺牲一个存储单元换来判断逻辑的清晰和简单在大多数情况下是值得的。这意味着一个声明大小为MAX_SIZE的循环队列实际最多只能存储MAX_SIZE - 1个元素。让我们更新queue.c中的函数// 文件queue.c (循环队列版本) #include stdio.h #include “queue.h” // 初始化不变 void InitQueue(SeqQueue *q) { if (q NULL) return; q-front 0; q-rear 0; } // 循环队列-判空条件不变 int IsEmpty(SeqQueue *q) { if (q NULL) return 1; return (q-front q-rear); } // 循环队列-判满新条件 int IsFull(SeqQueue *q) { if (q NULL) return 1; // 关键rear的下一个位置是front则队满 return ((q-rear 1) % MAX_SIZE q-front); } // 循环队列-入队 int EnQueue(SeqQueue *q, ElementType value) { if (q NULL) return 0; if (IsFull(q)) { printf(“队列已满入队%d失败\n”, value); return 0; } q-data[q-rear] value; // 1. 存值 q-rear (q-rear 1) % MAX_SIZE; // 2. rear循环后移 return 1; } // 循环队列-出队 int DeQueue(SeqQueue *q, ElementType *value) { if (q NULL || value NULL) return 0; if (IsEmpty(q)) { printf(“队列为空出队失败\n”); return 0; } *value q-data[q-front]; // 1. 取值 q-front (q-front 1) % MAX_SIZE; // 2. front循环后移 return 1; } // 获取队列当前元素个数 int GetQueueLength(SeqQueue *q) { if (q NULL) return 0; // 计算元素个数考虑循环 return (q-rear - q-front MAX_SIZE) % MAX_SIZE; } // 打印循环队列 (需要更复杂的逻辑) void PrintQueue(SeqQueue *q) { if (q NULL) return; if (IsEmpty(q)) { printf(“队列为空 []\n”); return; } printf(“队列内容 (front%d, rear%d, len%d): [”, q-front, q-rear, GetQueueLength(q)); int i q-front; // 从front开始遍历直到遇到rear while (i ! q-rear) { printf(“%d”, q-data[i]); i (i 1) % MAX_SIZE; // 循环递增 if (i ! q-rear) printf(“, “); } printf(“]\n”); }核心变化解读指针移动rear (rear 1) % MAX_SIZE和front (front 1) % MAX_SIZE。取模运算%是实现“循环”的关键。当指针在末尾MAX_SIZE-1时加1再取模就回到了 0。判满逻辑(rear 1) % MAX_SIZE front。检查rear的下一个位置是不是front如果是说明再入队就会覆盖front即队头此时队列已满。计算长度(rear - front MAX_SIZE) % MAX_SIZE。因为rear可能小于front循环了一圈所以需要加上MAX_SIZE再取模来得到正确的正数差值。4.3 循环队列实战测试让我们用新的main.c来验证循环队列解决了“假溢出”问题。// 文件main.c (测试循环队列) #include stdio.h #include “queue.h” int main() { SeqQueue q; ElementType val; int capacity MAX_SIZE; // 假设 MAX_SIZE 5 以便观察 printf(“ 循环队列测试 \n”); InitQueue(q); printf(“初始队列空%s 满%s\n”, IsEmpty(q)?“是”:“否”, IsFull(q)?“是”:“否”); // 入队直到队满 printf(“\n1. 入队元素直到队满理论最大容量 %d:\n”, MAX_SIZE-1); for (int i 1; i MAX_SIZE; i) { // 尝试入队 MAX_SIZE 次 if (EnQueue(q, i*10)) { printf(“ 入队 %d 成功。”, i*10); PrintQueue(q); } else { printf(“ 入队 %d 失败预期中队列应已满。\n”, i*10); } } // 此时队列应满有 MAX_SIZE-1 个元素 printf(“队列长度: %d\n”, GetQueueLength(q)); // 出队两个元素释放空间 printf(“\n2. 出队两个元素:\n”); DeQueue(q, val); printf(“ 出队: %d\n”, val); DeQueue(q, val); printf(“ 出队: %d\n”, val); PrintQueue(q); // 再次入队验证空间可循环使用 printf(“\n3. 再次入队新元素验证循环利用:\n”); EnQueue(q, 100); printf(“ 入队 100\n”); EnQueue(q, 200); printf(“ 入队 200\n”); PrintQueue(q); // 此时再入队一个应该会满 if (!EnQueue(q, 300)) { printf(“ 入队 300 失败队列已满正确。\n”); } // 复杂遍历测试 printf(“\n4. 复杂操作交替入队出队\n”); while (!IsEmpty(q)) { DeQueue(q, val); printf(“ 出队: %d, “, val); PrintQueue(q); } printf(“最终队列为空。\n”); return 0; }将MAX_SIZE定义为 5 并运行此程序你会清晰地看到队列最多容纳 4 个元素牺牲一个单元。出队后数组前端的空间被释放。新的元素入队时rear指针会从数组末尾“绕回”到开头填充之前释放的空间。完美解决了“假溢出”问题。5. 常见问题与深度排查在实现和使用队列时下面这些“坑”几乎每个初学者都会遇到。5.1 指针移动与取模运算问题为什么是(rear 1) % MAX_SIZE而不是rear解答rear是线性移动到达数组末尾后无法回头。取模运算%实现了“环形”移动。当rear为MAX_SIZE-1最后一个下标时(MAX_SIZE-1 1) % MAX_SIZE 0指针回到了起点。陷阱MAX_SIZE必须是队列数组的实际长度。如果你定义data[100]那么MAX_SIZE应该是 100取模运算才正确。5.2 判空判满条件混淆这是循环队列最经典的错误来源。我们总结一个对比表条件线性队列 (有假溢出)循环队列 (牺牲单元法)说明初始化front rear 0front rear 0一致队空front rearfront rear一致队满rear MAX_SIZE(rear 1) % MAX_SIZE front本质区别指针后移rear,frontrear (rear1)%MAX_SIZEfront (front1)%MAX_SIZE本质区别记忆口诀空则相等满则追尾。队列空时头尾指针重合队列满时尾指针再走一步就会撞上等于头指针。5.3 元素类型与内存管理我们的示例使用typedef int ElementType。在实际项目中你可能需要存储更复杂的类型。存储结构体直接修改ElementType的定义即可。注意入队时是值拷贝。存储指针如果存储的是malloc分配的内存地址你需要在出队或销毁队列时负责释放这些内存否则会造成内存泄漏。这通常意味着你需要实现一个DestroyQueue函数。// 示例存储字符串指针 typedef char* ElementType; // 存储动态字符串 int EnQueueString(SeqQueue *q, const char* str) { char *new_str strdup(str); // 复制字符串 if (new_str NULL) return 0; if (!EnQueue(q, new_str)) { // 调用通用的EnQueue free(new_str); return 0; } return 1; } int DeQueueString(SeqQueue *q, char **str) { char *temp; if (!DeQueue(q, temp)) return 0; // 调用通用的DeQueue *str temp; return 1; } // 必须有一个函数来清理队列中剩余的所有字符串 void ClearQueue(SeqQueue *q) { char *str; while (DeQueueString(q, str)) { free(str); } }5.4 多线程环境下的安全问题我们实现的队列是非线程安全的。如果多个线程同时调用EnQueue或DeQueue对front/rear和data数组的读写会产生竞争条件导致数据错乱或指针异常。解决方案互斥锁Mutex在操作队列前加锁操作后解锁。这是最简单的方法但会影响性能。无锁队列使用 CASCompare-And-Swap等原子操作实现性能高但实现复杂。C11 标准提供了stdatomic.h库可用于实现。// 简单的互斥锁包装示例伪代码需链接 pthread 库 #include pthread.h typedef struct { SeqQueue queue; pthread_mutex_t lock; } ThreadSafeQueue; void InitTSQueue(ThreadSafeQueue *tsq) { InitQueue(tsq-queue); pthread_mutex_init(tsq-lock, NULL); } int EnQueueTS(ThreadSafeQueue *tsq, ElementType value) { pthread_mutex_lock(tsq-lock); int result EnQueue(tsq-queue, value); pthread_mutex_unlock(tsq-lock); return result; } // ... 其他操作类似6. 工程实践与扩展建议掌握了基础的循环队列后我们可以思考如何让它更健壮、更通用。6.1 动态扩容队列静态数组的固定大小是硬伤。我们可以用动态数组malloc/realloc实现一个能自动扩容的队列。设计思路结构体中用指针ElementType *data代替静态数组。初始化时动态分配初始容量。在EnQueue发现队列满时不是返回失败而是 a. 分配一个更大的新数组通常是原容量的 1.5 或 2 倍。 b. 将旧数组中的有效元素从front到rear-1考虑循环复制到新数组的头部并重置front0,rear元素个数。 c. 释放旧数组将指针指向新数组。// 动态循环队列结构体草图 typedef struct { ElementType *data; // 指向动态数组的指针 int capacity; // 数组总容量 int front; int rear; } DynSeqQueue; int EnQueueDyn(DynSeqQueue *q, ElementType value) { if (IsFull(q)) { // 扩容逻辑 int new_capacity q-capacity * 2; // 翻倍 ElementType *new_data (ElementType*)malloc(new_capacity * sizeof(ElementType)); if (!new_data) return 0; // 分配失败 // 复制元素... // 更新指针和容量... } // ... 正常入队逻辑 }6.2 泛型队列C 语言没有模板但我们可以使用void*指针来实现泛型存储任意类型数据的地址。typedef struct { void **data; // 存储 void* 指针的数组 int capacity; int front; int rear; size_t elem_size; // 每个元素的大小用于拷贝 } GenericQueue; // 入队时需要传入元素地址和大小 int EnQueueGeneric(GenericQueue *q, const void *elem, size_t size) { if (IsFull(q)) return 0; // 为元素分配内存并拷贝 void *new_elem malloc(size); if (!new_elem) return 0; memcpy(new_elem, elem, size); q-data[q-rear] new_elem; q-rear (q-rear 1) % q-capacity; return 1; } // 出队时需要用户提供缓冲区来接收数据 int DeQueueGeneric(GenericQueue *q, void *buffer, size_t size) { if (IsEmpty(q)) return 0; void *elem q-data[q-front]; memcpy(buffer, elem, size); free(elem); // 释放队列内部分配的内存 q-front (q-front 1) % q-capacity; return 1; }注意泛型队列的内存管理更复杂使用者必须清楚何时分配、何时释放。6.3 链式队列简介除了顺序存储数组队列也可以用链表实现称为链队列。它本质上是一个带有头尾指针的单链表。优点理论上可以无限扩容直到内存耗尽没有“假溢出”和“牺牲单元”的问题。缺点每个元素都需要额外的指针空间内存访问不如数组连续缓存不友好。// 链队列节点 typedef struct QueueNode { ElementType data; struct QueueNode *next; } QueueNode; // 链队列结构体包含头尾指针 typedef struct { QueueNode *front; // 指向头节点非数据节点或直接指向第一个数据节点 QueueNode *rear; // 指向最后一个节点 } LinkedQueue;链队列的入队就是在链表尾部插入节点出队就是删除链表头部节点。判空条件是front NULL或front rear取决于实现。7. 从理论到应用队列在算法中的身影学习数据结构最终是为了解决问题。队列的一个经典算法应用是广度优先搜索BFS。BFS 常用于寻找最短路径在无权图中、层次遍历树等场景。其核心就是使用队列来管理待访问的节点。BFS 伪代码框架1. 将起始节点入队并标记为已访问。 2. while (队列非空) { 3. 当前节点 出队(); 4. 处理当前节点例如打印。 5. for (当前节点的每个未访问的邻居节点) { 6. 标记邻居为已访问 7. 将邻居节点入队 8. } 9. }这个框架清晰体现了队列“先进先出”的特性先被发现的节点先被处理从而保证了搜索是按“层次”或“距离”由近及远展开的。纸上得来终觉浅绝知此事要躬行。队列作为数据结构中的基石其思想渗透在计算机世界的各个角落。从操作系统的任务调度到网络框架的请求缓冲再到日常算法解题理解并熟练实现一个健壮的队列是每个程序员的基本功。建议你合上文章后亲自在 IDE 里敲一遍所有代码尝试修改MAX_SIZE观察不同操作下front和rear的变化甚至挑战实现动态扩容或链式队列。当你不再需要死记硬背“判满公式”而是能自然推导出它时才算真正掌握了循环队列的精髓。
平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测)
