溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務(wù)條款》
您好，登錄后才能下訂單哦！
這篇文章將為大家詳細講解有關(guān)C語言中隊列的示例分析，小編覺得挺實用的，因此分享給大家做個參考，希望大家閱讀完這篇文章后可以有所收獲。
???? 概念：
① 隊列只允許在一端進行插入數(shù)據(jù)操作，在另一端進行刪除數(shù)據(jù)操作的特殊線性表。
② 入隊列，進行插入操作的一端稱為 隊尾。出隊列，進行刪除操作的一端稱為 隊頭。
③ 隊列中的元素遵循先進先出的原則，即 FIFO 原則（First In First Out）
???? 結(jié)構(gòu)：
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)，實際中定義幾個指針是看你的需求確定的。
???? 這是需要實現(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); //求隊列大小
???? 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為空。初始化只需要把頭指針和尾指針都置成空即可。
/* 銷毀隊列：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; //信標(biāo)指針curNext，防止釋放cur后找不到其下一個節(jié)點
free(cur); //釋放cur當(dāng)前指向的節(jié)點
cur = curNext; //移動指針cur
}
pQ->pHead = pQ->pTail = NULL; //置空干掉野指針
}???? 解讀：
① 首先斷言防止傳入的pQ為空。
② 銷毀要把所有節(jié)點都釋放掉，我們創(chuàng)建遍歷指針 cur 遍歷整個隊列。既然要釋放 cur 指向的節(jié)點，為了防止釋放 cur 之后找不到其下一個節(jié)點導(dǎo)致無法移動，我們這里創(chuàng)建一個類似于信標(biāo)性質(zhì)的指針 curNext 來記錄一下 cur 的下一個節(jié)點，之后再 free 掉 cur，這樣就可以移動 cur 了。
③ 最后為了防止野指針，還需要把頭指針和尾指針都置為空。
???? 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。
???? Queue.h
void QueuePush(Queue* pQ, QueueDataType x); //入隊
???? Queue.c
/* 入隊：隊尾入數(shù)據(jù)，對頭出數(shù)據(jù)。如果是第一個入隊的則既要當(dāng)頭又當(dāng)尾 */
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：隊列為空：既當(dāng)頭又當(dāng)尾
* [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; // 既當(dāng)頭又當(dāng)尾
} 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 大小的空間，都學(xué)到這里了大家想必都養(yǎng)成了檢查 malloc 的好習(xí)慣了吧？。最后放置數(shù)據(jù)嗎，將待插入的數(shù)據(jù) x 交給 data，next 默認置空，和之前學(xué)鏈表一樣，這里就不過多贅述了。
③ 新節(jié)點創(chuàng)建好后，我們可以開始寫入隊的操作了。首先要理解隊列的性質(zhì)：隊尾入數(shù)據(jù)，隊頭出數(shù)據(jù)。這里既然是入隊，就要在對尾后面進行插入。這里我們還要考慮到如果隊列為空的情況，這時我們要把頭指針和尾指針都交付給 new_node 。為了理清思路，我們可以畫一個思路草圖來幫助我們更好地理解：
有了這個圖，我們就可以清楚地實現(xiàn)了：
if(pQ->pHead == NULL) { //情況1: 隊列為空
pQ->pHead = pQ->pTail = new_node; // 既當(dāng)頭又當(dāng)尾
}
else { //情況2: 隊列不為空
pQ->pTail->next = new_node; // 在現(xiàn)有尾的后一個節(jié)點放置new_node
pQ->pTail = new_node; // 更新pTail，使它指向新的尾
}當(dāng)隊列為空時，令頭指針和尾指針都指向 new_node ，當(dāng)隊列不為空時，再尾部地下一個節(jié)點放置 new_node ，隨后再更新尾指針讓其指向新的尾（new_node 的位置）。
???? 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; //信標(biāo)指針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ù)需要釋放，和銷毀一樣，這里使用一個類似于信標(biāo)性質(zhì)的指針來記錄 pHead 的下一個節(jié)點，之后我們就可以大膽地釋放 pHead 而不用擔(dān)心找不到了。free 掉之后更新頭即可，令頭指針指向 headNext 即可。
???? 注意：這里還要考慮一個問題，如果隊內(nèi)都被刪完了，pHead 往后走指向空，但是 pTail 仍然指向那塊已經(jīng)被 free 掉的空間。pTail 就是一個典型的野指針。
我們可以不用擔(dān)心 pHead，因為后面沒有數(shù)據(jù)他會自然指向 NULL，但是我們這里得關(guān)注 pTail ！我們需要手動處理一下它：
如果 pHead 為空，我們就把 pTail 也置為空即可。
if(pQ->pHead == NULL) //如果pHead為空 pQ->pTail = NULL; //處理一下尾指針，將尾指針置空
???? 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ù)即可，特別簡單沒有什么好講的。
???? 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ù)即可。
???? 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é)果即可。
???? 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; //信標(biāo)指針curNext，防止釋放cur后找不到其下一個節(jié)點
free(cur); //釋放cur當(dāng)前指向的節(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ù)。如果是第一個入隊的則既要當(dāng)頭又當(dāng)尾 */
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：隊列為空：既當(dāng)頭又當(dāng)尾
* [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; // 既當(dāng)頭又當(dāng)尾
} 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; //信標(biāo)指針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;
}關(guān)于“C語言中隊列的示例分析”這篇文章就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，使各位可以學(xué)到更多知識，如果覺得文章不錯，請把它分享出去讓更多的人看到。
免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點不代表本網(wǎng)站立場，如果涉及侵權(quán)請聯(lián)系站長郵箱：is@yisu.com進行舉報，并提供相關(guān)證據(jù)，一經(jīng)查實，將立刻刪除涉嫌侵權(quán)內(nèi)容。
億速云公眾號
手機網(wǎng)站二維碼