??專欄導(dǎo)讀
??作者簡(jiǎn)介：M malloc，致力于成為嵌入式大牛的男人
??專欄簡(jiǎn)介：本文收錄于 初階數(shù)據(jù)結(jié)構(gòu)，本專欄主要內(nèi)容講述了初階的數(shù)據(jù)結(jié)構(gòu)，如順序表，鏈表，棧，隊(duì)列等等，專為小白打造的文章專欄。
??相關(guān)專欄推薦：LeetCode刷題集，C語(yǔ)言每日一題。
??文章導(dǎo)讀
本章我將詳細(xì)的講解關(guān)于棧的知識(shí)點(diǎ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ì)列的兩種概念：
1、入隊(duì)列：進(jìn)行插入操作的一端稱為隊(duì)尾
2、出隊(duì)列：進(jìn)行刪除操作的一端稱為隊(duì)頭
??畫圖描述
如下圖所示，就是入隊(duì)列出隊(duì)列全過程啦！關(guān)于隊(duì)列有一個(gè)特點(diǎn)就是先進(jìn)先出不要忘記啦！
關(guān)于隊(duì)列的指示就是，先進(jìn)先出，隊(duì)尾進(jìn)，隊(duì)頭出。
??隊(duì)列的代碼實(shí)現(xiàn)及其各類講解
??隊(duì)列實(shí)現(xiàn)的理論過程
隊(duì)列也可以用數(shù)組和鏈表的結(jié)構(gòu)實(shí)現(xiàn)，使用鏈表的結(jié)構(gòu)實(shí)現(xiàn)更優(yōu)一些，因?yàn)槿绻褂脭?shù)組的結(jié)構(gòu)，出隊(duì)列在數(shù)組頭上出數(shù)據(jù)，效率會(huì)比較低。
??隊(duì)列的初始化代碼實(shí)現(xiàn)及其講解
??隊(duì)列的初始化
首先我們先定義一個(gè)結(jié)構(gòu)體類型(這里我們選擇使用的是鏈?zhǔn)疥?duì)列)：
typedef int QDatatype;
typedef struct QueueNode
{
struct QueueNode* next;
QDatatype data;
}QNode;
typedef struct Queue
{
QNode* phead;
QNode* ptail;
int size;
}Queue;
第一段結(jié)構(gòu)體類型其實(shí)是定義這個(gè)節(jié)點(diǎn)的類型，第二個(gè)結(jié)構(gòu)體定義的是這個(gè)隊(duì)列類型。
隊(duì)列的初始化
代碼如下：
void QueueInit(Queue* pq)
{
assert(pq);
pq->phead = NULL;
pq->ptail = NULL;
pq->size = 0;
}
首先assert是斷言，當(dāng)我們這個(gè)隊(duì)列為空的時(shí)候，我們程序就會(huì)報(bào)錯(cuò)，直接結(jié)束進(jìn)程。相對(duì)應(yīng)的初始化，如果指針的話我們賦值為NULL就行啦！
??隊(duì)列的銷毀代碼實(shí)現(xiàn)及其講解
因?yàn)槲覀冇玫氖擎準(zhǔn)疥?duì)列，而不是數(shù)組隊(duì)列，所以對(duì)于每一個(gè)節(jié)點(diǎn)我們都應(yīng)該釋放掉，因?yàn)閙alloc開辟的是在堆上開辟的。那么具體的是指什么時(shí)候呢？
首先：這是我們最開始的情況
我們要記住，在遍歷的過程中永遠(yuǎn)不要?jiǎng)幼畛醯闹羔?，我們一定要把它賦值給一個(gè)指針，讓他遍歷，我們應(yīng)該從頭開始刪除，于是就有了下圖，我們把head賦給了cur
如下圖所示，此時(shí)的next值存儲(chǔ)的是cur->next，當(dāng)我們?cè)诒闅v的過程中，我們把cur，free掉之后，我們就可以通過next找到下一個(gè)我們想要銷毀的指針，直到這一片位置全被銷毀位置！
void QueueDestroy(Queue* pq)
{
assert(pq);
QNode* cur = pq->phead;
while (cur)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
pq->phead = pq->ptail = NULL;
pq->size = 0;
}
??隊(duì)列的插入代碼實(shí)現(xiàn)及其講解
在實(shí)現(xiàn)代碼的時(shí)候，我們要先考慮，我們應(yīng)該怎么插入。此時(shí)我們會(huì)發(fā)現(xiàn)插入其實(shí)很像單鏈表的頭插，我們可以理解為這是加入了限制條件的鏈表，也就是隊(duì)列。
在插入的時(shí)候我們應(yīng)該考慮多種情況，例如
1、此時(shí)這是一個(gè)空的隊(duì)列，我們應(yīng)該如何插入
2、也就是有節(jié)點(diǎn)的隊(duì)列如何插入。
好啦知道了我們要做什么了，現(xiàn)在我們就應(yīng)該開始進(jìn)行我們的畫圖描述啦！
1、首先我們應(yīng)該先malloc一塊新的節(jié)點(diǎn)出來(lái)，然后讓他賦給鏈表，那我們?nèi)绾沃肋@塊隊(duì)列是空的呢？這個(gè)時(shí)候，就需要來(lái)看到tail了，我們可以想象一下，如果尾結(jié)點(diǎn)是NULL值，那么是不是代表著此時(shí)的隊(duì)列就是空的呢？是滴！
所以我們第一步就應(yīng)該先判斷我們的tail指針是否為空，如果為空，我們直接把新節(jié)點(diǎn)賦給尾指針就行了。
那么此時(shí)是不是已經(jīng)有一個(gè)節(jié)點(diǎn)了呢？如下圖所示：
接下來(lái)我們要做的操作類似于單鏈表的尾插操作啦！首先我們要讓tail的next指向newnode，然后在把tail指針的位置移動(dòng)到newnode此時(shí)的位置，并且最后再讓size++
void QueuePush(Queue* pq, QDatatype x)
{
assert(pq);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc fail\n");
return;
}
newnode->data = x;
newnode->next = NULL;
if (pq->ptail == NULL)
{
assert(pq->phead == NULL);
pq->phead = pq->ptail = newnode;
}
else
{
pq->ptail->next = newnode;
pq->ptail = newnode;
}
pq->size++;
}
??隊(duì)列的刪除代碼實(shí)現(xiàn)及其講解
在隊(duì)列做刪除操作時(shí)，我們也要知道，我們刪除的時(shí)候也是從隊(duì)頭進(jìn)行刪除，其實(shí)就是頭刪啦。
這里我們也得考慮兩種情況，例如：
1、當(dāng)我們隊(duì)列只有一個(gè)節(jié)點(diǎn)的時(shí)候，我們應(yīng)該如何刪除呢？
2、也就是正常情況啦，也就是多個(gè)節(jié)點(diǎn)的情況
如果節(jié)點(diǎn)只有一個(gè)的情況我們需要考慮的是，直接free掉就行啦，
但是如果有多個(gè)節(jié)點(diǎn)的時(shí)候，我們就需要保存下一節(jié)點(diǎn)的地址，當(dāng)我們刪除上一節(jié)點(diǎn)時(shí)，我們就需要把下一節(jié)點(diǎn)的地址賦給頭結(jié)點(diǎn)指針就行啦，如下圖所示，我們把head，free掉，此時(shí)head的指針就應(yīng)該指向next處，這樣就可以進(jìn)行刪除啦！
void QueuePop(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
if (pq->phead->next == NULL)
{
free(pq->phead);
pq->phead = pq->ptail = NULL;
}
else
{
QNode* next = pq->phead->next;
free(pq->phead);
pq->phead = next;
}
pq->size--;
}
??隊(duì)列的判空代碼實(shí)現(xiàn)及其講解
判空代碼的實(shí)際過程其實(shí)是這樣的，當(dāng)頭指針和尾指針都是空的時(shí)候，它就是空啦??！
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->phead == NULL
&& pq->ptail == NULL;
}
??隊(duì)列的全部代碼的實(shí)現(xiàn)
queue.h
#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int QDatatype;
typedef struct QueueNode
{
struct QueueNode* next;
QDatatype data;
}QNode;
typedef struct Queue
{
QNode* phead;
QNode* ptail;
int size;
}Queue;
void QueueInit(Queue* pq);
void QueueDestroy(Queue* pq);
void QueuePush(Queue* pq, QDatatype x);
void QueuePop(Queue* pq);
QDatatype QueueFront(Queue* pq);
QDatatype QueueBack(Queue* pq);
int QueueSize(Queue* pq);
bool QueueEmpty(Queue* pq);
queue.c文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-475868.html
#define _CRT_SECURE_NO_WARNINGS 1
#include "Queue.h"
void QueueInit(Queue* pq)
{
assert(pq);
pq->phead = NULL;
pq->ptail = NULL;
pq->size = 0;
}
void QueueDestroy(Queue* pq)
{
assert(pq);
QNode* cur = pq->phead;
while (cur)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
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\n");
return;
}
newnode->data = x;
newnode->next = NULL;
if (pq->ptail == NULL)
{
assert(pq->phead == NULL);
pq->phead = pq->ptail = newnode;
}
else
{
pq->ptail->next = newnode;
pq->ptail = newnode;
}
pq->size++;
}
void QueuePop(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
if (pq->phead->next == NULL)
{
free(pq->phead);
pq->phead = pq->ptail = NULL;
}
else
{
QNode* next = pq->phead->next;
free(pq->phead);
pq->phead = next;
}
pq->size--;
}
QDatatype QueueFront(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->phead->data;
}
QDatatype QueueBack(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->ptail->data;
}
int QueueSize(Queue* pq)
{
assert(pq);
return pq->size;
}
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->phead == NULL
&& pq->ptail == NULL;
//pq->size == 0
}
總結(jié)
我是愛你們的M malloc，如果你覺得這一期對(duì)你有幫助你可以一鍵三連鴨?。。。∠乱黄跁?huì)繼續(xù)更細(xì)數(shù)據(jù)結(jié)構(gòu)??！文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-475868.html
到了這里，關(guān)于初階數(shù)據(jù)結(jié)構(gòu)之隊(duì)列的實(shí)現(xiàn)（六）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
