? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 🌹個(gè)人主頁(yè)🌹：喜歡草莓熊的bear

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 🌹專欄🌹：數(shù)據(jù)結(jié)構(gòu)

---

前言

上期博客介紹了”? 棧 “這個(gè)數(shù)據(jù)結(jié)構(gòu)，他具有先進(jìn)后出的特點(diǎn)。本期介紹“ 隊(duì)列 ”這個(gè)數(shù)據(jù)結(jié)構(gòu)，他具有先進(jìn)先出的特點(diǎn)。

?

目錄

前言

一、隊(duì)列

1.1隊(duì)列的概念及結(jié)構(gòu)

1.2隊(duì)列的實(shí)現(xiàn)

1.2.1隊(duì)列結(jié)構(gòu)體定義

1.2.2初始化和銷毀

1.2.3隊(duì)尾插入和隊(duì)頭刪除

1.2.3.1隊(duì)尾插入

1.2.3.2隊(duì)頭刪除

1.2.4獲取隊(duì)頭與隊(duì)尾數(shù)據(jù)

1.2.5返回隊(duì)列里面的元素個(gè)數(shù)

1.2.6隊(duì)列判空

1.3測(cè)試代碼

1.4代碼展示

頭文件

?實(shí)現(xiàn)功能文件.c

總結(jié)

---

一、隊(duì)列

1.1隊(duì)列的概念及結(jié)構(gòu)

1.2隊(duì)列的實(shí)現(xiàn)

1.2.1隊(duì)列結(jié)構(gòu)體定義

根據(jù)上面提到的我們基于鏈表（這里的鏈表代指單鏈表）來(lái)實(shí)現(xiàn)隊(duì)列。所以我就定義以下結(jié)構(gòu)體

typedef int QDataType;typedef struct QueueNode//我們基于單鏈表創(chuàng)建的隊(duì)列節(jié)點(diǎn)
{struct QueueNode* next;//下一節(jié)點(diǎn)的地址QDataType val;
}QNode;

?根據(jù)內(nèi)容發(fā)現(xiàn)我們要獲取隊(duì)列的隊(duì)頭數(shù)據(jù)和隊(duì)尾數(shù)據(jù)，所以我們要?jiǎng)?chuàng)建兩個(gè)這樣的結(jié)構(gòu)體。由于節(jié)點(diǎn)的地址是通過(guò)一級(jí)指針來(lái)表示的，所以要用二級(jí)指針來(lái)儲(chǔ)存，所以我們傳參數(shù)時(shí)要使用二級(jí)指針。?記住只要涉及通過(guò)形式參數(shù)改變實(shí)參的都要傳地址。

這時(shí)我們很牛的杭哥就給了一個(gè)思路，那就是再創(chuàng)建一個(gè)結(jié)構(gòu)體里面的元素是上一個(gè)結(jié)構(gòu)體。這樣既滿足了隊(duì)頭和隊(duì)尾指針，還不需要傳二級(jí)指針。因?yàn)橛幸粋€(gè)計(jì)數(shù)的功能所以再定義一個(gè)計(jì)數(shù)的變量。

typedef struct Queue //因?yàn)槲覀円獋黝^指針和尾指針，所以我們要傳兩個(gè)指針//我們又要傳二級(jí)指針，但是呢很麻煩，所以我們就新創(chuàng)建一個(gè)結(jié)構(gòu)體來(lái)儲(chǔ)存//上一個(gè)結(jié)構(gòu)體的指針。
{QNode* phead;//隊(duì)頭指針QNode* ptail;//隊(duì)尾指針int size;
}Queue;

1.2.2初始化和銷毀

初始化：這一步和上次寫的棧的初始化可以說(shuō)是十分相似，第一步還是判斷傳來(lái)的是否為空隊(duì)列，把結(jié)構(gòu)體里面的指針置為NULL，再把size賦值位0。就ok了。

void QueueInit(Queue* pq)
{assert(pq);pq->phead = pq->ptail = NULL;pq->size = 0;
}

銷毀：因?yàn)橐暾?qǐng)空間，必定需要free，因?yàn)槲覀兪腔阪湵韺?shí)現(xiàn)的參考一下單鏈表的銷毀。

?所以我們也需要一個(gè)一個(gè)節(jié)點(diǎn)釋放，最后把指針指向空指針，把size賦值為0.

void QueueDestory(Queue* pq)
{assert(pq);QNode* pur = pq->phead;while (pur){QNode* cur = pur->next;free(pur);pur = cur;}pq->phead = pq->ptail = NULL;pq->size = 0;
}

1.2.3隊(duì)尾插入和隊(duì)頭刪除

1.2.3.1隊(duì)尾插入

因?yàn)槲覀兪腔趩捂湵淼膶?shí)現(xiàn)的，所以只需要?jiǎng)?chuàng)建節(jié)點(diǎn)就可以了，通過(guò)malloc申請(qǐng)空間。添加一個(gè)節(jié)點(diǎn)就開(kāi)辟一塊空間。

鏈表不為空；很簡(jiǎn)單直接進(jìn)行尾插操作，不要忘了給size++。

鏈表為空；那就把頭和尾指針同時(shí)指向這個(gè)新節(jié)點(diǎn)。

判別是否為空鏈表少不了。

void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* Newnode = (QNode*)malloc(sizeof(QNode));if (Newnode == NULL){perror("malloc fail");return;}Newnode->next = NULL;Newnode->val = x;if (pq->phead==NULL)//空鏈表{pq->phead = pq->ptail = Newnode;}else{pq->ptail->next = Newnode;pq->ptail = Newnode;}pq->size++;//用來(lái)計(jì)數(shù)
}

1.2.3.2隊(duì)頭刪除

鏈表中只有一個(gè)節(jié)點(diǎn)：當(dāng)phead == ptail 時(shí)就只有一個(gè)節(jié)點(diǎn)了，所以我們把這個(gè)節(jié)點(diǎn)釋放了以后要把phead 和 ptail 都置為空指針，預(yù)防出現(xiàn)野指針。

多個(gè)節(jié)點(diǎn)：我們創(chuàng)建一個(gè)節(jié)點(diǎn)用來(lái)儲(chǔ)存頭節(jié)點(diǎn)的下一個(gè)指針，這樣釋放了頭節(jié)點(diǎn)也可以找到剩下的節(jié)點(diǎn)。對(duì)頭刪除當(dāng)然要size--。

老生常談，判斷是否為空鏈表，還要判斷是否還可以進(jìn)行隊(duì)頭刪除操作。也就隊(duì)列里面還有數(shù)據(jù)嗎

void QueuePop(Queue* pq)
{assert(pq);assert(pq->phead);if (pq->phead == pq->ptail)//只有一個(gè)節(jié)點(diǎn){free(pq->phead);pq->phead = pq->ptail = NULL;}else//多個(gè)節(jié)點(diǎn){QNode* tmp = pq->phead->next;free(pq->phead);pq->phead = tmp;}pq->size--;
}

1.2.4獲取隊(duì)頭與隊(duì)尾數(shù)據(jù)

很簡(jiǎn)單返回指針里面儲(chǔ)存的數(shù)據(jù)就可以了，除了判斷隊(duì)列是否為空。還要判斷這些頭尾指針是否為空的。

QDataType QueueFront(Queue* pq) //返回隊(duì)頭數(shù)據(jù)
{assert(pq);assert(pq->phead);return pq->phead->val;
}QDataType QueueBack(Queue* pq) //返回隊(duì)尾數(shù)據(jù)
{assert(pq);assert(pq->ptail);return pq->ptail->val;
}

1.2.5返回隊(duì)列里面的元素個(gè)數(shù)

這時(shí)就可以體現(xiàn)出我們?cè)俚诙o結(jié)構(gòu)體中創(chuàng)建size的價(jià)值了，我們直接返回size。沒(méi)有創(chuàng)建size我們就需要遍歷隊(duì)列了。

int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}

1.2.6隊(duì)列判空

前面創(chuàng)建的szie又幫了大忙，還可以用來(lái)判斷是否為空對(duì)列。

bool QueueEmpty(Queue* pq)
{assert(pq);return pq->size == 0;
}

1.3測(cè)試代碼

進(jìn)行了4個(gè)數(shù)據(jù)的插入，檢測(cè)了判空、獲取隊(duì)頭元素、隊(duì)頭刪除。等操作，在這里還是建議大家每完成一個(gè)功能就進(jìn)行測(cè)試，不然一起測(cè)試出現(xiàn)了很多問(wèn)題修改起來(lái)很麻煩的。作者身有體會(huì)，

#define _CRT_SECURE_NO_WARNINGS
#include"Queue.h"int main()
{Queue q;QueueInit(&q);QueuePush(&q, 1);QueuePush(&q, 2);printf("%d ", QueueFront(&q));QueuePop(&q);QueuePush(&q, 3);QueuePush(&q, 4);while (!QueueEmpty(&q)){printf("%d ", QueueFront(&q));QueuePop(&q);}QueueDestory(&q);return 0;
}

?成功實(shí)現(xiàn)了隊(duì)列 “ 先進(jìn)先出 ”的特點(diǎn)。

1.4代碼展示

頭文件

Queue.h
#pragma once
#include<stdio.h>
#include<stdbool.h>
#include<assert.h>
#include<stdlib.h>typedef int QDataType;typedef struct QueueNode//我們基于單鏈表創(chuàng)建的隊(duì)列節(jié)點(diǎn)
{struct QueueNode* next;QDataType val;
}QNode;typedef struct Queue //因?yàn)槲覀円獋黝^指針和尾指針，所以我們要傳兩個(gè)指針//我們又要傳二級(jí)指針，但是呢很麻煩，所以我們就新創(chuàng)建一個(gè)結(jié)構(gòu)體來(lái)儲(chǔ)存//上一個(gè)結(jié)構(gòu)體的指針。
{QNode* phead;QNode* ptail;int size;
}Queue;//初始化和銷毀
void QueueInit(Queue* pq);
void QueueDestory(Queue* pq);//隊(duì)尾插入和隊(duì)頭刪除
void QueuePush(Queue* pq, QDataType x);
void QueuePop(Queue* pq);//獲取隊(duì)頭、尾數(shù)據(jù)
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);//返回個(gè)數(shù)和判空
int QueueSize(Queue* pq);
bool QueueEmpty(Queue* pq);

?實(shí)現(xiàn)功能文件.c

Queue.c
#define _CRT_SECURE_NO_WARNINGS
#include"Queue.h"void QueueInit(Queue* pq)
{assert(pq);pq->phead = pq->ptail = NULL;pq->size = 0;
}void QueueDestory(Queue* pq)
{assert(pq);QNode* pur = pq->phead;while (pur){QNode* cur = pur->next;free(pur);pur = cur;}pq->phead = pq->ptail = NULL;pq->size = 0;
}void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* Newnode = (QNode*)malloc(sizeof(QNode));if (Newnode == NULL){perror("malloc fail");return;}Newnode->next = NULL;Newnode->val = x;if (pq->phead==NULL)//空鏈表{pq->phead = pq->ptail = Newnode;}else{pq->ptail->next = Newnode;pq->ptail = Newnode;}pq->size++;//用來(lái)計(jì)數(shù)
}void QueuePop(Queue* pq)
{assert(pq);assert(pq->phead);if (pq->phead == pq->ptail)//只有一個(gè)節(jié)點(diǎn){free(pq->phead);pq->phead = pq->ptail = NULL;}else//多個(gè)節(jié)點(diǎn){QNode* tmp = pq->phead->next;free(pq->phead);pq->phead = tmp;}pq->size--;
}QDataType QueueFront(Queue* pq)
{assert(pq);assert(pq->phead);return pq->phead->val;
}QDataType QueueBack(Queue* pq)
{assert(pq);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;
}

---

總結(jié)

很感謝大家的喜歡，有問(wèn)題大家在評(píng)論區(qū)發(fā)來(lái)我們一起交流。下期預(yù)告通過(guò)棧和隊(duì)列互相實(shí)現(xiàn)對(duì)方的功能。