一队列队列只允许在一端进行插入队尾在另一端进行删除队头操作的特殊线性表。类比现实生活中的排队就餐队尾加人插入队头拿到饭了出去删除。具有先进先出的特质。二队列的实现我们选择单链表。PS栈可以通过数组和链表来实现但由于链表的尾插和尾删操作成本较高故选择了数组队列同样可以通过数组和链表来实现但由于数组的头删之后还要挪动数据成本较高故选择了单链表。双向链表啥时候都能实现但我们反而要去看数组和单链表是否可行。因为双向链表空间成本较高。代码实现//按照单链表的节点构造写 typedef int QDatatype; struct QueueNode { QDatatype val; struct QueueNode* next; }; typedef struct QueueNode QNode;三队列相关函数的实现1尾插入队 QueuePushvoid QueuePush(QNode** pphead,QNode** pptail,QDatatype x);当链表为空时插入需要头结点当链表不为空时插入就只需要尾结点了所以参数需要头尾结点且需要改变实参所以是二级指针传址调用。比较一下为啥单链表的插入操作中只传头结点而不传尾结点入队插入函数传尾结点的意义是以免每次进行尾插操作都要遍历查找尾结点所以干脆把尾结点传给了入队的插入函数。而在单链表的尾插中我们就算传了尾结点也不顶用我们还需要找到尾结点的前一个节点难道还加一个参数prev那就更麻烦了所以我们干脆只传了头结点。通过头结点我们就能找到ptail和prev了只不过每次都要遍历。从函数的参数观察每次都要传两个二级指针是不是太复杂了复杂在于需要传两个指针且指针还都是二级这里我们有一个很妙的思路我们创建一个结构体用于存放头结点指针和尾结点指针再将结构体指针作为参数传给函数。结构体Queue的实现//Queue.h //头尾结点指针的结构体 typedef struct Queue { QNode* phead; QNode* ptail; }Queue; //入队声明 void QueuePush(Queue* pq, QDatatype x);因为函数中的插入操作会导致头结点尾结点的指针发生改变所以我们才需要传递二级指针(QNode节点结构体的指针的指针)在此处我们将头结点指针和尾结点指针放在一个结构体中头尾节点指针就成了结构体的一个成员变量我们想通过函数真正改变结构体的成员变量就只需要传递结构体指针就行了。这样就解决了一次性需要传两个二级指针的复杂参数问题。写到这不妨来回顾一下——联想到双向链表的传参这和在双向链表中我们传递哨兵位节点指针一级就够了而不用二级的底层逻辑是一样的。在双向循环带头链表中头插操作是将新节点插在哨兵位节点和第一个节点之间并不是要改变哨兵位节点指针而是改变哨兵位结构体节点的成员变量next指针所以只需要传递哨兵位结构体节点指针不需要传指针的指针(二级指针)了。而这里密封的Queue结构体就类似于哨兵位的结构体。但Queue结构体仍然存在优化空间。在队列中有数元素个数的函数QueueSize如果我们去遍历链表则函数的时间复杂度为O(N)但假如在队列中存在像顺序表中的size一样的变量我们只需要在入队函数中写一条size出队函数中写size--则到调用QueueSize函数时size不就已经代表了当下队列中的元素个数了吗这就避免了我们再去从头遍历带来的时间消耗。代码优化//Queue.h //头尾结点指针的结构体 typedef struct Queue { QNode* phead; QNode* ptail; int size; }Queue; //入队声明 void QueuePush(Queue* pq, QDatatype x);或许你会问既然要加一个额外变量size为啥是加在Queue结构体而不是QNode结构体里如果加在QNode结构体里就是加在了节点里那只要创建节点每个节点中都需要再多一块空间存储size变量岂不是造成更多的额外消耗N而在Queue结构体中只会占一块空间。1写到这我们先来实现初始化函数。2初始化 QueueInit注意初始化函数初始的是装了头尾结点和size的结构体Queue而不是节点结构体QNode。代码实现://Queue.c //初始化定义 void QueueInit(Queue* pq) { pq-phead pq-ptail NULL; pq-size 0; }再回到入栈函数的实现中。代码实现//队尾插入 void QueuePush(Queue* pq , QDatatype x) { assert(pq); //不再单独封装一个创建节点函数了因为只需要在插入函数中写一次没必要 QNode* newnode (QNode*)malloc(sizeof(QNode)); newnode-val x; newnode-next NULL; if (newnode NULL) { perror(failed malloc); return 0; } if (pq-phead NULL) { //空链表的插入 pq-phead pq-ptail newnode; } else { //非空链表的插入 pq-ptail-next newnode; pq-ptail newnode; } pq-size; //为QueueSize函数做准备 }在实现单链表时我们封装了一个SLTBuyNode创建节点函数头插、尾插、任意位置插入都需要创建新节点封装成函数就能让程序更简洁但在队列中只有尾插入队函数需要创建新节点所以不需要再额外封装一个创建节点函数。我们说QNode节点结构体不需要初始化为什么我们先来回顾一下顺序表的初始化我们在测试源文件中创建了顺序表结构体变量sl并将其指针传给了STInit函数顺序表结构体有了空间我们就能对其中的成员变量arr、capacity和size进行初始化可我们并不能对数组元素进行初始化都没有malloc空间出来根本就谈不上初始化。而在链表中我们在测试源文件中创建了单链表的节点结构体指针并置空仅仅只是创建了结构体指针而没有创建结构体节点变量因为节点需要malloc创建而我们还没有涉及malloc啊那既然连结构体节点都没有创建又何来初始化结构体成员这一说呢等到真正通过创建节点函数创建结构体节点后在创建节点函数内部我们就能对成员变量data和next进行了赋值操作其实在我看来这更像是初始化。而初始化的本质就是赋值。3头删出队 Queuepop代码实现//队头删除 void QueuePop(Queue* pq) { //只要涉及删除就一定要对链表判空 assert(pq); assert(pq-size 0); if (pq-phead-next NULL) { //仅剩一个节点 free(pq-phead); pq-phead pq-ptail NULL; } else { //多节点链表 QNode* del pq-phead-next; free(pq-phead); pq-phead del; } pq-size--; }分成单节点和多节点的情况是为了防止ptail变成野指针的情况。其实多节点分支下的逻辑足以满足单、多节点的头删操作仅仅只是等到链表变成空后没有处理ptail这样ptail就会变成野指针为了防止这种情况我们可以分成单、多节点的情况。当然也可以按照如下方式处理//队头删除 void QueuePop(Queue* pq) { //只要涉及删除就一定要对链表判空 assert(pq); assert(pq-size 0); //处理ptail野指针的另一种写法 QNode* del pq-phead-next; free(pq-phead); pq-phead del; if (pq-phead NULL) pq-ptail NULL; pq-size--; }不过也要注意此时的if的条件判断是判空而不是判断是否为单节点链表了。4取队头节点val数据 QueueFront注意取队头节点val数据仅仅只是取值并没有涉及删除节点操作。//取队头val数据 QDatatype QueueFront(Queue* pq) { assert(pq); //不能对空指针解引用 assert(pq-size 0); //确保队列还能有节点能进行取值操作 return pq-phead-val; }当QueueFront和QueuePop搭配使用时就能获取队列中的所有节点的val值。判空总结顺序表assert(ps-size)单链表assert(*pphead)双向链表assert(phead-next ! phead)栈assert(pst-size)队列assert(pq-phead) / assert(pq-size)。5取队尾节点的val数据 QueueBack//取队尾节点的val数据 QDatatype QueueBack(Queue* pq) { assert(pq); assert(pq-size 0); //assert(pq-ptail); return pq-ptail-val; }6数队列节点个数 QueueSize//数队列节点个数 int QueueSize(Queue* pq) { assert(pq); return pq-size; }7判空 QueueEmpty//判空 bool QueueEmpty(Queue* pq) { assert(pq); return pq-size 0; }8队列的销毁 QueueDestory//队列的销毁 void QueueDestory(Queue* pq) { assert(pq); QNode* pcur pq-phead; while (pcur) { QNode* next pcur-next; //不提前保存pcur下一个节点释放pcur后就找不到了 free(pcur); pcur next; } pq-phead pq-ptail NULL; pq-size 0; }四代码汇总//Queue.h #includestdio.h #includeassert.h #includestdlib.h #includestdbool.h typedef int QDatatype; struct QueueNode { QDatatype val; struct QueueNode* next; }; typedef struct QueueNode QNode; //头尾结点指针的结构体 typedef struct Queue { QNode* phead; QNode* ptail; int size; }Queue; //尾插入队声明 void QueuePush(Queue* pq, QDatatype x); //初始化Queue结构体声明 void QueueInit(Queue* pq); //出队头删声明 void QueuePop(Queue* pq); //取队头val QDatatype QueueFront(Queue* pq); //取队尾val QDatatype QueueBack(Queue* pq); //节点个数 int QueueSize(Queue* pq); //判空 bool QueueEmpty(Queue* pq); //销毁队列 void QueueDestory(Queue* pq);//Queue.c #includeQueue.h //初始化定义 void QueueInit(Queue* pq) { pq-phead pq-ptail NULL; pq-size 0; } //队尾插入 void QueuePush(Queue* pq , QDatatype x) { assert(pq); //不再单独封装一个创建节点函数了因为只需要在插入函数中写一次没必要 QNode* newnode (QNode*)malloc(sizeof(QNode)); newnode-val x; newnode-next NULL; if (newnode NULL) { perror(failed malloc); return 0; } if (pq-phead NULL) { //空链表的插入 pq-phead pq-ptail newnode; } else { //非空链表的插入 pq-ptail-next newnode; pq-ptail newnode; } pq-size; //为QueueSize函数做准备 } //队头删除 void QueuePop(Queue* pq) { //只要涉及删除就一定要对链表判空 assert(pq); assert(pq-size 0); if (pq-phead-next NULL) { //仅剩一个节点 free(pq-phead); pq-phead pq-ptail NULL; } else { //多节点链表 QNode* del pq-phead-next; free(pq-phead); pq-phead del; } pq-size--; //处理ptail野指针的另一种写法 /*QNode* del pq-phead-next; free(pq-phead); pq-phead del; if (pq-phead NULL) pq-ptail NULL;*/ } //取队头val数据 QDatatype QueueFront(Queue* pq) { assert(pq); assert(pq-size 0); //assert(pq-phead); return pq-phead-val; } //取队尾节点的val数据 QDatatype QueueBack(Queue* pq) { assert(pq); assert(pq-size 0); //assert(pq-ptail); return pq-ptail-val; } //数队列节点个数 int QueueSize(Queue* pq) { assert(pq); return pq-size; } //判空 bool QueueEmpty(Queue* pq) { assert(pq); return pq-size 0; } //队列的销毁 void QueueDestory(Queue* pq) { assert(pq); QNode* pcur pq-phead; while (pcur) { QNode* next pcur-next; free(pcur); pcur next; } pq-phead pq-ptail NULL; pq-size 0; }//Test.c #includeQueue.h void Test01() { Queue q; QueueInit(q); QueuePush(q, 1); QueuePush(q, 2); QueuePush(q, 3); QueuePush(q, 4); while (!QueueEmpty(q)) { printf(%d ,QueueFront(q)); QueuePop(q); } } int main() { Test01(); return 0; }测试源文件在顺序表中数组我们创建一个结构体类型变量SL sl进行测试在单链表和双向链表中我们都是创建一个结构体节点指针变量STLNode* plist第一个节点/LTNode* plist哨兵位节点来进行测试在栈中数组我们创建一个结构体类型变量ST st 来进行测试在队列中单链表我们创建一个结构体变量类型Queue q来进行测试。由于函数参数都需要pqphead、ptail所以创建Queue q是我们需要的。或许你会觉得这跟单链表创建plist的行为不同但其实是一样的。创建plist的本质就是创建了单链表的第一个节点而创建Queue q也就是创建了单链表的第一个节点因为Queue结构体中包含了phead。出栈顺序在栈中我们说数据入栈的顺序是1 2 3 4但出栈的顺序却不只有4 3 2 1这一种数据可以边进边出所以数据出栈的顺序是有N种的。但在队列中只要数据入队的顺序是1 2 3 4那么出队的顺序就只会是1 2 3 4这一种即使是数据边进边出也只有这一种。可以来测试一下//Test.c #includeQueue.h void Test01() { Queue q; QueueInit(q); QueuePush(q, 1); printf(%d \n, QueueFront(q)); QueuePop(q); QueuePush(q, 2); printf(%d \n, QueueFront(q)); QueuePop(q); QueuePush(q, 3); printf(%d \n, QueueFront(q)); QueuePop(q); QueuePush(q, 4); printf(%d \n, QueueFront(q)); QueuePop(q); while (!QueueEmpty(q)) { printf(%d ,QueueFront(q)); QueuePop(q); } } int main() { Test01(); return 0; }——end——