C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)系列隊(duì)列篇
一、隊(duì)列(Queue)
0x00 隊(duì)列的概念
?? 概念:
① 隊(duì)列只允許在一端進(jìn)行插入數(shù)據(jù)操作,在另一端進(jìn)行刪除數(shù)據(jù)操作的特殊線性表。
② 入隊(duì)列,進(jìn)行插入操作的一端稱為 隊(duì)尾。出隊(duì)列,進(jìn)行刪除操作的一端稱為 隊(duì)頭。
③ 隊(duì)列中的元素遵循先進(jìn)先出的原則,即 FIFO?原則(First In First Out)
0x01 隊(duì)列的結(jié)構(gòu)
?? 結(jié)構(gòu):
二、隊(duì)列的定義
0x00 鏈?zhǔn)疥?duì)列
typedef int QueueDataType; //隊(duì)列類型 typedef struct QueueNode { struct QueueNode* next; //指向下一個(gè)節(jié)點(diǎn) QueueDataType data; //數(shù)據(jù) } QueueNode; typedef struct Queue { QueueNode* pHead; //頭指針 QueueNode* pTail; //尾指針 } Queue;
? 為什么不使用單鏈表?
?? 單鏈表我們只定義了一個(gè)指針指向頭,沒(méi)有定義尾指針。因?yàn)槎x尾指針解決不了問(wèn)題,比如尾插尾刪。所以我們沒(méi)有必要定義一個(gè)結(jié)構(gòu)體把他們封到一起。這里我們?cè)俣x一個(gè)頭指針 head 一個(gè)尾指針 tail?,這兩個(gè)指針才有意義。因?yàn)楦鶕?jù)隊(duì)列的性質(zhì),我們只會(huì)在隊(duì)尾插,不會(huì)再隊(duì)尾刪。所以這個(gè)尾指針的價(jià)值就得到了完美的體現(xiàn),實(shí)際中定義幾個(gè)指針是看你的需求確定的。
0x02?接口函數(shù)
?? 這是需要實(shí)現(xiàn)幾個(gè)接口函數(shù):
void QueueInit(Queue* pQ); //隊(duì)列初始化 void QueueDestroy(Queue* pQ); //銷毀隊(duì)列 bool QueueIsEmpty(Queue* pQ); //判斷隊(duì)列是否為空 void QueuePush(Queue* pQ, QueueDataType x); //入隊(duì) void QueuePop(Queue* pQ); //出隊(duì) QueueDataType QueueFront(Queue* pQ); //返回隊(duì)頭數(shù)據(jù) QueueDataType QueueBack(Queue* pQ); //返回隊(duì)尾數(shù)據(jù) int QueueSize(Queue* pQ); //求隊(duì)列大小
三、隊(duì)列的實(shí)現(xiàn)
0x00 隊(duì)列初始化(QueueInit)
?? Queue.h
#pragma once #include <stdio.h> #include <stdlib.h> #include <assert.h> #include <stdbool.h> typedef int QueueDataType; //隊(duì)列類型 typedef struct QueueNode { struct QueueNode* next; //指向下一個(gè)節(jié)點(diǎn) QueueDataType data; //數(shù)據(jù) } QueueNode; typedef struct Queue { QueueNode* pHead; //頭指針 QueueNode* pTail; //尾指針 } Queue; void QueueInit(Queue* pQ); //隊(duì)列初始化
?? Queue.c
/* 隊(duì)列初始化:將頭尾指針置為NULL */ void QueueInit(Queue* pQ) { assert(pQ); //防止傳入的pQ為空 pQ->pHead = pQ->pTail = NULL; //將頭尾指針置空 }
?? 解析:首先使用斷言防止傳入的pQ為空。初始化只需要把頭指針和尾指針都置成空即可。
0x01 銷毀隊(duì)列(QueueDestroy)
/* 銷毀隊(duì)列:free掉所有隊(duì)列元素并將頭尾置空 */ void QueueDestroy(Queue* pQ) { assert(pQ); //防止傳入的pQ為空 QueueNode* cur = pQ->pHead; //創(chuàng)建遍歷指針cur while(cur != NULL) { //cur不為空就進(jìn)入循環(huán) QueueNode* curNext = cur->next; //信標(biāo)指針curNext,防止釋放cur后找不到其下一個(gè)節(jié)點(diǎn) free(cur); //釋放cur當(dāng)前指向的節(jié)點(diǎn) cur = curNext; //移動(dòng)指針cur } pQ->pHead = pQ->pTail = NULL; //置空干掉野指針 }
?? 解讀:
① 首先斷言防止傳入的pQ為空。
② 銷毀要把所有節(jié)點(diǎn)都釋放掉,我們創(chuàng)建遍歷指針 cur 遍歷整個(gè)隊(duì)列。既然要釋放 cur 指向的節(jié)點(diǎn),為了防止釋放 cur 之后找不到其下一個(gè)節(jié)點(diǎn)導(dǎo)致無(wú)法移動(dòng),我們這里創(chuàng)建一個(gè)類似于信標(biāo)性質(zhì)的指針 curNext 來(lái)記錄一下 cur 的下一個(gè)節(jié)點(diǎn),之后再 free 掉 cur,這樣就可以移動(dòng) cur 了。
③ 最后為了防止野指針,還需要把頭指針和尾指針都置為空。
0x02 判斷隊(duì)列是否為空(HeapIsEmpty)
?? Queue.h
bool QueueIsEmpty(Queue* pQ); //判斷隊(duì)列是否為空
?? 解讀:布爾值,返回 true 或 false
?? Queue.c
/* 判斷隊(duì)列是否為空 */ bool QueueIsEmpty(Queue* pQ) { assert(pQ); //防止傳入的pQ為空 return pQ->pHead == NULL; //如果成立則為True,不成立則為False }
?? 解讀:
① 首先斷言防止傳入的pQ為空。
② 判斷隊(duì)列是否為空,可以直接返回,巧妙地利用布爾類型的特性。如果 pQ->pHead == NULL 成立則為真,會(huì)返回 true;不成立則為假,會(huì)返回 false。
0x03 入隊(duì)(QueuePush)
?? Queue.h
void QueuePush(Queue* pQ, QueueDataType x); //入隊(duì)
?? Queue.c
/* 入隊(duì):隊(duì)尾入數(shù)據(jù),對(duì)頭出數(shù)據(jù)。如果是第一個(gè)入隊(duì)的則既要當(dāng)頭又當(dāng)尾 */ void QueuePush(Queue* pQ, QueueDataType x) { assert(pQ); //防止傳入的pQ為空 /* 創(chuàng)建新節(jié)點(diǎn):創(chuàng)建一個(gè)大小為QueueNode的空間 */ QueueNode* new_node = (QueueNode*)malloc(sizeof(QueueNode)); /* 檢查malloc */ if(new_node == NULL) { printf("malloc failed!\n"); exit(-1); } /* 放置 */ new_node->data = x; //待插入的數(shù)據(jù) new_node->next = NULL; //默認(rèn)為空 /* 入隊(duì): *【思路草圖】 * 情況1:隊(duì)列為空:既當(dāng)頭又當(dāng)尾 * [new_node] * ↑ ↑ * pHead pTail * * 情況2:隊(duì)列不為空:隊(duì)尾入數(shù)據(jù) * [] -> [] -> [] -> [] -> [new_node] * pHead pTail pTail->next * ↓ ↑ * ----------→ pTail(更新尾指針) */ if(pQ->pHead == NULL) { //情況1: 隊(duì)列為空 pQ->pHead = pQ->pTail = new_node; // 既當(dāng)頭又當(dāng)尾 } else { //情況2: 隊(duì)列不為空 pQ->pTail->next = new_node; // 在現(xiàn)有尾的后一個(gè)節(jié)點(diǎn)放置new_node pQ->pTail = new_node; // 更新pTail,使它指向新的尾 } }
?? 解讀:
① 首先斷言防止傳入的pQ為空。
② 我們首先要?jiǎng)?chuàng)建新節(jié)點(diǎn)。通過(guò) malloc 動(dòng)態(tài)內(nèi)存開辟一塊 QueueNode 大小的空間,都學(xué)到這里了大家想必都養(yǎng)成了檢查 malloc 的好習(xí)慣了吧?。最后放置數(shù)據(jù)嗎,將待插入的數(shù)據(jù) x 交給 data,next 默認(rèn)置空,和之前學(xué)鏈表一樣,這里就不過(guò)多贅述了。
③ 新節(jié)點(diǎn)創(chuàng)建好后,我們可以開始寫入隊(duì)的操作了。首先要理解隊(duì)列的性質(zhì):隊(duì)尾入數(shù)據(jù),隊(duì)頭出數(shù)據(jù)。這里既然是入隊(duì),就要在對(duì)尾后面進(jìn)行插入。這里我們還要考慮到如果隊(duì)列為空的情況,這時(shí)我們要把頭指針和尾指針都交付給 new_node 。為了理清思路,我們可以畫一個(gè)思路草圖來(lái)幫助我們更好地理解:
有了這個(gè)圖,我們就可以清楚地實(shí)現(xiàn)了:
if(pQ->pHead == NULL) { //情況1: 隊(duì)列為空 pQ->pHead = pQ->pTail = new_node; // 既當(dāng)頭又當(dāng)尾 } else { //情況2: 隊(duì)列不為空 pQ->pTail->next = new_node; // 在現(xiàn)有尾的后一個(gè)節(jié)點(diǎn)放置new_node pQ->pTail = new_node; // 更新pTail,使它指向新的尾 }
當(dāng)隊(duì)列為空時(shí),令頭指針和尾指針都指向 new_node ,當(dāng)隊(duì)列不為空時(shí),再尾部地下一個(gè)節(jié)點(diǎn)放置 new_node?,隨后再更新尾指針讓其指向新的尾(new_node 的位置)。
0x04 出隊(duì)(QueuePop)
?? Queue.h
void QueuePop(Queue* pQ); //出隊(duì)
?? Queue.c
/* 出隊(duì):隊(duì)尾入數(shù)據(jù),對(duì)頭出數(shù)據(jù) */ void QueuePop(Queue* pQ) { assert(pQ); //防止傳入的pQ為空 assert(!QueueIsEmpty(pQ)); //防止隊(duì)列為空 /* 出隊(duì): *【思路草圖】 * [free] -> [] -> [] -> [] * pHead headNext * ↓ ↑ * -------→ pHead(更新頭指針) */ QueueNode* headNext = pQ->pHead->next; //信標(biāo)指針HeadNext free(pQ->pHead); pQ->pHead = headNext; //更新頭 /* 如果隊(duì)內(nèi)都被刪完了,不處理pTail就會(huì)帶來(lái)野指針的隱患 * 【思路草圖】 * NULL 已經(jīng)被free掉的內(nèi)存! * ↑ ↑ (野指針警告) * pHead(因?yàn)镠eadNext是NULL) pTail */ if(pQ->pHead == NULL) //如果pHead為空 pQ->pTail = NULL; //處理一下尾指針,將尾指針置空 }
?? 解讀:
① 首先斷言防止傳入的 pQ 為空,這里還要放置隊(duì)列為空,如果隊(duì)列為空還要求出隊(duì)的話會(huì)出問(wèn)題的,所以這里要斷言一下 QueueIsEmpty 為假。
② 思路草圖如下:
出數(shù)據(jù)需要釋放,和銷毀一樣,這里使用一個(gè)類似于信標(biāo)性質(zhì)的指針來(lái)記錄 pHead 的下一個(gè)節(jié)點(diǎn),之后我們就可以大膽地釋放 pHead 而不用擔(dān)心找不到了。free 掉之后更新頭即可,令頭指針指向 headNext 即可。?
?? 注意:這里還要考慮一個(gè)問(wèn)題,如果隊(duì)內(nèi)都被刪完了,pHead 往后走指向空,但是 pTail 仍然指向那塊已經(jīng)被 free 掉的空間。pTail 就是一個(gè)典型的野指針。
我們可以不用擔(dān)心 pHead,因?yàn)楹竺鏇](méi)有數(shù)據(jù)他會(huì)自然指向 NULL,但是我們這里得關(guān)注 pTail !我們需要手動(dòng)處理一下它:
如果 pHead 為空,我們就把 pTail 也置為空即可。
if(pQ->pHead == NULL) //如果pHead為空 pQ->pTail = NULL; //處理一下尾指針,將尾指針置空
0x05?返回隊(duì)頭數(shù)據(jù)(QueueFront)
?? Queue.h
QueueDataType QueueFront(Queue* pQ); //返回隊(duì)頭數(shù)據(jù)
?? Queue.c
/* 返回隊(duì)頭數(shù)據(jù) */ QueueDataType QueueFront(Queue* pQ) { assert(pQ); //防止傳入的pQ為空 assert(!QueueIsEmpty(pQ)); //防止隊(duì)列為空 return pQ->pHead->data; }
?? 解讀:
① 首先斷言防止傳入的 pQ 為空,這里我們還是要斷言一下 QueueIsEmpty 為假,因?yàn)槿绻?duì)內(nèi)沒(méi)有數(shù)據(jù),還返回個(gè)錘子數(shù)據(jù)呢。
② 這里直接返回頭的數(shù)據(jù)即可,特別簡(jiǎn)單沒(méi)有什么好講的。
0x06?返回隊(duì)尾數(shù)據(jù)(QueueBack)
?? Queue.h
QueueDataType QueueBack(Queue* pQ); //返回隊(duì)尾數(shù)據(jù)
?? Queue.c
/* 返回隊(duì)尾數(shù)據(jù) */ QueueDataType QueueBack(Queue* pQ) { assert(pQ); //防止傳入的pQ為空 assert(!QueueIsEmpty(pQ)); //防止隊(duì)列為空 return pQ->pTail->data; }
?? 解讀:
① 首先斷言防止傳入的 pQ 為空,斷言一下 QueueIsEmpty 為假。
② 這里直接返回隊(duì)尾的數(shù)據(jù)即可。
0x07?求隊(duì)列大小(QueueSize)
?? Queue.h
int QueueSize(Queue* pQ); //求隊(duì)列大小
?? Queue.c
/* 求隊(duì)列大?。河?jì)數(shù)器法 */ int QueueSize(Queue* pQ) { assert(pQ); //防止傳入的pQ為空 int count = 0; //計(jì)數(shù)器 QueueNode* cur = pQ->pHead; //創(chuàng)建遍歷指針cur while(cur != NULL) { ++count; //計(jì)數(shù)+1 cur = cur->next; //移動(dòng)指針cur } return count; }
?? 解讀:這里我們采用計(jì)數(shù)器法來(lái)求大小即可,調(diào)用一次就是 O(N)?,也沒(méi)什么不好的。
① 首先斷言防止傳入的 pQ 為空。
② 創(chuàng)建計(jì)數(shù)器變量和遍歷指針 cur,遍歷整個(gè)隊(duì)列并計(jì)數(shù),最后返回計(jì)數(shù)的結(jié)果即可。
0x08 完整代碼
?? Queue.h
#pragma once #include <stdio.h> #include <stdlib.h> #include <assert.h> #include <stdbool.h> typedef int QueueDataType; //隊(duì)列類型 typedef struct QueueNode { struct QueueNode* next; //指向下一個(gè)節(jié)點(diǎn) QueueDataType data; //數(shù)據(jù) } QueueNode; typedef struct Queue { QueueNode* pHead; //頭指針 QueueNode* pTail; //尾指針 } Queue; void QueueInit(Queue* pQ); //隊(duì)列初始化 void QueueDestroy(Queue* pQ); //銷毀隊(duì)列 bool QueueIsEmpty(Queue* pQ); //判斷隊(duì)列是否為空 void QueuePush(Queue* pQ, QueueDataType x); //入隊(duì) void QueuePop(Queue* pQ); //出隊(duì) QueueDataType QueueFront(Queue* pQ); //返回隊(duì)頭數(shù)據(jù) QueueDataType QueueBack(Queue* pQ); //返回隊(duì)尾數(shù)據(jù) int QueueSize(Queue* pQ); //求隊(duì)列大小
?? Queue.c
#include <Queue.h> /* 隊(duì)列初始化:將頭尾指針置為NULL */ void QueueInit(Queue* pQ) { assert(pQ); //防止傳入的pQ為空 pQ->pHead = pQ->pTail = NULL; //將頭尾指針置空 } /* 銷毀隊(duì)列:free掉所有隊(duì)列元素并將頭尾置空 */ void QueueDestroy(Queue* pQ) { assert(pQ); //防止傳入的pQ為空 QueueNode* cur = pQ->pHead; //創(chuàng)建遍歷指針cur while(cur != NULL) { //cur不為空就進(jìn)入循環(huán) QueueNode* curNext = cur->next; //信標(biāo)指針curNext,防止釋放cur后找不到其下一個(gè)節(jié)點(diǎn) free(cur); //釋放cur當(dāng)前指向的節(jié)點(diǎn) cur = curNext; //移動(dòng)指針cur } pQ->pHead = pQ->pTail = NULL; //置空干掉野指針 } /* 判斷隊(duì)列是否為空 */ bool QueueIfEmpty(Queue* pQ) { assert(pQ); //防止傳入的pQ為空 return pQ->pHead == NULL; //如果成立則為True,不成立則為False } /* 入隊(duì):隊(duì)尾入數(shù)據(jù),對(duì)頭出數(shù)據(jù)。如果是第一個(gè)入隊(duì)的則既要當(dāng)頭又當(dāng)尾 */ void QueuePush(Queue* pQ, QueueDataType x) { assert(pQ); //防止傳入的pQ為空 /* 創(chuàng)建新節(jié)點(diǎn):創(chuàng)建一個(gè)大小為QueueNode的空間 */ QueueNode* new_node = (QueueNode*)malloc(sizeof(QueueNode)); /* 檢查malloc */ if(new_node == NULL) { printf("malloc failed!\n"); exit(-1); } /* 放置 */ new_node->data = x; //待插入的數(shù)據(jù) new_node->next = NULL; //默認(rèn)為空 /* 入隊(duì): *【思路草圖】 * 情況1:隊(duì)列為空:既當(dāng)頭又當(dāng)尾 * [new_node] * ↑ ↑ * pHead pTail * * 情況2:隊(duì)列不為空:隊(duì)尾入數(shù)據(jù) * [] -> [] -> [] -> [] -> [new_node] * pHead pTail pTail->next * ↓ ↑ * ----------→ pTail(更新尾指針) */ if(pQ->pHead == NULL) { //情況1: 隊(duì)列為空 pQ->pHead = pQ->pTail = new_node; // 既當(dāng)頭又當(dāng)尾 } else { //情況2: 隊(duì)列不為空 pQ->pTail->next = new_node; // 在現(xiàn)有尾的后一個(gè)節(jié)點(diǎn)放置new_node pQ->pTail = new_node; // 更新pTail,使它指向新的尾 } } /* 出隊(duì):隊(duì)尾入數(shù)據(jù),對(duì)頭出數(shù)據(jù) */ void QueuePop(Queue* pQ) { assert(pQ); //防止傳入的pQ為空 assert(!QueueIsEmpty(pQ)); //防止隊(duì)列為空 /* 出隊(duì): *【思路草圖】 * [free] -> [] -> [] -> [] * pHead headNext * ↓ ↑ * -------→ pHead(更新頭指針) */ QueueNode* headNext = pQ->pHead->next; //信標(biāo)指針HeadNext,防止釋放pHead后找不到其下一個(gè)節(jié)點(diǎn) free(pQ->pHead); pQ->pHead = headNext; //更新頭 /* 如果隊(duì)內(nèi)都被刪完了,不處理pTail就會(huì)帶來(lái)野指針的隱患 * 【思路草圖】 * NULL 已經(jīng)被free掉的空間! * ↑ ↑ (野指針) * pHead(因?yàn)镠eadNext是NULL) pTail */ if(pQ->pHead == NULL) //如果pHead為空 pQ->pTail = NULL; //處理一下尾指針,將尾指針置空 } /* 返回隊(duì)頭數(shù)據(jù) */ QueueDataType QueueFront(Queue* pQ) { assert(pQ); //防止傳入的pQ為空 assert(!QueueIsEmpty(pQ)); //防止隊(duì)列為空 return pQ->pHead->data; } /* 返回隊(duì)尾數(shù)據(jù) */ QueueDataType QueueBack(Queue* pQ) { assert(pQ); //防止傳入的pQ為空 assert(!QueueIsEmpty(pQ)); //防止隊(duì)列為空 return pQ->pTail->data; } /* 求隊(duì)列大?。河?jì)數(shù)器法 */ int QueueSize(Queue* pQ) { assert(pQ); //防止傳入的pQ為空 int count = 0; //計(jì)數(shù)器 QueueNode* cur = pQ->pHead; //創(chuàng)建遍歷指針cur while(cur != NULL) { ++count; //計(jì)數(shù)+1 cur = cur->next; //移動(dòng)指針cur } return count; }
?? Test.c
#include "Queue.h" void TestQueue1() { Queue q; 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); } void TestQueue2() { Queue q; QueueInit(&q); QueuePush(&q, 1); QueuePush(&q, 2); QueuePush(&q, 3); QueuePush(&q, 4); //假設(shè)先入了1 2,讓1出來(lái),再繼續(xù)入,它的順序還是不會(huì)變。 // 永遠(yuǎn)保持先進(jìn)先出的,無(wú)論是入了兩個(gè)出兩個(gè),再入再出,還是全部入完了再出,都是不會(huì)變的。這就是隊(duì)列的性質(zhì) while(!QueueIsEmpty(&q)) { QueueDataType front = QueueFront(&q); printf("%d ", front); QueuePop(&q); //pop掉去下一個(gè) } printf("\n"); QueueDestroy(&q); } int main(void) { TestQueue2(); return 0; }
參考資料:
Microsoft. MSDN(Microsoft Developer Network)[EB/OL]. []. .
百度百科[EB/OL]. []. https://baike.baidu.com/.
?? 筆者:王亦優(yōu)
?? 更新: 2021.11.17
? 勘誤: 無(wú)
?? 聲明: 由于作者水平有限,本文有錯(cuò)誤和不準(zhǔn)確之處在所難免,本人也很想知道這些錯(cuò)誤,懇望讀者批評(píng)指正!
本篇完。
到此這篇關(guān)于C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)系列隊(duì)列篇的文章就介紹到這了,更多相關(guān)C語(yǔ)言 隊(duì)列內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
C語(yǔ)言連續(xù)生成多個(gè)隨機(jī)數(shù)實(shí)現(xiàn)可限制范圍
這篇文章主要介紹了C語(yǔ)言連續(xù)生成多個(gè)隨機(jī)數(shù)實(shí)現(xiàn)可限制范圍,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2021-01-01c++連接mysql5.6的出錯(cuò)問(wèn)題總結(jié)
下面小編就為大家?guī)?lái)一篇c++連接mysql5.6的出錯(cuò)問(wèn)題總結(jié)。小編覺(jué)得挺不錯(cuò)的,現(xiàn)在就分享給大家,也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧,祝大家游戲愉快哦2016-12-12利用Qt實(shí)現(xiàn)獲取計(jì)算機(jī)的硬件信息
在開發(fā)時(shí),常常會(huì)需要用到計(jì)算機(jī)的相關(guān)信息。利用這些信息,我們可以開發(fā)一些輔助模塊。本文將利用Qt實(shí)現(xiàn)獲取計(jì)算機(jī)的硬件信息,感興趣的可以嘗試一下2022-12-12C語(yǔ)言對(duì)數(shù)組元素進(jìn)行冒泡排序的實(shí)現(xiàn)
這篇文章主要介紹了C語(yǔ)言對(duì)數(shù)組元素進(jìn)行冒泡排序的實(shí)現(xiàn),文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2021-02-02