文章目录队列一、队列的基本知识二、链式队列链式队列的创建链式队列的判空链式队列的入队链式队列的出队链式队列的遍历链式队列获取头元素链式队列的销毁三、顺序队列循环队列循环队列的创建循环队列的判空循环队列的判满循环队列的入队循环队列的出队循环队列的遍历循环队列的头元素获取循环队列的销毁队列对于队列其本质还是链表所以需要链表的知识以下两篇文章是对链表的详细讲解数据结构基本概念及单向链表单向链表的使用与进阶练习以及双向链表和内核链表一、队列的基本知识定义一种只允许从一端插入数据另外一端删除数据的线性存储结构。我们将数据插入的一端称为队尾删除数据的一端称为队头。插入数据的操作称为入队删除操作称为出队。特点先进先出后进后出。FIFO应用数据缓存实现方式顺序队列通过数组实现链式队列通过链表实现。二、链式队列API创建队列判空入队出队遍历获取头元素销毁链式队列的创建链式队列本质上也是一种链表因此同样创建一个结点结构体一个队列对象结构体相比于普通链表队列对象的结构体会多一个指向尾节点的指针。typedefintData_t;typedefstructnode{intdata;structnode*pnext;}Qnode;typedefstructlink{Qnode*phead;Qnode*ptail;intclen;}Qlink;Qlink*creat_queue(){Qlink*pqlinkmalloc(sizeof(Qlink));if(pqlinkNULL){printf(malloc error!\n);returnNULL;}pqlink-pheadNULL;pqlink-ptailNULL;pqlink-clen0;returnpqlink;}链式队列的判空和普通链表判空一样检测队列的头指针是否为NULL就可以判断队列是否为空了。intis_empty_queue(Qlink*pqlink){if(pqlink-pheadNULL){return1;}return0;}链式队列的入队接收队列指针与待插入数据首先动态申请新结点内存内存分配失败则打印错误并返回‑1分配成功后为新结点赋值数据域、将后继指针置空接着判断队列是否为空空队列时新结点同时作为队头与队尾非空则把新结点接到当前队尾之后并更新队尾指针最后队列长度自增成功返回 0。intinsert_qnode(Qlink*pqlink,Data_t data){Qnode*pinsertmalloc(sizeof(Qnode));if(pinsertNULL){printf(malloc error!\n);return-1;}pinsert-datadata;pinsert-pnextNULL;if(is_empty_queue(pqlink)){pqlink-pheadpinsert;pqlink-ptailpinsert;pqlink-clen;return0;}pqlink-ptail-pnextpinsert;pqlink-ptailpinsert;pqlink-clen;return0;}链式队列的出队函数接收队列指针和用于保存出队元素的指针。首先检查队列是否为空队列为空直接返回 - 1获取队头结点将队头指针向后移动一位取出队头结点的数据存入输出参数释放已出队结点的内存队列长度减 1若移动后队头指针变为空说明队列已清空将队尾指针也置为空操作成功返回 0。intgoout_qlink(Qlink*pqlink,Data_t*pdata){if(is_empty_queue(pqlink)){return-1;}Qnode*poutpqlink-phead;pqlink-pheadpout-pnext;if(pout!NULL){*pdatapout-data;}free(pout);pqlink-clen--;if(pqlink-pheadNULL){pqlink-ptailNULL;}return0;}链式队列的遍历传入队列指针先判断队列是否为空为空直接返回定义临时指针从队头结点开始循环顺着链表依次输出每个结点的数据指针不断后移直到遍历结束最后换行。intshow_qlink(Qlink*pqlink){if(is_empty_queue(pqlink)){return0;}Qnode*ptmppqlink-phead;while(ptmp!NULL){printf(%d ,ptmp-data);ptmpptmp-pnext;}printf(\n);}链式队列获取头元素首先判断队列是否为空若为空返回 - 1 表示读取失败不为空时将队头结点的数据赋值给外部指针变量带回读取成功后返回 0。intget_head_qlink(Qlink*pqlink,Data_t*pdata){if(is_empty_queue(pqlink)){return-1;}*pdatapqlink-phead-data;return0;}链式队列的销毁调用出队函数依次释放队列内每一个结点直到队头指针为空、所有链表结点全部清理完毕随后释放队列管理结构体本身的内存最终返回 0 完成队列销毁。intdestroy_qlink(Qlink*pqlink){while(pqlink-phead){goout_qlink(pqlink,NULL);}free(pqlink);return0;}三、顺序队列循环队列顺序队列本质上就是一个数组由于一般顺序队列会出现假溢出情况所以一般不使用此队列。因此循环队列就出现了其本质就是一个循环的数组。API创建判空判空入队出队遍历获取头元素销毁循环队列的创建循环队列的创建和链式队列的创建基本一样首先创建一个结构体来作为循环队列对象其中包含指向数组首元素的一个指针pbase指向队列首元素的指针phead指向队列结束标志的指针ptail。#defineSQE_MAX_LEN10typedefintData_t;typedefstructsq{Data_t*pbase;intphead;intptail;}Sque_t;然后在堆区空间中申请一定大小的空间使pbase指向此空间。Sque_t*creat_sque(){Sque_t*psquemalloc(sizeof(Sque_t));if(NULLpsque){printf(malloc error\n);returnNULL;}psque-pbasemalloc(sizeof(Data_t)*SQE_MAX_LEN);psque-phead0;psque-ptail0;returnpsque;}这里不得不提一下对于一个标准的循环队列它的首尾之间一般会空出一个空位这样方便判断循环队列的空满状态。如下图所示更加直观来看就是这样循环队列的判空通过判断头尾指针是否指向相同位置来判断队列的空。intis_empty_sque(Sque_t*psque){if(psque-pheadpsque-ptail){return1;}return0;}循环队列的判满利用牺牲一个存储单元的判满规则判断队尾指针加一后取模队列最大长度是否等于队头指针条件成立代表队列已满打印提示信息并返回 1否则队列未满返回 0。intis_full_sque(Sque_t*psque){if((psque-ptail1)%SQE_MAX_LENpsque-phead){printf(queue is full\n);return1;}return0;}循环队列的入队调用判满函数检查队列是否已满队列已满则入队失败返回‑1未满时将待插入数据存入队尾下标对应的数组位置再更新队尾下标通过取模运算实现指针循环入队成功返回 0。intpush_sque(Sque_t*psque,Data_t data){if(is_full_sque(psque)){return-1;}psque-pbase[psque-ptail]data;psque-ptail(psque-ptail1)%SQE_MAX_LEN;return0;}循环队列的出队调用判空函数检查队列是否为空队列为空则出队失败返回‑1队列非空时利用取模运算将队头下标向后循环移动一位完成出队成功返回 0。intpop_sque(Sque_t*psque){if(is_empty_sque(psque)){return-1;}psque-phead(psque-phead1)%SQE_MAX_LEN;return0;}循环队列的遍历先用临时变量保存队头下标从队头开始循环输出数组内的数据每次下标加一并对队列最大长度取模直到临时下标追上队尾下标结束遍历最后换行。voidshow_sque(Sque_t*psque){inttmppsque-phead;while(tmp!psque-ptail){printf(%d ,psque-pbase[tmp]);tmp(tmp1)%SQE_MAX_LEN;}printf(\n);}循环队列的头元素获取首先调用判空函数检测队列若队列为空返回‑1 表示读取失败非空时取出队头下标对应的数组元素通过指针参数pdata将数据带出读取成功返回 0。intget_sque_head(Sque_t*psque,Data_t*pdata){if(is_empty_sque(psque)){return-1;}*pdatapsque-pbase[psque-phead];return0;}循环队列的销毁先释放存储队列元素的动态数组空间pbase再释放队列管理结构体本身所占内存完成内存回收最后返回 0表示销毁完毕。intdestroy_sque(Sque_t*psque){free(psque-pbase);free(psque);return0;}