C語言數(shù)據(jù)結(jié)構(gòu)系列隊列篇
一、隊列（Queue）
0x00 隊列的概念
?? 概念：
① 隊列只允許在一端進行插入數(shù)據(jù)操作，在另一端進行刪除數(shù)據(jù)操作的特殊線性表。
② 入隊列，進行插入操作的一端稱為 隊尾。出隊列，進行刪除操作的一端稱為 隊頭。
③ 隊列中的元素遵循先進先出的原則，即 FIFO?原則（First In First Out）
0x01 隊列的結(jié)構(gòu)
?? 結(jié)構(gòu)：
二、隊列的定義
0x00 鏈式隊列
typedef int QueueDataType; //隊列類型
typedef struct QueueNode {
struct QueueNode* next; //指向下一個節(jié)點
QueueDataType data; //數(shù)據(jù)
} QueueNode;
typedef struct Queue {
QueueNode* pHead; //頭指針
QueueNode* pTail; //尾指針
} Queue;
? 為什么不使用單鏈表？
?? 單鏈表我們只定義了一個指針指向頭，沒有定義尾指針。因為定義尾指針解決不了問題，比如尾插尾刪。所以我們沒有必要定義一個結(jié)構(gòu)體把他們封到一起。這里我們再定義一個頭指針 head 一個尾指針 tail?，這兩個指針才有意義。因為根據(jù)隊列的性質(zhì)，我們只會在隊尾插，不會再隊尾刪。所以這個尾指針的價值就得到了完美的體現(xiàn)，實際中定義幾個指針是看你的需求確定的。
0x02?接口函數(shù)
?? 這是需要實現(xiàn)幾個接口函數(shù)：
void QueueInit(Queue* pQ); //隊列初始化 void QueueDestroy(Queue* pQ); //銷毀隊列 bool QueueIsEmpty(Queue* pQ); //判斷隊列是否為空 void QueuePush(Queue* pQ, QueueDataType x); //入隊 void QueuePop(Queue* pQ); //出隊 QueueDataType QueueFront(Queue* pQ); //返回隊頭數(shù)據(jù) QueueDataType QueueBack(Queue* pQ); //返回隊尾數(shù)據(jù) int QueueSize(Queue* pQ); //求隊列大小
三、隊列的實現(xiàn)
0x00 隊列初始化（QueueInit）
?? Queue.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef int QueueDataType; //隊列類型
typedef struct QueueNode {
struct QueueNode* next; //指向下一個節(jié)點
QueueDataType data; //數(shù)據(jù)
} QueueNode;
typedef struct Queue {
QueueNode* pHead; //頭指針
QueueNode* pTail; //尾指針
} Queue;
void QueueInit(Queue* pQ); //隊列初始化
?? Queue.c
/* 隊列初始化：將頭尾指針置為NULL */
void QueueInit(Queue* pQ) {
assert(pQ); //防止傳入的pQ為空
pQ->pHead = pQ->pTail = NULL; //將頭尾指針置空
}
?? 解析：首先使用斷言防止傳入的pQ為空。初始化只需要把頭指針和尾指針都置成空即可。
0x01 銷毀隊列（QueueDestroy）
/* 銷毀隊列：free掉所有隊列元素并將頭尾置空 */
void QueueDestroy(Queue* pQ) {
assert(pQ); //防止傳入的pQ為空
QueueNode* cur = pQ->pHead; //創(chuàng)建遍歷指針cur
while(cur != NULL) { //cur不為空就進入循環(huán)
QueueNode* curNext = cur->next; //信標指針curNext，防止釋放cur后找不到其下一個節(jié)點
free(cur); //釋放cur當前指向的節(jié)點
cur = curNext; //移動指針cur
}
pQ->pHead = pQ->pTail = NULL; //置空干掉野指針
}
?? 解讀：
① 首先斷言防止傳入的pQ為空。
② 銷毀要把所有節(jié)點都釋放掉，我們創(chuàng)建遍歷指針 cur 遍歷整個隊列。既然要釋放 cur 指向的節(jié)點，為了防止釋放 cur 之后找不到其下一個節(jié)點導致無法移動，我們這里創(chuàng)建一個類似于信標性質(zhì)的指針 curNext 來記錄一下 cur 的下一個節(jié)點，之后再 free 掉 cur，這樣就可以移動 cur 了。
③ 最后為了防止野指針，還需要把頭指針和尾指針都置為空。
0x02 判斷隊列是否為空（HeapIsEmpty）
?? Queue.h
bool QueueIsEmpty(Queue* pQ); //判斷隊列是否為空
?? 解讀：布爾值，返回 true 或 false
?? Queue.c
/* 判斷隊列是否為空 */
bool QueueIsEmpty(Queue* pQ) {
assert(pQ); //防止傳入的pQ為空
return pQ->pHead == NULL; //如果成立則為True，不成立則為False
}
?? 解讀：
① 首先斷言防止傳入的pQ為空。
② 判斷隊列是否為空，可以直接返回，巧妙地利用布爾類型的特性。如果 pQ->pHead == NULL 成立則為真，會返回 true；不成立則為假，會返回 false。
0x03 入隊（QueuePush）
?? Queue.h
void QueuePush(Queue* pQ, QueueDataType x); //入隊
?? Queue.c
/* 入隊：隊尾入數(shù)據(jù)，對頭出數(shù)據(jù)。如果是第一個入隊的則既要當頭又當尾 */
void QueuePush(Queue* pQ, QueueDataType x) {
assert(pQ); //防止傳入的pQ為空
/* 創(chuàng)建新節(jié)點：創(chuàng)建一個大小為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; //默認為空
/* 入隊：
*【思路草圖】
* 情況1：隊列為空：既當頭又當尾
* [new_node]
* ↑ ↑
* pHead pTail
*
* 情況2：隊列不為空：隊尾入數(shù)據(jù)
* [] -> [] -> [] -> [] -> [new_node]
* pHead pTail pTail->next
* ↓ ↑
* ----------→ pTail（更新尾指針）
*/
if(pQ->pHead == NULL) { //情況1: 隊列為空
pQ->pHead = pQ->pTail = new_node; // 既當頭又當尾
} else { //情況2: 隊列不為空
pQ->pTail->next = new_node; // 在現(xiàn)有尾的后一個節(jié)點放置new_node
pQ->pTail = new_node; // 更新pTail，使它指向新的尾
}
}
?? 解讀：
① 首先斷言防止傳入的pQ為空。
② 我們首先要創(chuàng)建新節(jié)點。通過 malloc 動態(tài)內(nèi)存開辟一塊 QueueNode 大小的空間，都學到這里了大家想必都養(yǎng)成了檢查 malloc 的好習慣了吧？。最后放置數(shù)據(jù)嗎，將待插入的數(shù)據(jù) x 交給 data，next 默認置空，和之前學鏈表一樣，這里就不過多贅述了。
③ 新節(jié)點創(chuàng)建好后，我們可以開始寫入隊的操作了。首先要理解隊列的性質(zhì)：隊尾入數(shù)據(jù)，隊頭出數(shù)據(jù)。這里既然是入隊，就要在對尾后面進行插入。這里我們還要考慮到如果隊列為空的情況，這時我們要把頭指針和尾指針都交付給 new_node 。為了理清思路，我們可以畫一個思路草圖來幫助我們更好地理解：
有了這個圖，我們就可以清楚地實現(xiàn)了：
if(pQ->pHead == NULL) { //情況1: 隊列為空
pQ->pHead = pQ->pTail = new_node; // 既當頭又當尾
}
else { //情況2: 隊列不為空
pQ->pTail->next = new_node; // 在現(xiàn)有尾的后一個節(jié)點放置new_node
pQ->pTail = new_node; // 更新pTail，使它指向新的尾
}
當隊列為空時，令頭指針和尾指針都指向 new_node ，當隊列不為空時，再尾部地下一個節(jié)點放置 new_node?，隨后再更新尾指針讓其指向新的尾（new_node 的位置）。
0x04 出隊（QueuePop）
?? Queue.h
void QueuePop(Queue* pQ); //出隊
?? Queue.c
/* 出隊：隊尾入數(shù)據(jù)，對頭出數(shù)據(jù) */
void QueuePop(Queue* pQ) {
assert(pQ); //防止傳入的pQ為空
assert(!QueueIsEmpty(pQ)); //防止隊列為空
/* 出隊:
*【思路草圖】
* [free] -> [] -> [] -> []
* pHead headNext
* ↓ ↑
* -------→ pHead（更新頭指針）
*/
QueueNode* headNext = pQ->pHead->next; //信標指針HeadNext
free(pQ->pHead);
pQ->pHead = headNext; //更新頭
/* 如果隊內(nèi)都被刪完了，不處理pTail就會帶來野指針的隱患
* 【思路草圖】
* NULL 已經(jīng)被free掉的內(nèi)存！
* ↑ ↑ （野指針警告）
* pHead(因為HeadNext是NULL) pTail
*/
if(pQ->pHead == NULL) //如果pHead為空
pQ->pTail = NULL; //處理一下尾指針，將尾指針置空
}
?? 解讀：
① 首先斷言防止傳入的 pQ 為空，這里還要放置隊列為空，如果隊列為空還要求出隊的話會出問題的，所以這里要斷言一下 QueueIsEmpty 為假。
② 思路草圖如下：
出數(shù)據(jù)需要釋放，和銷毀一樣，這里使用一個類似于信標性質(zhì)的指針來記錄 pHead 的下一個節(jié)點，之后我們就可以大膽地釋放 pHead 而不用擔心找不到了。free 掉之后更新頭即可，令頭指針指向 headNext 即可。?
?? 注意：這里還要考慮一個問題，如果隊內(nèi)都被刪完了，pHead 往后走指向空，但是 pTail 仍然指向那塊已經(jīng)被 free 掉的空間。pTail 就是一個典型的野指針。
我們可以不用擔心 pHead，因為后面沒有數(shù)據(jù)他會自然指向 NULL，但是我們這里得關(guān)注 pTail ！我們需要手動處理一下它：
如果 pHead 為空，我們就把 pTail 也置為空即可。
if(pQ->pHead == NULL) //如果pHead為空
pQ->pTail = NULL; //處理一下尾指針，將尾指針置空
0x05?返回隊頭數(shù)據(jù)（QueueFront）
?? Queue.h
QueueDataType QueueFront(Queue* pQ); //返回隊頭數(shù)據(jù)
?? Queue.c
/* 返回隊頭數(shù)據(jù) */
QueueDataType QueueFront(Queue* pQ) {
assert(pQ); //防止傳入的pQ為空
assert(!QueueIsEmpty(pQ)); //防止隊列為空
return pQ->pHead->data;
}
?? 解讀：
① 首先斷言防止傳入的 pQ 為空，這里我們還是要斷言一下 QueueIsEmpty 為假，因為如果隊內(nèi)沒有數(shù)據(jù)，還返回個錘子數(shù)據(jù)呢。
② 這里直接返回頭的數(shù)據(jù)即可，特別簡單沒有什么好講的。
0x06?返回隊尾數(shù)據(jù)（QueueBack）
?? Queue.h
QueueDataType QueueBack(Queue* pQ); //返回隊尾數(shù)據(jù)
?? Queue.c
/* 返回隊尾數(shù)據(jù) */
QueueDataType QueueBack(Queue* pQ) {
assert(pQ); //防止傳入的pQ為空
assert(!QueueIsEmpty(pQ)); //防止隊列為空
return pQ->pTail->data;
}
?? 解讀：
① 首先斷言防止傳入的 pQ 為空，斷言一下 QueueIsEmpty 為假。
② 這里直接返回隊尾的數(shù)據(jù)即可。
0x07?求隊列大?。≦ueueSize）
?? Queue.h
int QueueSize(Queue* pQ); //求隊列大小
?? Queue.c
/* 求隊列大?。河嫈?shù)器法 */
int QueueSize(Queue* pQ) {
assert(pQ); //防止傳入的pQ為空
int count = 0; //計數(shù)器
QueueNode* cur = pQ->pHead; //創(chuàng)建遍歷指針cur
while(cur != NULL) {
++count; //計數(shù)+1
cur = cur->next; //移動指針cur
}
return count;
}
?? 解讀：這里我們采用計數(shù)器法來求大小即可，調(diào)用一次就是 O(N)?，也沒什么不好的。
① 首先斷言防止傳入的 pQ 為空。
② 創(chuàng)建計數(shù)器變量和遍歷指針 cur，遍歷整個隊列并計數(shù)，最后返回計數(shù)的結(jié)果即可。
0x08 完整代碼
?? Queue.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef int QueueDataType; //隊列類型
typedef struct QueueNode {
struct QueueNode* next; //指向下一個節(jié)點
QueueDataType data; //數(shù)據(jù)
} QueueNode;
typedef struct Queue {
QueueNode* pHead; //頭指針
QueueNode* pTail; //尾指針
} Queue;
void QueueInit(Queue* pQ); //隊列初始化
void QueueDestroy(Queue* pQ); //銷毀隊列
bool QueueIsEmpty(Queue* pQ); //判斷隊列是否為空
void QueuePush(Queue* pQ, QueueDataType x); //入隊
void QueuePop(Queue* pQ); //出隊
QueueDataType QueueFront(Queue* pQ); //返回隊頭數(shù)據(jù)
QueueDataType QueueBack(Queue* pQ); //返回隊尾數(shù)據(jù)
int QueueSize(Queue* pQ); //求隊列大小
?? Queue.c
#include <Queue.h>
/* 隊列初始化：將頭尾指針置為NULL */
void QueueInit(Queue* pQ) {
assert(pQ); //防止傳入的pQ為空
pQ->pHead = pQ->pTail = NULL; //將頭尾指針置空
}
/* 銷毀隊列：free掉所有隊列元素并將頭尾置空 */
void QueueDestroy(Queue* pQ) {
assert(pQ); //防止傳入的pQ為空
QueueNode* cur = pQ->pHead; //創(chuàng)建遍歷指針cur
while(cur != NULL) { //cur不為空就進入循環(huán)
QueueNode* curNext = cur->next; //信標指針curNext，防止釋放cur后找不到其下一個節(jié)點
free(cur); //釋放cur當前指向的節(jié)點
cur = curNext; //移動指針cur
}
pQ->pHead = pQ->pTail = NULL; //置空干掉野指針
}
/* 判斷隊列是否為空 */
bool QueueIfEmpty(Queue* pQ) {
assert(pQ); //防止傳入的pQ為空
return pQ->pHead == NULL; //如果成立則為True，不成立則為False
}
/* 入隊：隊尾入數(shù)據(jù)，對頭出數(shù)據(jù)。如果是第一個入隊的則既要當頭又當尾 */
void QueuePush(Queue* pQ, QueueDataType x) {
assert(pQ); //防止傳入的pQ為空
/* 創(chuàng)建新節(jié)點：創(chuàng)建一個大小為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; //默認為空
/* 入隊：
*【思路草圖】
* 情況1：隊列為空：既當頭又當尾
* [new_node]
* ↑ ↑
* pHead pTail
*
* 情況2：隊列不為空：隊尾入數(shù)據(jù)
* [] -> [] -> [] -> [] -> [new_node]
* pHead pTail pTail->next
* ↓ ↑
* ----------→ pTail（更新尾指針）
*/
if(pQ->pHead == NULL) { //情況1: 隊列為空
pQ->pHead = pQ->pTail = new_node; // 既當頭又當尾
} else { //情況2: 隊列不為空
pQ->pTail->next = new_node; // 在現(xiàn)有尾的后一個節(jié)點放置new_node
pQ->pTail = new_node; // 更新pTail，使它指向新的尾
}
}
/* 出隊：隊尾入數(shù)據(jù)，對頭出數(shù)據(jù) */
void QueuePop(Queue* pQ) {
assert(pQ); //防止傳入的pQ為空
assert(!QueueIsEmpty(pQ)); //防止隊列為空
/* 出隊:
*【思路草圖】
* [free] -> [] -> [] -> []
* pHead headNext
* ↓ ↑
* -------→ pHead（更新頭指針）
*/
QueueNode* headNext = pQ->pHead->next; //信標指針HeadNext，防止釋放pHead后找不到其下一個節(jié)點
free(pQ->pHead);
pQ->pHead = headNext; //更新頭
/* 如果隊內(nèi)都被刪完了，不處理pTail就會帶來野指針的隱患
* 【思路草圖】
* NULL 已經(jīng)被free掉的空間！
* ↑ ↑ （野指針）
* pHead(因為HeadNext是NULL) pTail
*/
if(pQ->pHead == NULL) //如果pHead為空
pQ->pTail = NULL; //處理一下尾指針，將尾指針置空
}
/* 返回隊頭數(shù)據(jù) */
QueueDataType QueueFront(Queue* pQ) {
assert(pQ); //防止傳入的pQ為空
assert(!QueueIsEmpty(pQ)); //防止隊列為空
return pQ->pHead->data;
}
/* 返回隊尾數(shù)據(jù) */
QueueDataType QueueBack(Queue* pQ) {
assert(pQ); //防止傳入的pQ為空
assert(!QueueIsEmpty(pQ)); //防止隊列為空
return pQ->pTail->data;
}
/* 求隊列大小：計數(shù)器法 */
int QueueSize(Queue* pQ) {
assert(pQ); //防止傳入的pQ為空
int count = 0; //計數(shù)器
QueueNode* cur = pQ->pHead; //創(chuàng)建遍歷指針cur
while(cur != NULL) {
++count; //計數(shù)+1
cur = cur->next; //移動指針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出來，再繼續(xù)入，它的順序還是不會變。
// 永遠保持先進先出的，無論是入了兩個出兩個，再入再出，還是全部入完了再出，都是不會變的。這就是隊列的性質(zhì)
while(!QueueIsEmpty(&q)) {
QueueDataType front = QueueFront(&q);
printf("%d ", front);
QueuePop(&q); //pop掉去下一個
}
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
? 勘誤： 無
?? 聲明： 由于作者水平有限，本文有錯誤和不準確之處在所難免，本人也很想知道這些錯誤，懇望讀者批評指正！
本篇完。
到此這篇關(guān)于C語言數(shù)據(jù)結(jié)構(gòu)系列隊列篇的文章就介紹到這了,更多相關(guān)C語言 隊列內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
本文主要介紹了淺談C++流庫的基本結(jié)構(gòu)，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2023-04-04
下面小編就為大家?guī)硪黄钊肜斫釰ava事務(wù)的原理與應用。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2016-06-06
C++實現(xiàn)十六進制字符串轉(zhuǎn)換為十進制整數(shù)的方法
這篇文章主要介紹了C++實現(xiàn)十六進制字符串轉(zhuǎn)換為十進制整數(shù)的方法,涉及C++字符串與數(shù)制轉(zhuǎn)換的相關(guān)技巧,具有一定參考借鑒價值,需要的朋友可以參考下2015-07-07
這篇文章主要為大家詳細介紹了C語言實現(xiàn)BMP圖像細化處理，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-10-10
這篇文章主要為大家介紹了C++實現(xiàn)簡單的信息管理系統(tǒng)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2016-04-04
Boost是為C++語言標準庫提供擴展的一些C++程序庫的總稱。Boost庫是一個可移植、提供源代碼的C++庫，作為標準庫的后備，是C++標準化進程的開發(fā)引擎之一，是為C++語言標準庫提供擴展的一些C++程序庫的總稱2022-11-11
本文主要介紹了C++使用VLD檢測內(nèi)存泄漏，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2023-06-06
詳解如何配置CLion作為Qt5開發(fā)環(huán)境的方法
這篇文章主要介紹了詳解如何配置CLion作為Qt5開發(fā)環(huán)境的方法，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2021-04-04
在C++中，內(nèi)存分為：棧、堆、自由存儲區(qū)、全局/靜態(tài)存儲區(qū)、常量存儲區(qū)。這篇文章主要介紹了一文秒懂C語言/C++內(nèi)存管理,需要的朋友可以參考下2020-11-11
C++超詳細分析講解內(nèi)聯(lián)函數(shù)
為了消除函數(shù)調(diào)用的時空開銷，C++ 提供一種提高效率的方法，即在編譯時將函數(shù)調(diào)用處用函數(shù)體替換，類似于C語言中的宏展開。這種在函數(shù)調(diào)用處直接嵌入函數(shù)體的函數(shù)稱為內(nèi)聯(lián)函數(shù)（Inline Function），又稱內(nèi)嵌函數(shù)或者內(nèi)置函數(shù)2022-06-06