🎉🎉想快速入門資料結構，推薦訂閱作者的初階資料結構專欄！此專欄預計更新：順序表，鏈表，堆疊，佇列，二叉樹，排序演算法等等

🎉🎉初階資料結構我們通過c語言實作，所以此專欄也可以幫助大家鞏固大家的c語言知識

🎉🎉源代碼已上傳至我的碼云

🎉🎉博主的微信公眾號關注啦，關注我每天學習一道題，點我關注

前言

我們在前面已經學習了堆疊這種資料結構，已經了解了它是一種操作受限的線性表，其只能在堆疊頂進行插入與洗掉操作，遵循后進先出的規則

而佇列，與堆疊的本質差不多，都是操作受限的線性表，但它卻有一些不同的性質

它有兩個操作端，隊尾和隊頭，且只能在隊頭洗掉資料，只能在隊尾插入資料

支持的是先進先出

我們可以形象地理解一下：佇列佇列，顧明思義就是排隊

試想現在是中午，一群人排隊去食堂打飯

那肯定是先到的人先打到飯，也就是會先退出這個隊伍

佇列我們同樣可以使用順序表或者鏈表實作

但佇列這一塊沒有爭議，用鏈表實作稍好一些

因為我們知道，順序表要插入和洗掉的復雜度是O(n)

而鏈表的插入洗掉復雜度是O(1)

這個結構不像堆疊，只在一端進行插入和洗掉，那樣順序表可以達到O(1)

而它兩邊都需要操作，那么順序表總有一端操作的復雜度會達到O(n)

所以佇列我們使用鏈表來實作

佇列定義

佇列的頭檔案定義

首先，因為是鏈表實作，我們要定義一個鏈表出來，本文使用單鏈表來實作

typedef struct QueneNode
{
	struct QueneNode* next;
	QDataType data;
}QNode;

鏈表的文章我在前面有講過哦，不懂的小伙伴需要復習功課啦！點我復習

隨后就需要定義佇列了

為了方便佇列的操作，我們需要兩個指標，一個指向頭結點head，一個指向尾結點tail

我們知道，單鏈表的尾部插入的復雜度為O(n)，（需要遍歷到尾結點），所以定義這兩個指標是非常有必要的

typedef struct Quene
{
	QNode* front;//指向頭結點的指標
	QNode* tail;//指向尾結點的指標
}Quene;

隨后補全一些代碼，完成的我們的定義

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

typedef int QDataType;

typedef struct QueneNode
{
	struct QueneNode* next;
	QDataType data;
}QNode;

typedef struct Quene
{
	QNode* front;
	QNode* tail;
}Quene;

佇列初始化

因為我們佇列中的指標還沒有初始化，是野指標，對于野指標我們是零容忍的，所以，我們需要先對它們進行置空

void QueneInit(Quene* pq)
{
	assert(pq);

	pq->front = NULL;
	pq->tail = NULL;
}

佇列的插入

佇列我們是在隊尾進行插入的，所以我們需要對tail指標進行操作

在tail后面插入一個結點后，再將tail進行更新

可以寫出以下代碼

void QuenePush(Quene* pq, QDataType x)
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (!newnode)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	//以上是結點開辟的方法，屬于單鏈表的內容

	pq->tail->next = newnode;//鏈接
	pq->tail = newnode;//更新

但是有以下的情況：

如果佇列為空，我們直接操作的話，就是典型的空指標參考的問題

所以我們需要對這個情況進行特判

然后就完成了完整的代碼

void QuenePush(Quene* pq, QDataType x)
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (!newnode)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;

	if (QueneEmpty(pq))//后文講到的判空函式
	{
		pq->front = newnode;
		pq->tail = newnode;
	}//這個代碼塊是佇列為空的特判
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;

	}
	
}

佇列洗掉

我們只能在隊頭進行洗掉，也就是只能對頭結點進行操作

因為釋放了頭結點后，我們就找不到新的頭結點了

所以需要一個變數來記錄，方便更新頭結點

這里有兩個問題

首先是佇列為空的問題

這個我們已經比較熟悉了，直接assert斷言即可

其次是野指標隱患

當我們只剩一個結點的時候，如果我們需要洗掉資料

發現了嗎？雖然head被置空了，但是tail卻還指向一個已經被釋放的結點

為了避免這種情況，需要將tail置空

void QuenePop(Quene* pq)
{
	assert(pq);
	assert(!QueneEmpty(pq));//空佇列特判
	QNode* newfront = pq->front->next;
	free(pq->front);
	pq->front = newfront;
	if (!newfront)
	{
		pq->tail = NULL;//防止野指標
	}
}

佇列判空

頭結點為空即可

bool QueneEmpty(Quene* pq)
{
	assert(pq);
	return pq->front == NULL;
}

取出隊尾和隊頭的元素

沒什么難度，直接回傳頭指標或者尾指標指向的結點的值即可

QDataType QueneFront(Quene* pq)
{
	assert(pq);
	assert(!QueneEmpty(pq));
	return pq->front->data;
}

QDataType QueneBack(Quene* pq)
{
	assert(pq);
	assert(!QueneEmpty(pq));
	return pq->tail->data;
}

佇列大小

這里由于我們沒有儲存大小，所以需要遍歷來算出佇列的大小

int QueneSize(Quene* pq)
{
	assert(pq);
	assert(!QueneEmpty(pq));
	int cnt = 0;
	QNode* cur = pq->front;
	while (cur)
	{
		cur = cur->next;
		cnt++;
	}
	return cnt;
}

佇列銷毀

與鏈表的銷毀相同，只是最后要把tail和head給置空

void QueneDestory(Quene* pq)
{
	assert(pq);
	QNode* cur = pq->front;
	

	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
		
	}
	pq->front = pq->tail = NULL;
}