C语言中队列的示例分析
导读:本文共8383字符,通常情况下阅读需要28分钟。同时您也可以点击右侧朗读,来听本文内容。按键盘←(左) →(右) 方向键可以翻页。
摘要: 一、队列(Queue)0x00 队列的概念???? 概念:① 队列只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表。② 入队列,进行插入操作的一端称为 队尾。出队列,进行删除操作的一端称为 队头。③ 队列中的元素遵循先进先出的原则,即 FIFO原则(First In First Out)0x01 队列的结构???? 结构:二、队列的定义0x00... ...
目录
(为您整理了一些要点),点击可以直达。一、队列(Queue)
0x00 队列的概念
???? 概念:
① 队列只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表。
② 入队列,进行插入操作的一端称为 队尾。出队列,进行删除操作的一端称为 队头。
③ 队列中的元素遵循先进先出的原则,即 FIFO原则(First In First Out)
0x01 队列的结构
???? 结构:
二、队列的定义
0x00 链式队列
typedefintQueueDataType;//队列类型typedefstructQueueNode{structQueueNode*next;//指向下一个节点QueueDataTypedata;//数据}QueueNode;typedefstructQueue{QueueNode*pHead;//头指针QueueNode*pTail;//尾指针}Queue;
❓ 为什么不使用单链表?
???? 单链表我们只定义了一个指针指向头,没有定义尾指针。因为定义尾指针解决不了问题,比如尾插尾删。所以我们没有必要定义一个结构体把他们封到一起。这里我们再定义一个头指针 head 一个尾指针 tail,这两个指针才有意义。因为根据队列的性质,我们只会在队尾插,不会再队尾删。所以这个尾指针的价值就得到了完美的体现,实际中定义几个指针是看你的需求确定的。
0x02接口函数
???? 这是需要实现几个接口函数:
voidQueueInit(Queue*pQ);//队列初始化voidQueueDestroy(Queue*pQ);//销毁队列boolQueueIsEmpty(Queue*pQ);//判断队列是否为空voidQueuePush(Queue*pQ,QueueDataTypex);//入队voidQueuePop(Queue*pQ);//出队QueueDataTypeQueueFront(Queue*pQ);//返回队头数据QueueDataTypeQueueBack(Queue*pQ);//返回队尾数据intQueueSize(Queue*pQ);//求队列大小
三、队列的实现
0x00 队列初始化(QueueInit)
???? Queue.h
#pragmaonce#include<stdio.h>#include<stdlib.h>#include<assert.h>#include<stdbool.h>typedefintQueueDataType;//队列类型typedefstructQueueNode{structQueueNode*next;//指向下一个节点QueueDataTypedata;//数据}QueueNode;typedefstructQueue{QueueNode*pHead;//头指针QueueNode*pTail;//尾指针}Queue;voidQueueInit(Queue*pQ);//队列初始化
???? Queue.c
/*队列初始化:将头尾指针置为NULL*/voidQueueInit(Queue*pQ){assert(pQ);//防止传入的pQ为空pQ->pHead=pQ->pTail=NULL;//将头尾指针置空}
???? 解析:首先使用断言防止传入的pQ为空。初始化只需要把头指针和尾指针都置成空即可。
0x01 销毁队列(QueueDestroy)
/*销毁队列:free掉所有队列元素并将头尾置空*/voidQueueDestroy(Queue*pQ){assert(pQ);//防止传入的pQ为空QueueNode*cur=pQ->pHead;//创建遍历指针curwhile(cur!=NULL){//cur不为空就进入循环QueueNode*curNext=cur->next;//信标指针curNext,防止释放cur后找不到其下一个节点free(cur);//释放cur当前指向的节点cur=curNext;//移动指针cur}pQ->pHead=pQ->pTail=NULL;//置空干掉野指针}
???? 解读:
① 首先断言防止传入的pQ为空。
② 销毁要把所有节点都释放掉,我们创建遍历指针 cur 遍历整个队列。既然要释放 cur 指向的节点,为了防止释放 cur 之后找不到其下一个节点导致无法移动,我们这里创建一个类似于信标性质的指针 curNext 来记录一下 cur 的下一个节点,之后再 free 掉 cur,这样就可以移动 cur 了。
③ 最后为了防止野指针,还需要把头指针和尾指针都置为空。
0x02 判断队列是否为空(HeapIsEmpty)
???? Queue.h
boolQueueIsEmpty(Queue*pQ);//判断队列是否为空
???? 解读:布尔值,返回 true 或 false
???? Queue.c
/*判断队列是否为空*/boolQueueIsEmpty(Queue*pQ){assert(pQ);//防止传入的pQ为空returnpQ->pHead==NULL;//如果成立则为True,不成立则为False}
???? 解读:
① 首先断言防止传入的pQ为空。
② 判断队列是否为空,可以直接返回,巧妙地利用布尔类型的特性。如果 pQ->pHead == NULL 成立则为真,会返回 true;不成立则为假,会返回 false。
0x03 入队(QueuePush)
???? Queue.h
voidQueuePush(Queue*pQ,QueueDataTypex);//入队
???? Queue.c
/*入队:队尾入数据,对头出数据。如果是第一个入队的则既要当头又当尾*/voidQueuePush(Queue*pQ,QueueDataTypex){assert(pQ);//防止传入的pQ为空/*创建新节点:创建一个大小为QueueNode的空间*/QueueNode*new_node=(QueueNode*)malloc(sizeof(QueueNode));/*检查malloc*/if(new_node==NULL){printf("mallocfailed!\n");exit(-1);}/*放置*/new_node->data=x;//待插入的数据new_node->next=NULL;//默认为空/*入队:*【思路草图】*情况1:队列为空:既当头又当尾*[new_node]*↑↑*pHeadpTail**情况2:队列不为空:队尾入数据*[]->[]->[]->[]->[new_node]*pHeadpTailpTail->next*↓↑*----------→pTail(更新尾指针)*/if(pQ->pHead==NULL){//情况1:队列为空pQ->pHead=pQ->pTail=new_node;//既当头又当尾}else{//情况2:队列不为空pQ->pTail->next=new_node;//在现有尾的后一个节点放置new_nodepQ->pTail=new_node;//更新pTail,使它指向新的尾}}
???? 解读:
① 首先断言防止传入的pQ为空。
② 我们首先要创建新节点。通过 malloc 动态内存开辟一块 QueueNode 大小的空间,都学到这里了大家想必都养成了检查 malloc 的好习惯了吧?。最后放置数据吗,将待插入的数据 x 交给 data,next 默认置空,和之前学链表一样,这里就不过多赘述了。
③ 新节点创建好后,我们可以开始写入队的操作了。首先要理解队列的性质:队尾入数据,队头出数据。这里既然是入队,就要在对尾后面进行插入。这里我们还要考虑到如果队列为空的情况,这时我们要把头指针和尾指针都交付给 new_node 。为了理清思路,我们可以画一个思路草图来帮助我们更好地理解:
有了这个图,我们就可以清楚地实现了:
if(pQ->pHead==NULL){//情况1:队列为空pQ->pHead=pQ->pTail=new_node;//既当头又当尾}else{//情况2:队列不为空pQ->pTail->next=new_node;//在现有尾的后一个节点放置new_nodepQ->pTail=new_node;//更新pTail,使它指向新的尾}
当队列为空时,令头指针和尾指针都指向 new_node ,当队列不为空时,再尾部地下一个节点放置 new_node,随后再更新尾指针让其指向新的尾(new_node 的位置)。
0x04 出队(QueuePop)
???? Queue.h
voidQueuePop(Queue*pQ);//出队
???? Queue.c
/*出队:队尾入数据,对头出数据*/voidQueuePop(Queue*pQ){assert(pQ);//防止传入的pQ为空assert(!QueueIsEmpty(pQ));//防止队列为空/*出队:*【思路草图】*[free]->[]->[]->[]*pHeadheadNext*↓↑*-------→pHead(更新头指针)*/QueueNode*headNext=pQ->pHead->next;//信标指针HeadNextfree(pQ->pHead);pQ->pHead=headNext;//更新头/*如果队内都被删完了,不处理pTail就会带来野指针的隐患*【思路草图】*NULL已经被free掉的内存!*↑↑(野指针警告)*pHead(因为HeadNext是NULL)pTail*/if(pQ->pHead==NULL)//如果pHead为空pQ->pTail=NULL;//处理一下尾指针,将尾指针置空}
???? 解读:
① 首先断言防止传入的 pQ 为空,这里还要放置队列为空,如果队列为空还要求出队的话会出问题的,所以这里要断言一下 QueueIsEmpty 为假。
② 思路草图如下:
出数据需要释放,和销毁一样,这里使用一个类似于信标性质的指针来记录 pHead 的下一个节点,之后我们就可以大胆地释放 pHead 而不用担心找不到了。free 掉之后更新头即可,令头指针指向 headNext 即可。
???? 注意:这里还要考虑一个问题,如果队内都被删完了,pHead 往后走指向空,但是 pTail 仍然指向那块已经被 free 掉的空间。pTail 就是一个典型的野指针。
我们可以不用担心 pHead,因为后面没有数据他会自然指向 NULL,但是我们这里得关注 pTail !我们需要手动处理一下它:
如果 pHead 为空,我们就把 pTail 也置为空即可。
if(pQ->pHead==NULL)//如果pHead为空pQ->pTail=NULL;//处理一下尾指针,将尾指针置空
0x05返回队头数据(QueueFront)
???? Queue.h
QueueDataTypeQueueFront(Queue*pQ);//返回队头数据
???? Queue.c
/*返回队头数据*/QueueDataTypeQueueFront(Queue*pQ){assert(pQ);//防止传入的pQ为空assert(!QueueIsEmpty(pQ));//防止队列为空returnpQ->pHead->data;}
???? 解读:
① 首先断言防止传入的 pQ 为空,这里我们还是要断言一下 QueueIsEmpty 为假,因为如果队内没有数据,还返回个锤子数据呢。
② 这里直接返回头的数据即可,特别简单没有什么好讲的。
0x06返回队尾数据(QueueBack)
???? Queue.h
QueueDataTypeQueueBack(Queue*pQ);//返回队尾数据
???? Queue.c
/*返回队尾数据*/QueueDataTypeQueueBack(Queue*pQ){assert(pQ);//防止传入的pQ为空assert(!QueueIsEmpty(pQ));//防止队列为空returnpQ->pTail->data;}
???? 解读:
① 首先断言防止传入的 pQ 为空,断言一下 QueueIsEmpty 为假。
② 这里直接返回队尾的数据即可。
0x07求队列大小(QueueSize)
???? Queue.h
intQueueSize(Queue*pQ);//求队列大小
???? Queue.c
/*求队列大小:计数器法*/intQueueSize(Queue*pQ){assert(pQ);//防止传入的pQ为空intcount=0;//计数器QueueNode*cur=pQ->pHead;//创建遍历指针curwhile(cur!=NULL){++count;//计数+1cur=cur->next;//移动指针cur}returncount;}
???? 解读:这里我们采用计数器法来求大小即可,调用一次就是 O(N),也没什么不好的。
① 首先断言防止传入的 pQ 为空。
② 创建计数器变量和遍历指针 cur,遍历整个队列并计数,最后返回计数的结果即可。
0x08 完整代码
???? Queue.h
#pragmaonce#include<stdio.h>#include<stdlib.h>#include<assert.h>#include<stdbool.h>typedefintQueueDataType;//队列类型typedefstructQueueNode{structQueueNode*next;//指向下一个节点QueueDataTypedata;//数据}QueueNode;typedefstructQueue{QueueNode*pHead;//头指针QueueNode*pTail;//尾指针}Queue;voidQueueInit(Queue*pQ);//队列初始化voidQueueDestroy(Queue*pQ);//销毁队列boolQueueIsEmpty(Queue*pQ);//判断队列是否为空voidQueuePush(Queue*pQ,QueueDataTypex);//入队voidQueuePop(Queue*pQ);//出队QueueDataTypeQueueFront(Queue*pQ);//返回队头数据QueueDataTypeQueueBack(Queue*pQ);//返回队尾数据intQueueSize(Queue*pQ);//求队列大小
???? Queue.c
#include<Queue.h>/*队列初始化:将头尾指针置为NULL*/voidQueueInit(Queue*pQ){assert(pQ);//防止传入的pQ为空pQ->pHead=pQ->pTail=NULL;//将头尾指针置空}/*销毁队列:free掉所有队列元素并将头尾置空*/voidQueueDestroy(Queue*pQ){assert(pQ);//防止传入的pQ为空QueueNode*cur=pQ->pHead;//创建遍历指针curwhile(cur!=NULL){//cur不为空就进入循环QueueNode*curNext=cur->next;//信标指针curNext,防止释放cur后找不到其下一个节点free(cur);//释放cur当前指向的节点cur=curNext;//移动指针cur}pQ->pHead=pQ->pTail=NULL;//置空干掉野指针}/*判断队列是否为空*/boolQueueIfEmpty(Queue*pQ){assert(pQ);//防止传入的pQ为空returnpQ->pHead==NULL;//如果成立则为True,不成立则为False}/*入队:队尾入数据,对头出数据。如果是第一个入队的则既要当头又当尾*/voidQueuePush(Queue*pQ,QueueDataTypex){assert(pQ);//防止传入的pQ为空/*创建新节点:创建一个大小为QueueNode的空间*/QueueNode*new_node=(QueueNode*)malloc(sizeof(QueueNode));/*检查malloc*/if(new_node==NULL){printf("mallocfailed!\n");exit(-1);}/*放置*/new_node->data=x;//待插入的数据new_node->next=NULL;//默认为空/*入队:*【思路草图】*情况1:队列为空:既当头又当尾*[new_node]*↑↑*pHeadpTail**情况2:队列不为空:队尾入数据*[]->[]->[]->[]->[new_node]*pHeadpTailpTail->next*↓↑*----------→pTail(更新尾指针)*/if(pQ->pHead==NULL){//情况1:队列为空pQ->pHead=pQ->pTail=new_node;//既当头又当尾}else{//情况2:队列不为空pQ->pTail->next=new_node;//在现有尾的后一个节点放置new_nodepQ->pTail=new_node;//更新pTail,使它指向新的尾}}/*出队:队尾入数据,对头出数据*/voidQueuePop(Queue*pQ){assert(pQ);//防止传入的pQ为空assert(!QueueIsEmpty(pQ));//防止队列为空/*出队:*【思路草图】*[free]->[]->[]->[]*pHeadheadNext*↓↑*-------→pHead(更新头指针)*/QueueNode*headNext=pQ->pHead->next;//信标指针HeadNext,防止释放pHead后找不到其下一个节点free(pQ->pHead);pQ->pHead=headNext;//更新头/*如果队内都被删完了,不处理pTail就会带来野指针的隐患*【思路草图】*NULL已经被free掉的空间!*↑↑(野指针)*pHead(因为HeadNext是NULL)pTail*/if(pQ->pHead==NULL)//如果pHead为空pQ->pTail=NULL;//处理一下尾指针,将尾指针置空}/*返回队头数据*/QueueDataTypeQueueFront(Queue*pQ){assert(pQ);//防止传入的pQ为空assert(!QueueIsEmpty(pQ));//防止队列为空returnpQ->pHead->data;}/*返回队尾数据*/QueueDataTypeQueueBack(Queue*pQ){assert(pQ);//防止传入的pQ为空assert(!QueueIsEmpty(pQ));//防止队列为空returnpQ->pTail->data;}/*求队列大小:计数器法*/intQueueSize(Queue*pQ){assert(pQ);//防止传入的pQ为空intcount=0;//计数器QueueNode*cur=pQ->pHead;//创建遍历指针curwhile(cur!=NULL){++count;//计数+1cur=cur->next;//移动指针cur}returncount;}
???? Test.c
#include"Queue.h"voidTestQueue1(){Queueq;QueueInit(&q);QueuePush(&q,1);QueuePush(&q,2);QueuePush(&q,3);QueuePush(&q,4);QueuePop(&q);QueuePop(&q);QueuePop(&q);QueuePop(&q);//QueuePop(&q);QueueDestroy(&q);}voidTestQueue2(){Queueq;QueueInit(&q);QueuePush(&q,1);QueuePush(&q,2);QueuePush(&q,3);QueuePush(&q,4);//假设先入了12,让1出来,再继续入,它的顺序还是不会变。//永远保持先进先出的,无论是入了两个出两个,再入再出,还是全部入完了再出,都是不会变的。这就是队列的性质while(!QueueIsEmpty(&q)){QueueDataTypefront=QueueFront(&q);printf("%d",front);QueuePop(&q);//pop掉去下一个}printf("\n");QueueDestroy(&q);}intmain(void){TestQueue2();return0;}
</div> <div class="zixun-tj-product adv-bottom"></div> </div> </div> <div class="prve-next-news">
C语言中队列的示例分析的详细内容,希望对您有所帮助,信息来源于网络。