一.队列的概念与结构1.概念概念只允许在⼀端进⾏插⼊数据操作在另⼀端进⾏删除数据操作的特殊线性表队列具有先进先出FIFO(First In First Out)。⼊队列进⾏插⼊操作的⼀端称为队尾出队列进⾏删除操作的⼀端称为队头2.结构队列底层结构选型队列也可以数组和链表的结构实现使⽤链表的结构实现更优⼀些因为如果使⽤数组的结构出队列在数组头上出数据效率会⽐较低。a.队列的顺序存储结构队列的顺序存储结构通常使用数组来实现一般用队头指针phead和队尾指针ptail来标记队头和队尾的位置。入队在队尾插入新元素只需要修改队尾指针不需要移动任何元素时间复杂度为 O(1)。出队删除队头元素后需要将所有剩余元素整体往前移动一位时间复杂度为 O(N)。这种普通数组队列出队效率较低因此实际中更常用循环队列来优化让出队也达到 O(1)。b.队列的链表存储结构队列的链式存储结构使用链表来实现定义两个指针队头指针phead指向第一个节点队尾指针ptail指向尾节点。空队列时phead 和 ptail 都指向 NULL。入队尾插在链表尾部插入新节点时间复杂度为 O(1)。出队头删删除链表头部节点时间复杂度为 O(1)。链式队列不需要像普通数组那样移动数据入队和出队效率都较高但每个节点需要额外的指针域内存开销稍大。二.队列的实现用数组实现队列时如果采用普通数组的方式出队操作需要先删除队头数据再将剩余所有元素整体往前移动一位时间复杂度为 O(N)。当数据量较大时这个开销是很明显的效率太低不适合实际使用。相比之下选择用单向链表来实现队列更合适。链式队列通过队头指针phead进行头删通过队尾指针ptail进行尾插入队和出队操作都只需要修改指针的指向不需要移动任何数据时间复杂度都是 O(1)效率很高。至于双向链表虽然也能实现队列但队列只需要在一端插入尾插、另一端删除头删单向链表已经能够完美支持这两个操作。双向链表多维护了一个 prev 指针在这个场景下发挥不出什么作用反而增加了内存开销和代码复杂度所以用单向链表就足够了。1.创建文件在实现队列之前首先需要创建以下三个文件test.c—— 主函数文件用于测试队列的各个接口功能是否正常Queue.c—— 队列接口函数的具体实现文件包含初始化、入队、出队、获取队头元素等操作Queue.h—— 队列的头文件包含队列的类型定义、接口函数声明以及所需引用的头文件采用这种模块化的文件组织方式可以将队列的实现细节与测试代码分离提高代码的可读性和可维护性也便于后续复用和扩展。其中 Queue.h 负责声明Queue.c 负责实现test.c 负责验证。2.Queue.h 头文件代码// Queue.h // 链式结构表示队列 #pragma once #include stdio.h #include stdbool.h // bool 类型 #include assert.h // assert 断言 #include stdlib.h // malloc、free typedef int QDataType; // 类型重命名队列中元素类型先假设为 int // 队列节点结构 typedef struct QueueNode { struct QueueNode* next; // 指向下一个节点的指针 QDataType data; // 节点中存储的数据 } QueueNode; // 队列的链式结构 typedef struct Queue { QueueNode* head; // 队头指针指向第一个节点 QueueNode* tail; // 队尾指针指向最后一个节点 int size; // 队列中有效元素的个数可选方便统计 } Queue; // 初始化队列 void QueueInit(Queue* pq); // 销毁队列 void QueueDestroy(Queue* pq); // 队尾入队列尾插 void QueuePush(Queue* pq, QDataType data); // 队头出队列头删 void QueuePop(Queue* pq); // 获取队列头部元素 QDataType QueueFront(Queue* pq); // 获取队列尾部元素 QDataType QueueBack(Queue* pq); // 获取队列中有效元素个数 int QueueSize(Queue* pq); // 检测队列是否为空如果为空返回 true如果非空返回 false bool QueueEmpty(Queue* pq);注意这两点size成员不是必须的但加上后可以在 O(1) 时间内获取队列元素个数否则需要遍历链表统计时间复杂度为 O(N)队头指针head用于出队操作头删队尾指针tail用于入队操作尾插两者配合使用入队和出队的时间复杂度都是 O(1)三.Queue.c 中各个接口函数的实现1.初始化队列// 初始化队列 void QueueInit(Queue* pq) { assert(pq); // 断言防止传入空指针 pq-head pq-tail NULL; // 头尾指针都置空 }解析初始化就是把队头和队尾指针都置成 NULL表示这是一个空队列。加上 assert 是为了保证传入的指针是有效的。2.销毁队列// 销毁队列 void QueueDestroy(Queue* pq) { assert(pq); // 断言防止传入空指针 QueueNode* cur pq-head; // 从队头开始遍历 while (cur) { QueueNode* next cur-next; // 保存下一个节点的地址 free(cur); // 释放当前节点 cur next; // 移到下一个节点 } pq-head pq-tail NULL; // 所有节点释放完后头尾指针置空 }解析销毁队列需要把链表中所有节点都释放掉防止内存泄漏。从队头开始一个一个往后遍历每次释放当前节点之前先保存下一个节点的地址不然释放后就找不到下一个了。全部释放完之后把 head 和 tail 置空。3.队尾入队列尾插// 队尾入队列尾插 void QueuePush(Queue* pq, QDataType x) { assert(pq); // 断言防止传入空指针 // 动态申请一个新节点 QueueNode* newnode (QueueNode*)malloc(sizeof(QueueNode)); if (newnode NULL) // 检查内存申请是否成功 { printf(malloc fail\n); exit(-1); } newnode-data x; // 存入数据 newnode-next NULL; // 新节点的 next 置空作为新的尾节点 // 如果队列为空头尾指针都指向新节点 if (pq-head NULL) { pq-head pq-tail newnode; } else // 队列不为空链接到当前尾节点后面 { pq-tail-next newnode; pq-tail newnode; // 更新尾指针 } }解析入队就是在链表尾部插入一个新节点。先 malloc 一个新节点把数据存进去next 置空。然后分两种情况如果队列为空头尾指针都指向这个新节点如果队列不为空就把当前尾节点的 next 指向新节点然后更新尾指针。这样入队操作的时间复杂度是 O(1)。4.队头出队列头删// 队头出队列头删 void QueuePop(Queue* pq) { assert(pq); // 断言防止传入空指针 // 暴力处理方式推荐 assert(!QueueEmpty(pq)); // 断言确保队列不为空空队列不能出队 QueueNode* next pq-head-next; // 记录第二个节点的地址 free(pq-head); // 释放队头节点 pq-head next; // 更新队头指针 // 如果队列中只有一个节点删除后队列为空尾指针也要置空 if (pq-head NULL) { pq-tail NULL; } }// 写法二也是正确的 void QueuePop(Queue* pq) { assert(pq); // 断言防止传入空指针 assert(!QueueEmpty(pq)); // 断言确保队列不为空 if (pq-head-next NULL) // 队列中只有一个节点 { free(pq-head); pq-head pq-tail NULL; // 头尾指针都置空 } else // 队列中有多个节点 { QueueNode* next pq-head-next; // 记录第二个节点的地址 free(pq-head); // 释放队头节点 pq-head next; // 更新队头指针 } }解析出队就是删除链表的头节点。写法一先保存第二个节点的地址然后释放头节点再更新头指针。如果删完发现链表空了就把尾指针也置空。写法二则是分两种情况处理如果只有一个节点释放后头尾指针都置空如果多个节点就正常头删。两种写法都行写法一代码更简洁一些。关键点在于链表只有一个节点时要单独处理否则 tail 会变成野指针。5.获取队列头部元素// 获取队列头部元素 QDataType QueueFront(Queue* pq) { assert(pq); // 断言防止传入空指针 assert(!QueueEmpty(pq)); // 断言确保队列不为空 return pq-head-data; // 返回队头节点的数据 }解析这个函数只获取队头元素的值不删除它。直接返回 head-data 就行了。用 assert 保证队列不为空否则访问空指针会出问题。6.获取队列尾部元素// 获取队列尾部元素 QDataType QueueBack(Queue* pq) { assert(pq); // 断言防止传入空指针 assert(!QueueEmpty(pq)); // 断言确保队列不为空 return pq-tail-data; // 返回队尾节点的数据 }解析和上面类似只是换成了返回队尾元素。因为有 tail 指针直接 tail-data 就拿到了时间复杂度 O(1)。如果没有 tail 指针就得遍历到链表尾部那就变成 O(N) 了。这也是为什么我们要在队列结构体里同时维护 head 和 tail 两个指针。7.获取队列中有效元素个数// 获取队列中有效元素个数 int QueueSize(Queue* pq) { assert(pq); // 断言防止传入空指针 int n 0; QueueNode* cur pq-head; // 从队头开始遍历 while (cur) { n; cur cur-next; } return n; }解析这个函数返回队列中有效元素的个数。从队头开始遍历整个链表每经过一个节点计数加一直到遍历完所有节点。时间复杂度是 O(N)。如果频繁调用这个接口获取元素个数每次都要遍历整个链表效率就太低了最直观的改进办法就是在队列结构体里加一个 size 成员变量入队时 size出队时 size--这样获取元素个数直接返回 size 就行时间复杂度 O(1)。8.检测队列是否为空// 检测队列是否为空如果为空返回 true如果不为空返回 false bool QueueEmpty(Queue* pq) { assert(pq); // 断言防止传入空指针 return pq-head NULL; // 头指针为空表示队列为空 }解析判断队列是否为空只需要看队头指针是不是 NULL。如果 head 为 NULL说明队列里没有节点返回 true否则返回 false。这里只判断 head 就够了因为队列为空时 head 一定为 NULLtail 也为 NULL但反过来如果 head 不为空队列肯定不为空。四.整合代码Queue.h 头文件// Queue.h // 链式结构表示队列 #pragma once #include stdio.h #include stdbool.h // bool 类型 #include assert.h // assert 断言 #include stdlib.h // malloc、free typedef int QDataType; // 类型重命名队列中元素类型先假设为 int // 队列节点结构 typedef struct QueueNode { struct QueueNode* next; // 指向下一个节点的指针 QDataType data; // 节点中存储的数据 } QueueNode; // 队列的链式结构 typedef struct Queue { QueueNode* head; // 队头指针指向第一个节点 QueueNode* tail; // 队尾指针指向最后一个节点 int size; // 队列中有效元素的个数方便统计 } Queue; // 初始化队列 void QueueInit(Queue* pq); // 销毁队列 void QueueDestroy(Queue* pq); // 队尾入队列尾插 void QueuePush(Queue* pq, QDataType data); // 队头出队列头删 void QueuePop(Queue* pq); // 获取队列头部元素 QDataType QueueFront(Queue* pq); // 获取队列尾部元素 QDataType QueueBack(Queue* pq); // 获取队列中有效元素个数 int QueueSize(Queue* pq); // 检测队列是否为空如果为空返回 true如果非空返回 false bool QueueEmpty(Queue* pq);Queue.c 源文件// Queue.c // 队列接口函数的实现 #include Queue.h // 1、初始化队列 void QueueInit(Queue* pq) { assert(pq); // 断言防止传入空指针 pq-head pq-tail NULL; // 头尾指针都置空 pq-size 0; // 元素个数归零 } // 2、销毁队列 void QueueDestroy(Queue* pq) { assert(pq); // 断言防止传入空指针 QueueNode* cur pq-head; // 从队头开始遍历 while (cur) { QueueNode* next cur-next; // 保存下一个节点的地址 free(cur); // 释放当前节点 cur next; // 移到下一个节点 } pq-head pq-tail NULL; // 所有节点释放完后头尾指针置空 pq-size 0; // 元素个数归零 } // 3、队尾入队列尾插 void QueuePush(Queue* pq, QDataType x) { assert(pq); // 断言防止传入空指针 // 动态申请一个新节点 QueueNode* newnode (QueueNode*)malloc(sizeof(QueueNode)); if (newnode NULL) // 检查内存申请是否成功 { printf(malloc fail\n); exit(-1); } newnode-data x; // 存入数据 newnode-next NULL; // 新节点的 next 置空作为新的尾节点 // 如果队列为空头尾指针都指向新节点 if (pq-head NULL) { pq-head pq-tail newnode; } else // 队列不为空链接到当前尾节点后面 { pq-tail-next newnode; pq-tail newnode; // 更新尾指针 } pq-size; // 元素个数加一 } // 4、队头出队列头删 void QueuePop(Queue* pq) { assert(pq); // 断言防止传入空指针 assert(!QueueEmpty(pq)); // 断言确保队列不为空 QueueNode* next pq-head-next; // 保存第二个节点的地址 free(pq-head); // 释放队头节点 pq-head next; // 更新队头指针 // 如果队列中只剩一个节点删除后队列为空尾指针也要置空 if (pq-head NULL) { pq-tail NULL; } pq-size--; // 元素个数减一 } // 5、获取队列头部元素 QDataType QueueFront(Queue* pq) { assert(pq); // 断言防止传入空指针 assert(!QueueEmpty(pq)); // 断言确保队列不为空 return pq-head-data; // 返回队头节点的数据 } // 6、获取队列尾部元素 QDataType QueueBack(Queue* pq) { assert(pq); // 断言防止传入空指针 assert(!QueueEmpty(pq)); // 断言确保队列不为空 return pq-tail-data; // 返回队尾节点的数据 } // 7、获取队列中有效元素个数 int QueueSize(Queue* pq) { assert(pq); // 断言防止传入空指针 return pq-size; // 直接返回 size时间复杂度 O(1) } // 8、检测队列是否为空 bool QueueEmpty(Queue* pq) { assert(pq); // 断言防止传入空指针 return pq-head NULL; // 头指针为空表示队列为空 }test.c 测试文件// test.c // 主函数及功能测试 —— 覆盖所有接口函数 #include Queue.h // 测试1覆盖接口 —— QueueInit、QueuePush、QueuePop、QueueFront、QueueSize、QueueEmpty、QueueDestroy void TestQueue1() { Queue q; QueueInit(q); // 测试初始化 printf(入队1 2 3 4 5\n); QueuePush(q, 1); // 测试入队尾插 QueuePush(q, 2); QueuePush(q, 3); QueuePush(q, 4); QueuePush(q, 5); printf(队列中元素个数%d\n, QueueSize(q)); // 测试获取元素个数 printf(出队顺序); while (!QueueEmpty(q)) // 测试判空 { printf(%d , QueueFront(q)); // 测试获取队头元素 QueuePop(q); // 测试出队头删 } printf(\n); printf(出队后元素个数%d\n, QueueSize(q)); // 测试获取元素个数 printf(\n); QueueDestroy(q); // 测试销毁队列 } // 测试2覆盖接口 —— QueueInit、QueuePush、QueueFront、QueueBack、QueueDestroy void TestQueue2() { Queue q; QueueInit(q); // 测试初始化 QueuePush(q, 10); // 测试入队 QueuePush(q, 20); QueuePush(q, 30); printf(队头元素%d\n, QueueFront(q)); // 测试获取队头 printf(队尾元素%d\n, QueueBack(q)); // 测试获取队尾 printf(\n); QueueDestroy(q); // 测试销毁 } // 测试3覆盖接口 —— QueueInit、QueuePush、QueuePop、QueueFront、QueueSize、QueueEmpty、QueueDestroy // 额外验证多个队列同时存在时互不干扰 void TestQueue3() { Queue q1, q2; QueueInit(q1); // 测试初始化 QueueInit(q2); // 测试初始化 QueuePush(q1, 1); // 测试入队 QueuePush(q1, 2); QueuePush(q1, 3); QueuePush(q2, 10); // 测试入队 QueuePush(q2, 20); QueuePush(q2, 30); QueuePush(q2, 40); printf(q1 元素个数%d\n, QueueSize(q1)); // 测试获取元素个数 printf(q2 元素个数%d\n, QueueSize(q2)); printf(q1 出队); while (!QueueEmpty(q1)) // 测试判空 { printf(%d , QueueFront(q1)); // 测试获取队头 QueuePop(q1); // 测试出队 } printf(\n); printf(q2 出队); while (!QueueEmpty(q2)) { printf(%d , QueueFront(q2)); QueuePop(q2); } printf(\n); printf(\n); QueueDestroy(q1); // 测试销毁 QueueDestroy(q2); } int main() { TestQueue1(); // 初始话、入队、出队、获取队头、获取元素个数、判空、销毁 TestQueue2(); // 初始化、入队、获取队头、获取队尾、销毁 TestQueue3(); // 初始化、入队、出队、获取队头、获取元素个数、判空、销毁并验证多队列独立性 return 0; }五.测试功能1.测试1基本入队出队功能2.测试2获取队头和队尾元素3.测试3多队列独立运行六.拓展学习循环队列的概念与结构1.概念实际中还有⼀种特殊的队列叫循环队列环形队列⾸尾相连成环环形队列可以使⽤数组实现也可以使⽤循环链表实现。循环队列的好处是出队的时候不用挪动数据只需移动队头指针就行了入队和出队的时间复杂度都是 O(1)。解决了普通数组队列出队要挪动数据、效率低的问题。2.结构3.空循环队列队列为空时队头指针front和队尾指针rear指向同一个位置即front rear初始状态就是空的这时候 front 和 rear 都指向数组的第一个位置。4.满的循环队列两种判断方式方式一牺牲一个存储单元当(rear 1) % capacity front时认为队列已满。这种方式相当于把最后一个位置空出来不用专门用来区分队空和队满。判断队空front rear判断队满(rear 1) % capacity front这里用取模运算就是为了让 rear 加 1 之后能回到数组开头形成循环的效果。方式二增加 size 变量在结构体里加一个 size 变量入队时 size出队时 size--。判断队满直接看 size capacity 就行了。好处是不浪费空间但要多维护一个变量。思考为什么方式一中 rear 位置不存储数据如果所有位置都存了数据那么 front rear 的时候你分不清这是队空还是队满。因为队列为空时 front rear队列满了之后如果继续插入rear 绕了一圈又回到 front 的位置还是 front rear这就矛盾了。所以为了能区分这两种情况我们常用的做法是故意浪费一个位置不存数据。当 rear 的下一个位置是 front 时就说明队列满了不能再插了。小小总结方便大家理解循环队列说白了就是数组围成一个圈通过取模运算让指针转起来。核心就是要搞清楚怎么判断空和满。一般用方式一比较多虽然浪费一个空间但逻辑清晰写起来也方便。方式二更节约空间但要多维护一个 size 变量看个人习惯选择。用表格让两种方式对比方式队空条件队满条件是否浪费空间实现难度牺牲一个位置front rear(rear1) % k front浪费一个简单增加 size 变量size 0size capacity不浪费稍微复杂一点5.循环队列的小实验#include stdio.h #include stdbool.h #define CAPACITY 5 typedef struct { int a[CAPACITY]; int front; int rear; } MyCircularQueue; void init(MyCircularQueue* q) { q-front 0; q-rear 0; } bool empty(MyCircularQueue* q) { return q-front q-rear; } bool full(MyCircularQueue* q) { return (q-rear 1) % CAPACITY q-front; } void push(MyCircularQueue* q, int val) { if (full(q)) { printf(队列满了%d 入队失败\n, val); return; } q-a[q-rear] val; q-rear (q-rear 1) % CAPACITY; printf(%d 入队成功rear %d\n, val, q-rear); } void pop(MyCircularQueue* q) { if (empty(q)) { printf(队列空了出队失败\n); return; } printf(%d 出队成功front %d\n, q-a[q-front], q-front); q-front (q-front 1) % CAPACITY; } void print(MyCircularQueue* q) { printf(front %d, rear %d, q-front, q-rear); int i q-front; while (i ! q-rear) { printf(%d , q-a[i]); i (i 1) % CAPACITY; } printf(\n); } int main() { MyCircularQueue q; init(q); printf(循环队列小实验\n); printf(容量 %d实际存 %d 个\n\n, CAPACITY, CAPACITY - 1); push(q, 1); push(q, 2); push(q, 3); push(q, 4); print(q); push(q, 5); print(q); pop(q); pop(q); print(q); push(q, 5); push(q, 6); print(q); while (!empty(q)) { pop(q); } printf(全部出队后); print(q); return 0; }运行结果如下代码解析#include stdio.h #include stdbool.h #define CAPACITY 5 // 数组容量 // 队列结构体 typedef struct { int a[CAPACITY]; // 数组存放数据 int front; // 队头下标 int rear; // 队尾下标 } MyCircularQueue;这里定义了一个循环队列front 指向队头rear 指向队尾的下一个位置。void init(MyCircularQueue* q) { q-front 0; q-rear 0; }初始状态front 和 rear 都指向 0队列为空。bool empty(MyCircularQueue* q) { return q-front q-rear; }front 和 rear 相遇说明队列里没有元素。bool full(MyCircularQueue* q) { return (q-rear 1) % CAPACITY q-front; }rear 的下一个位置是 front说明队列满了所以浪费一个位置不用。void push(MyCircularQueue* q, int val) { if (full(q)) { printf(队列满了%d 入队失败\n, val); return; } q-a[q-rear] val; // 在 rear 位置放数据 q-rear (q-rear 1) % CAPACITY; // rear 往后移取模实现循环 printf(%d 入队成功rear %d\n, val, q-rear); }入队就是在 rear 位置放数据然后 rear 往后走一步。取模让 rear 能从末尾回到开头。void pop(MyCircularQueue* q) { if (empty(q)) { printf(队列空了出队失败\n); return; } printf(%d 出队成功front %d\n, q-a[q-front], q-front); q-front (q-front 1) % CAPACITY; // front 往后移取模实现循环 }出队就是 front 往后走一步逻辑上把队头删掉了数据不用真的清除。实验说明这个实验演示了什么用 5 个空间的数组实现队列实际只能存 4 个数据通过 front 和 rear 两个指针来标记队头和队尾。关键现象入队 1 2 3 4 后rear 4队列满了5 入队失败。然后出队 1 和 2front 变成 2这时候数组前面下标 0 和 1 的位置就空出来了。接着入队 5rear 从 4 变成 0入队 6rear 从 0 变成 1。说明 rear 通过取模运算回到了数组开头把前面空出来的位置重新利用上了。得出结论循环队列解决了普通数组队列“出队后前面位置空着却用不上”的问题空间可以反复使用而且出队不用挪数据效率高。核心就是靠% CAPACITY取模运算让指针在数组里转圈。