C語(yǔ)言超詳細(xì)講解隊(duì)列的實(shí)現(xiàn)及代碼
前言
隊(duì)列的概念
- 隊(duì)列:只允許在一端進(jìn)行插入數(shù)據(jù)操作,在另一端進(jìn)行刪除數(shù)據(jù)操作的特殊線性表,隊(duì)列具有先進(jìn)先出FIFO(First In First Out)
- 入隊(duì)列:進(jìn)行插入操作的一端稱為隊(duì)尾
- 出隊(duì)列:進(jìn)行刪除操作的一端稱為隊(duì)頭
隊(duì)列和前文所學(xué)的棧還是有一定區(qū)別的,隊(duì)列明確指出先進(jìn)先出。假如說(shuō)一個(gè)隊(duì)列的入隊(duì)順序?yàn)锳 B C D,那么出隊(duì)順序一定為A B C D,因?yàn)闊o(wú)論你是在A進(jìn)去再出來(lái),然后B進(jìn)去再出來(lái)接著CD進(jìn)去再出來(lái)或者類似的,都不會(huì)影響它最終的出隊(duì)順序A B C D。這點(diǎn)和棧還是有區(qū)別的,畢竟棧是后進(jìn)先出。
隊(duì)列的結(jié)構(gòu)
隊(duì)列的應(yīng)用場(chǎng)景
隊(duì)列:
- 公平排隊(duì)
- 廣度優(yōu)先遍歷 ……
棧:
- 解決括號(hào)匹配
- 逆波蘭表達(dá)式求解
- 遞歸改非遞歸 ……
隊(duì)列的實(shí)現(xiàn)
- 在實(shí)現(xiàn)之前,首先得考慮用哪種結(jié)構(gòu)好,是用數(shù)組結(jié)構(gòu)還是鏈?zhǔn)浇Y(jié)構(gòu)呢?上文的棧我們使用的是數(shù)組結(jié)構(gòu),難道隊(duì)列也要用嗎?
- 其實(shí)不然。應(yīng)該使用鏈?zhǔn)浇Y(jié)構(gòu)。前文棧刪除數(shù)據(jù)不需要挪動(dòng)數(shù)據(jù),使用數(shù)組結(jié)構(gòu)即可滿足需求,而隊(duì)列在刪除數(shù)據(jù)時(shí)需要把后面的數(shù)據(jù)挪到前面,使用鏈?zhǔn)浇Y(jié)構(gòu)非常容易實(shí)現(xiàn),只需改變節(jié)點(diǎn)指向即可,而數(shù)組結(jié)構(gòu)想要實(shí)現(xiàn)挪動(dòng)數(shù)據(jù)則非常麻煩。綜上,使用鏈?zhǔn)浇Y(jié)構(gòu)是最優(yōu)的。此外,單鏈表即可滿足需求,不需要使用其余較為復(fù)雜的鏈?zhǔn)浇Y(jié)構(gòu)。
創(chuàng)建隊(duì)列結(jié)構(gòu)
思路:
這里要定義兩個(gè)結(jié)構(gòu)體,除了要定義1個(gè)鏈?zhǔn)浇Y(jié)構(gòu)來(lái)記錄各個(gè)節(jié)點(diǎn)外,還要定義一個(gè)結(jié)構(gòu)來(lái)記錄隊(duì)頭和隊(duì)尾。以此方便后續(xù)的隊(duì)尾入數(shù)據(jù),隊(duì)頭出數(shù)據(jù)。
Queue.h 文件:
//創(chuàng)建隊(duì)列結(jié)構(gòu) typedef int QDataType; //方便后續(xù)更改存儲(chǔ)數(shù)據(jù)類型,本文以int為例 //創(chuàng)建隊(duì)列節(jié)點(diǎn) typedef struct QueueNode { QDataType data; //存儲(chǔ)數(shù)據(jù) struct QueueNode* next; //記錄下一個(gè)節(jié)點(diǎn) }QNode; //保存隊(duì)頭和隊(duì)尾 typedef struct Queue { QNode* head; //頭指針 QNode* tail; //尾指針 }Queue;
隊(duì)列初始化
思路:
隊(duì)列可以為空,但是管理頭指針和尾指針的結(jié)構(gòu)體不能為空,所以一開(kāi)始就要斷言。其次,在插入數(shù)據(jù)前,隊(duì)列肯定是空的,所以直接把頭指針和尾指針置空即可。
Queue.h 文件:
//初始化隊(duì)列 void QueueInit(Queue* pq);
Queue.c 文件:
//初始化隊(duì)列 void QueueInit(Queue* pq) { assert(pq); pq->head = pq->tail = NULL; }
隊(duì)列銷毀
思路:
銷毀隊(duì)列就是把隊(duì)列的每個(gè)數(shù)據(jù)都銷毀掉,那么需要遍歷鏈表進(jìn)行挨個(gè)銷毀free。首先定義一個(gè)cur指針為pq->head,用來(lái)保存第一個(gè)數(shù)據(jù),遍歷cur,如果不為空,就free。最后把tail和head置空即可。
Queue.h 文件:
//銷毀隊(duì)列 void QueueDestory(Queue* pq);
Queue.c 文件:
//銷毀隊(duì)列 void QueueDestory(Queue* pq) { assert(pq); QNode* cur = pq->head; while (cur) { QNode* next = cur->next; free(cur); cur = next; } pq->head = pq->tail = NULL; }
入隊(duì)列
思路:
入隊(duì)列其實(shí)很簡(jiǎn)單,只需要尾插即可,首先要新創(chuàng)建一個(gè)節(jié)點(diǎn)來(lái)保存新插入的數(shù)據(jù)。但是在尾插之前要考慮如果一開(kāi)始隊(duì)列沒(méi)有數(shù)據(jù),為空,那么只需要把head和tail節(jié)點(diǎn)指向新節(jié)點(diǎn)newnode節(jié)點(diǎn)即可。相反的,如果一開(kāi)始就有數(shù)據(jù),那么只需正常尾插把tail的next指向新節(jié)點(diǎn)newnode,再把newnode賦給tail即可。
Queue.h 文件:
//入隊(duì)列 void QueuePush(Queue* pq, QDataType x);
Queue.c 文件:
//入隊(duì)列 void QueuePush(Queue* pq, QDataType x) { assert(pq); //創(chuàng)建一個(gè)新節(jié)點(diǎn)保存數(shù)據(jù) QNode* newnode = (QNode*)malloc(sizeof(QNode)); //暴力檢測(cè)newnode,因?yàn)閙alloc的都要檢測(cè) assert(newnode); newnode->next = NULL; newnode->data = x; //如果一開(kāi)始沒(méi)有數(shù)據(jù),為空的情況 if (pq->tail == NULL) { assert(pq->head == NULL); pq->head = pq->tail = newnode; } else { pq->tail->next = newnode; pq->tail = newnode; } }
出隊(duì)列
思路:
特殊情況:
這里在刪除數(shù)據(jù)時(shí),首先要考慮特殊情況,當(dāng)刪到只剩一個(gè)數(shù)據(jù)時(shí),再刪一次,此時(shí)數(shù)據(jù)是沒(méi)了,不過(guò)head為空了,而tail變成野指針了,為了避免此現(xiàn)象的產(chǎn)生,單獨(dú)討論并置空head和tail即可。
一般情況:
此時(shí)只需要定義一個(gè)next指針保存head的下一個(gè)節(jié)點(diǎn),將head移動(dòng)到next即可,并把舊的head置空。
Queue.h 文件:
//出隊(duì)列 void QueuePop(Queue* pq);
Queue.c 文件:
//出隊(duì)列 void QueuePop(Queue* pq) { assert(pq); assert(pq->head && pq->tail); //tail和head均不能為空 //特殊:當(dāng)刪到head=tail的位置時(shí) if (pq->head->next == NULL) { free(pq->head); pq->head = pq->tail = NULL; } //一般情況 else { //保存head的下一個(gè)節(jié)點(diǎn) QNode* next = pq->head->next; free(pq->head); pq->head = next; } }
隊(duì)列判空
思路:
如果head為空或者tail為空都是判空的條件,直接返回即可。
Queue.h 文件:
//判空 bool QueueEmpty(Queue* pq);
Queue.c 文件:
//判空 bool QueueEmpty(Queue* pq) { assert(pq); return pq->head == NULL; }
獲取隊(duì)列元素個(gè)數(shù)
思路:
求元素個(gè)數(shù)其實(shí)不難,只需要定義一個(gè)cur指針為第一個(gè)數(shù)據(jù)pq->head,定義變量size來(lái)記錄個(gè)數(shù)。依次遍歷cur,不為空,size就++。這種遍歷的思想不復(fù)雜,但時(shí)間復(fù)雜度達(dá)到O(N),不是太好,想要O(1)的話可以直接在當(dāng)初定義結(jié)構(gòu)體時(shí)多定義一個(gè)size變量,專門(mén)用來(lái)記錄有效元素個(gè)數(shù),每次入隊(duì)列size++,出隊(duì)列size--。這樣實(shí)現(xiàn)是比較好的,不過(guò)為了封裝成一個(gè)獨(dú)立模塊,還是采用遍歷的方式。如下:
Queue.h 文件:
//獲取有效元素個(gè)數(shù) size_t QueueSize(Queue* pq);
Queue.c 文件:
//獲取有效元素個(gè)數(shù) size_t QueueSize(Queue* pq) { assert(pq); QNode* cur = pq->head; size_t size = 0; while (cur) { size++; cur = cur->next; } return size; }
獲取隊(duì)列頭部元素
思路:
首先要斷言頭部不能為空,如果頭部都為空了,那還怎么能獲得頭部元素,其次直接返回頭部head的數(shù)據(jù)即可。
Queue.h 文件:
//獲取隊(duì)頭元素 QDataType QueueFront(Queue* pq);
Queue.c 文件:
//獲取隊(duì)頭元素 QDataType QueueFront(Queue* pq) { assert(pq); assert(pq->head); //頭部不能為空 return pq->head->data; }
獲取隊(duì)列尾部元素
思路:
有了獲取隊(duì)頭元素的經(jīng)驗(yàn),隊(duì)尾就更簡(jiǎn)單了,把head換位tail即可,結(jié)構(gòu)與上文一樣。
Queue.h 文件:
//獲取隊(duì)尾元素 QDataType QueueBack(Queue* pq);
Queue.c 文件:
//獲取隊(duì)尾元素 QDataType QueueBack(Queue* pq) { assert(pq); assert(pq->tail); //尾部不能為空 return pq->tail->data; }
總代碼
Queue.h 文件
#pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h> #include<stdbool.h> //創(chuàng)建隊(duì)列結(jié)構(gòu) typedef int QDataType; //方便后續(xù)更改存儲(chǔ)數(shù)據(jù)類型,本文以int為例 //創(chuàng)建隊(duì)列節(jié)點(diǎn) typedef struct QueueNode { QDataType data; //存儲(chǔ)數(shù)據(jù) struct QueueNode* next; //記錄下一個(gè)節(jié)點(diǎn) }QNode; //保存隊(duì)頭和隊(duì)尾 typedef struct Queue { QNode* head; //頭指針 QNode* tail; //尾指針 }Queue; //初始化隊(duì)列 void QueueInit(Queue* pq); //銷毀隊(duì)列 void QueueDestory(Queue* pq); //入隊(duì)列 void QueuePush(Queue* pq, QDataType x); //出隊(duì)列 void QueuePop(Queue* pq); //判空 bool QueueEmpty(Queue* pq); //獲取有效元素個(gè)數(shù) size_t QueueSize(Queue* pq); //獲取隊(duì)頭元素 QDataType QueueFront(Queue* pq); //獲取隊(duì)尾元素 QDataType QueueBack(Queue* pq);
Queue.c 文件
#define _CRT_SECURE_NO_WARNINGS 1 #include"Queue.h" //初始化隊(duì)列 void QueueInit(Queue* pq) { assert(pq); pq->head = pq->tail = NULL; } //銷毀隊(duì)列 void QueueDestory(Queue* pq) { assert(pq); QNode* cur = pq->head; while (cur) { QNode* next = cur->next; free(cur); cur = next; } pq->head = pq->tail = NULL; } //入隊(duì)列 void QueuePush(Queue* pq, QDataType x) { assert(pq); //創(chuàng)建一個(gè)新節(jié)點(diǎn)保存數(shù)據(jù) QNode* newnode = (QNode*)malloc(sizeof(QNode)); //暴力檢測(cè)newnode,因?yàn)閙alloc的都要檢測(cè) assert(newnode); newnode->next = NULL; newnode->data = x; //如果一開(kāi)始沒(méi)有數(shù)據(jù),為空的情況 if (pq->tail == NULL) { assert(pq->head == NULL); pq->head = pq->tail = newnode; } else { pq->tail->next = newnode; pq->tail = newnode; } } //出隊(duì)列 void QueuePop(Queue* pq) { assert(pq); assert(pq->head && pq->tail); //tail和head均不能為空 //特殊:當(dāng)刪到head=tail的位置時(shí) if (pq->head->next == NULL) { free(pq->head); pq->head = pq->tail = NULL; } //一般情況 else { //保存head的下一個(gè)節(jié)點(diǎn) QNode* next = pq->head->next; free(pq->head); pq->head = next; } } //判空 bool QueueEmpty(Queue* pq) { assert(pq); return pq->head == NULL; } //獲取有效元素個(gè)數(shù) size_t QueueSize(Queue* pq) { assert(pq); QNode* cur = pq->head; size_t size = 0; while (cur) { size++; cur = cur->next; } return size; } //獲取隊(duì)頭元素 QDataType QueueFront(Queue* pq) { assert(pq); assert(pq->head); //頭部不能為空 return pq->head->data; } //獲取隊(duì)尾元素 QDataType QueueBack(Queue* pq) { assert(pq); assert(pq->tail); //尾部不能為空 return pq->tail->data; }
Test.c 文件
#define _CRT_SECURE_NO_WARNINGS 1 #include"Queue.h" void TestQueue() { Queue q; QueueInit(&q); //插入數(shù)據(jù) QueuePush(&q, 1); QueuePush(&q, 2); QueuePush(&q, 3); QueuePush(&q, 4); //打印 while (!QueueEmpty(&q)) { printf("%d ", QueueFront(&q)); QueuePop(&q); } printf("\n"); } int main() { TestQueue(); return 0; }
到此這篇關(guān)于C語(yǔ)言超詳細(xì)講解隊(duì)列的實(shí)現(xiàn)及代碼的文章就介紹到這了,更多相關(guān)C語(yǔ)言 隊(duì)列的實(shí)現(xiàn)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
C語(yǔ)言中進(jìn)程信號(hào)集的相關(guān)操作函數(shù)詳解
這篇文章主要介紹了C語(yǔ)言中進(jìn)程信號(hào)集的相關(guān)操作函數(shù)詳解,包括sigismember函數(shù)和sigfillset函數(shù)以及sigemptyset函數(shù)的用法,需要的朋友可以參考下2015-09-09C++ read函數(shù)讀入int整形數(shù)據(jù)
這篇文章主要介紹了C++ read函數(shù)讀入int整形數(shù)據(jù)的相關(guān)資料,需要的朋友可以參考下2016-07-07C++實(shí)例分析講解臨時(shí)對(duì)象與右值引用的用法
對(duì)性能來(lái)說(shuō),許多的問(wèn)題都需要和出現(xiàn)頻率及本身執(zhí)行一次的開(kāi)銷掛鉤,有些問(wèn)題雖然看似比較開(kāi)銷較大,但是很少會(huì)執(zhí)行到,那也不會(huì)對(duì)程序有大的影響;同樣一個(gè)很小開(kāi)銷的函數(shù)執(zhí)行很頻繁,同樣會(huì)對(duì)程序的執(zhí)行效率有很大影響。本章中作者主要根據(jù)臨時(shí)對(duì)象來(lái)闡述這樣一個(gè)觀點(diǎn)2022-08-08