一、队列的介绍① 队列 一种线性存储结构允许在一端队尾插入数据在另一端队头删除数据。② 队列主要特点插入操作入队在队尾进行删除操作出队在队头进行先进先出FIFOFirst In First Out③ 用处一般用于缓存数据二、队列的两种存储结构2.1 顺序队列基于数组实现2.1.1普通顺序队列线性队列① 底层结构采用线性存储结构一段连续的内存空间数组需要预分配内存空间。② 核心属性通过两个指针/下标进行管理——head队头和 tail队尾。③ 操作逻辑入队队尾先存储数据再移动 tail 指针出队队头先取出数据再移动 head 指针④ 缺点存在“假溢出”问题——当 tail 到达数组末尾时即使 head 之前的位置已空闲队尾已满但队头还有空位因出队操作仅移动 head 而不调整数据队列仍无法继续入队。⑤ 解决方案采用循环队列将数组逻辑上首尾相连。当 tail 到达数组末端时自动跳转至数组头部继续利用空闲空间从而提升存储效率。2.1.2循环顺序队列① 循环队列是顺序队列的一种具体实现方案目的是解决普通顺序队列的“假溢出”问题。② 在循环队列中head和tail的约定head指向队头元素的位置tail指向队尾元素的下一个位置③ 特点逻辑上将数组首尾相连通过取模运算%让指针循环移动。入队存入数据tail (tail 1) %容量出队取出数据head (head 1) % 容量空队列队头和队尾在同一位置满队列队列少存储一个数据当队尾1跟上队头④ 两种判空/判满实现方式实现方式判空条件判满条件空间利用率牺牲单元法head tail tail 1 %​​ 容量​​​​​head浪费 1 个空间计数器法size 0size 容量100% 利用2.2 链式队列基于链表实现① 底层结构采用单链表实现内存空间非连续分配。② 核心属性维护两个指针——phead指向队头元素节点和 ptail指向队尾元素节点。③ 操作逻辑入队操作在链表尾部追加新节点并更新 ptail 指针指向新节点出队操作移除链表头部节点并将 phead 指针后移指向下一节点④ 优点支持动态扩容避免假溢出现象入队/出队操作时间复杂度均为 O(1)⑤ 缺点每个节点需额外存储指针存在内存开销三、链式队列实现3.1 链式队列的对象和节点声明typedef int DataType_t; //声明链式队列节点 typedef struct node { DataType_t data; struct node *pnext; }LQNode_t; //声明链式队列对象 typedef struct linkqueue { LQNode_t *phead; LQNode_t *ptail; int clen; }LQueue_t;3.2 创建链式队列对象//创建链式队列对象 LQueue_t *create_linkqueue() { //在堆区动态分配一个 LQueue_t 类型结构体的内存空间 LQueue_t *pque malloc(sizeof(LQueue_t)); if (NULL pque) //检查 malloc 是否成功 { printf(malloc error\n); return NULL; } pque-phead NULL; //头指针置空表示队列无节点 pque-ptail NULL; //尾指针置空表示队列无节点 pque-clen 0;//队列长度为0 return pque; }3.3 创建链式队列节点//创建链式队列节点 LQNode_t *create_node(DataType_t data) { LQNode_t *pnode malloc(sizeof(LQNode_t)); if (NULL pnode) { printf(malloc error\n); return NULL; } //将传入的数据存储到节点的 data 字段 pnode-data data; //值传递数据被复制到节点中 pnode-pnext NULL; //将下一个节点指针置 NULL return pnode; }3.4 判断链式队列为空//链式队列判空 int is_empty_linkqueue(LQueue_t *pque) { //返回 1真队列为空 返回 0假队列非空 return NULL pque-phead; }3.5 链式队列入队尾插空队列状态头指针和尾指针均指向同一节点非空队列状态将新节点插入当前尾节点之后并将尾指针移至新节点采用尾插法//链式队列入队在队尾插入新元素 int push_linkqueue(LQueue_t *pque, DataType_t data) { LQNode_t *pnode create_node(data); //调用 create_node 创建新节点 if (NULL pnode) { return -1; } if (is_empty_linkqueue(pque)) //判空并插入 { //如果是空队列头尾指针都指向同一个节点 pque-phead pnode; // 头指针指向新节点 pque-ptail pnode; // 尾指针指向新节点 } else //非空队列 { pque-ptail-pnext pnode; // 当前尾节点指向新节点 pque-ptail pnode; // 更新尾指针 } pque-clen; //更新队列长度 return 0; }3.6 链式队列出队头删队列中有多个数据节点删除头节点后需要正确更新头指针队列中只有一个数据节点删除后头指针变为NULL说明队列已经空了此时需要将尾指针也置为NULL//从链式队列头部移除一个节点并将节点中的数据通过指针参数返回。 int pop_linkqueue(LQueue_t *pque, DataType_t *pdata) { if (is_empty_linkqueue(pque)) //判断队列是否为空 { return -1; } LQNode_t *ptmp pque-phead; //用临时指针 ptmp 保存队头节点的地址 pque-phead ptmp-pnext;//更新头指针将头指针指向第二个节点 //如果删除后头指针变为 NULL说明队列已经空了 if (NULL pque-phead) { pque-ptail NULL; //将尾指针也置为 NULL } if (pdata ! NULL) { //如果 pdata 不为 NULL将节点数据复制到 pdata 指向的内存 //如果调用者不需要数据可以传入 NULL只删除不出队 *pdata ptmp-data; } free(ptmp); //释放已移除节点的内存防止内存泄漏 ptmp NULL; // 置空防止野指针 pque-clen--; //更新队列长度 return 0; }3.7 遍历链式队列//遍历链式队列用于打印队列中所有元素 void show_linkqueue(LQueue_t *pque) { //创建临时指针 ptmp指向队头节点遍历的起点 LQNode_t *ptmp pque-phead; while (ptmp ! NULL) //未到达队尾 { printf(%d , ptmp-data); ptmp ptmp-pnext; } printf(\n); }3.8 获取链式队列队头元素的数据//获取链式队列队头元素的数据但不删除该节点只读操作 int get_linkqueue_head(LQueue_t *pque, DataType_t *pdata) { if (is_empty_linkqueue(pque)) //判断队列是否为空 { return -1; } if (pdata ! NULL) { //如果 pdata 不为 NULL将队头节点的数据复制到 pdata 指向的内存 *pdata pque-phead-data; } return 0; }3.9 销毁链式队列使用一级指针只修改了局部变量调用者的指针不变//完全销毁一个链式队列释放所有节点和队列结构体的内存并将指针置空 void destroy_linkqueue(LQueue_t **ppque) //二级指针指向队列指针的指针 { while (!is_empty_linkqueue(*ppque)) //队列不为空 { //每次删除一个节点直到队列为空传入 NULL 表示不返回数据只删除 pop_linkqueue(*ppque, NULL); //反复调用 pop_linkqueue 删除队头节点 } free(*ppque); //释放队列控制结构体LQueue_t占用的内存 *ppque NULL; //将调用者的队列指针置为 NULL } //调用 destroy_linkqueue(pque);3.10 附件代码① linkqueue.h#ifndef __LINKQUEUE_H__ #define __LINKQUEUE_H__ typedef int DataType_t; typedef struct node { DataType_t data; struct node *pnext; }LQNode_t; typedef struct linkqueue { LQNode_t *phead; LQNode_t *ptail; int clen; }LQueue_t; extern LQueue_t *create_linkqueue(); extern LQNode_t *create_node(DataType_t data); extern int is_empty_linkqueue(LQueue_t *pque); extern int push_linkqueue(LQueue_t *pque, DataType_t data); extern void show_linkqueue(LQueue_t *pque); extern int pop_linkqueue(LQueue_t *pque, DataType_t *pdata); extern int get_linkqueue_head(LQueue_t *pque, DataType_t *pdata); extern void destroy_linkqueue(LQueue_t **ppque); #endif② linkqueue.c#include linkqueue.h #include stdio.h #include stdlib.h LQueue_t *create_linkqueue() { LQueue_t *pque malloc(sizeof(LQueue_t)); if (NULL pque) { printf(malloc error\n); return NULL; } pque-phead NULL; pque-ptail NULL; pque-clen 0; return pque; } LQNode_t *create_node(DataType_t data) { LQNode_t *pnode malloc(sizeof(LQNode_t)); if (NULL pnode) { printf(malloc error\n); return NULL; } pnode-data data; pnode-pnext NULL; return pnode; } int is_empty_linkqueue(LQueue_t *pque) { return NULL pque-phead; } int push_linkqueue(LQueue_t *pque, DataType_t data) { LQNode_t *pnode create_node(data); if (NULL pnode) { return -1; } if (is_empty_linkqueue(pque)) { pque-phead pnode; pque-ptail pnode; } else { pque-ptail-pnext pnode; pque-ptail pnode; } pque-clen; return 0; } void show_linkqueue(LQueue_t *pque) { LQNode_t *ptmp pque-phead; while (ptmp ! NULL) { printf(%d , ptmp-data); ptmp ptmp-pnext; } printf(\n); } int pop_linkqueue(LQueue_t *pque, DataType_t *pdata) { if (is_empty_linkqueue(pque)) { return -1; } LQNode_t *ptmp pque-phead; pque-phead ptmp-pnext; if (NULL pque-phead) { pque-ptail NULL; } if (pdata ! NULL) { *pdata ptmp-data; } free(ptmp); pque-clen--; return 0; } int get_linkqueue_head(LQueue_t *pque, DataType_t *pdata) { if (is_empty_linkqueue(pque)) { return -1; } if (pdata ! NULL) { *pdata pque-phead-data; } return 0; } void destroy_linkqueue(LQueue_t **ppque) { while (!is_empty_linkqueue(*ppque)) { pop_linkqueue(*ppque, NULL); } free(*ppque); *ppque NULL; }③ main.c#include linkqueue.h #include stdio.h int main(int argc, const char *argv[]) { LQueue_t *pque NULL; DataType_t data; pque create_linkqueue(); if (NULL pque) { return -1; } push_linkqueue(pque, 1); push_linkqueue(pque, 2); push_linkqueue(pque, 3); push_linkqueue(pque, 4); push_linkqueue(pque, 5); show_linkqueue(pque); int ret pop_linkqueue(pque, data); if (0 ret) { printf(pop data : %d\n, data); } show_linkqueue(pque); ret get_linkqueue_head(pque, data); if (0 ret) { printf(head data : %d\n, data); } destroy_linkqueue(pque); return 0; }四、循环队列实现4.1 循环队列的对象声明//声明循环队列的对象 typedef int DataType_t; //将 int 类型重命名为 DataType_t typedef struct sque { DataType_t *pbase; // 指向动态数组的指针存储数据 int head; // 队头索引 int tail; // 队尾索引 }SQueue_t;4.2 创建循环队列对象//创建一个循环队列分配结构体内存和存储数据的内存并初始化为空队列 SQueue_t *create_sysqueue() { SQueue_t *psque malloc(sizeof(SQueue_t));//在堆区为队列结构体分配内存 if (NULL psque) { printf(malloc error\n); return NULL; } //为数据存储区分配动态数组 psque-pbase malloc(sizeof(DataType_t) * MAX_QUEUE_LEN); if (NULL psque-pbase) { printf(malloc error\n); return NULL; } psque-head 0; //队头索引初始化为 0 psque-tail 0; //队尾索引初始化为 0 return psque; } //分配数据区后 栈psque → 0x1000 堆0x1000 [SQueue_t结构体] ├─ pbase: 0x2000 ├─ head: 0 └─ tail: 0 堆0x2000 [数据区] ← 可存储 MAX_QUEUE_LEN 个元素4.3 循环队列判满//判断顺序循环队列是否已满返回1表示已满0表示未满。 int is_full_sysqueue(SQueue_t *psque) { //在循环队列中当尾指针的下一个位置等于头指针时表示队列已满 if (((psque-tail 1) % MAX_QUEUE_LEN) psque-head) { return 1; } return 0; }4.4 循环队列判空//判断顺序循环队列是否为空返回1表示为空0表示非空。 int is_empty_sysqueue(SQueue_t *psque) { //当头指针和尾指针重合时表示队列中没有元素 if (psque-head psque-tail) { return 1; } return 0; }4.5 循环队列入队//向顺序循环队列中插入一个元素入队操作如果队列已满则返回错误 int push_sysqueue(SQueue_t *psque, DataType_t data) { if (is_full_sysqueue(psque)) //判断队列是否已满防止数据覆盖或缓冲区溢出 { return -1; } //使用 tail 作为索引将数据存入数组tail 指向当前队尾的下一个位置空闲位置 psque-pbase[psque-tail] data; //更新尾指针循环 psque-tail (psque-tail1) % MAX_QUEUE_LEN; return 0; } //psque-tail (psque-tail1) % MAX_QUEUE_LEN; 核心操作tail 后移一位 (tail 1) % MAX_QUEUE_LEN实现循环 当 tail 到达数组末尾时自动回到开头 // 1.初始状态 空队列容量为8 索引: 0 1 2 3 4 5 6 7 [ ][ ][ ][ ][ ][ ][ ][ ] ↑ head0, tail0 2.入队元素10 pbase[tail] 10; // pbase[0] 10 tail (01) % 8; // tail 1 索引: 0 1 2 3 4 5 6 7 [10][ ][ ][ ][ ][ ][ ][ ] ↑ ↑ head0 tail14.6 循环队列出队//从顺序循环队列头部移除一个元素并通过指针参数返回其数据。 int pop_sysqueue(SQueue_t *psque, DataType_t *pdata) { //判断队列是否为空防止对空队列进行操作 if (is_empty_sysqueue(psque)) { return -1; } if (pdata ! NULL) //检查输出指针是否有效 { //如果 pdata 不为 NULL将队头数据复制到 pdata 指向的内存 *pdata psque-pbase[psque-head]; } //更新头指针循环 psque-head (psque-head 1) % MAX_QUEUE_LEN; return 0; } //psque-head (psque-head 1) % MAX_QUEUE_LEN; 核心操作head 后移一位 (head 1) % MAX_QUEUE_LEN实现循环 当 head 到达数组末尾时自动回到开头 1.初始状态3个元素容量为8 索引: 0 1 2 3 4 5 6 7 [10][20][30][ ][ ][ ][ ][ ] ↑ ↑ head0 tail3 2.出队元素10 // 如果 pdata ! NULL返回 pbase[0] 10 head (0 1) % 8; // head 1 索引: 0 1 2 3 4 5 6 7 [10][20][30][ ][ ][ ][ ][ ] ↑ ↑ head1 tail3 (逻辑上10已被删除)4.7 遍历循环队列//遍历顺序循环队列从头到尾打印所有有效元素。 void show_sysqueue(SQueue_t *psque) { for (int i psque-head; i ! psque-tail; i (i1)%MAX_QUEUE_LEN) { printf(%d , psque-pbase[i]); } printf(\n); } 初始化i psque-head - 从队头开始 循环条件i ! psque-tail - 未到达队尾 迭代i (i1) % MAX_QUEUE_LEN - 循环后移4.8 清空循环队列//清空顺序循环队列使队列回到初始空状态。 void clear_sysqueue(SQueue_t *psque) { psque-head psque-tail 0; }4.9 销毁循环队列void destroy_sysqueue(SQueue_t **ppsque) //二级指针指向队列指针的指针 { //(*ppsque)解引用得到队列结构体指针 free((*ppsque)-pbase); //释放动态分配的数据存储区数组 free(*ppsque); //释放队列结构体本身 *ppsque NULL; //将调用者的队列指针置为 NULL防止野指针 } //调用 destroy_sysqueue(psque);4.10 附件代码① sysqueue.h#ifndef __SYSQUEUE_H__ #define __SYSQUEUE_H__ typedef int DataType_t; typedef struct sque { DataType_t *pbase; int head; int tail; }SQueue_t; #define MAX_QUEUE_LEN 6 extern SQueue_t *create_sysqueue(); extern int is_full_sysqueue(SQueue_t *psque); extern int push_sysqueue(SQueue_t *psque, DataType_t data); extern void show_sysqueue(SQueue_t *psque); extern int pop_sysqueue(SQueue_t *psque, DataType_t *pdata); extern void destroy_sysqueue(SQueue_t **ppsque); extern void clear_sysqueue(SQueue_t *psque); #endif② sysqueue.c#include sysqueue.h #include stdio.h #include stdlib.h SQueue_t *create_sysqueue() { SQueue_t *psque malloc(sizeof(SQueue_t)); if (NULL psque) { printf(malloc error\n); return NULL; } psque-pbase malloc(sizeof(DataType_t) * MAX_QUEUE_LEN); if (NULL psque-pbase) { printf(malloc error\n); return NULL; } psque-head 0; psque-tail 0; return psque; } int is_full_sysqueue(SQueue_t *psque) { if (((psque-tail 1) % MAX_QUEUE_LEN) psque-head) { return 1; } return 0; } int is_empty_sysqueue(SQueue_t *psque) { if (psque-head psque-tail) { return 1; } return 0; } int push_sysqueue(SQueue_t *psque, DataType_t data) { if (is_full_sysqueue(psque)) { return -1; } psque-pbase[psque-tail] data; psque-tail (psque-tail1) % MAX_QUEUE_LEN; return 0; } void show_sysqueue(SQueue_t *psque) { for (int i psque-head; i ! psque-tail; i (i1)%MAX_QUEUE_LEN) { printf(%d , psque-pbase[i]); } printf(\n); } int pop_sysqueue(SQueue_t *psque, DataType_t *pdata) { if (is_empty_sysqueue(psque)) { return -1; } if (pdata ! NULL) { *pdata psque-pbase[psque-head]; } psque-head (psque-head 1) % MAX_QUEUE_LEN; return 0; } void clear_sysqueue(SQueue_t *psque) { psque-head psque-tail 0; } void destroy_sysqueue(SQueue_t **ppsque) { free((*ppsque)-pbase); free(*ppsque); *ppsque NULL; }③ main.c#include sysqueue.h #include stdio.h int main(int argc, const char *argv[]) { SQueue_t *psque NULL; DataType_t data; psque create_sysqueue(); if (NULL psque) { return -1; } push_sysqueue(psque, 1); push_sysqueue(psque, 2); push_sysqueue(psque, 3); push_sysqueue(psque, 4); push_sysqueue(psque, 5); show_sysqueue(psque); pop_sysqueue(psque, data); push_sysqueue(psque, 6); show_sysqueue(psque); clear_sysqueue(psque); destroy_sysqueue(psque); return 0; }