隊(duì)列，又稱為佇列（queue），計(jì)算機(jī)科學(xué)中的一種抽象資料類型，是先進(jìn)先出（FIFO, First-In-First-Out）的線性表。在具體應(yīng)用中通常用鏈表或者數(shù)組來(lái)實(shí)現(xiàn)。隊(duì)列只允許在后端（稱為rear）進(jìn)行插入操作，在前端（稱為front）進(jìn)行刪除操作。

typedef int QDataType;
typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType data;
}QNode;

這段代碼使用 typedef 關(guān)鍵字定義了一個(gè)名為 QueueNode 的結(jié)構(gòu)體。QueueNode 結(jié)構(gòu)體包含兩個(gè)成員：

一個(gè)指向另一個(gè) QueueNode 結(jié)構(gòu)體的指針，名為 next，用于表示隊(duì)列中的下一個(gè)節(jié)點(diǎn)。
一個(gè)名為 data 的變量，其數(shù)據(jù)類型為 QDataType，用于表示節(jié)點(diǎn)中存儲(chǔ)的數(shù)據(jù)。
QNode 被定義為 struct QueueNode* 的別名，也就是說(shuō)，QNode 是一個(gè)指向 QueueNode 結(jié)構(gòu)體的指針。

總的來(lái)說(shuō)，這段代碼定義了一個(gè)鏈表節(jié)點(diǎn)結(jié)構(gòu)體，可以用來(lái)實(shí)現(xiàn)隊(duì)列數(shù)據(jù)結(jié)構(gòu)，其中每個(gè)節(jié)點(diǎn)包含一個(gè)數(shù)據(jù)元素和一個(gè)指向隊(duì)列中下一個(gè)節(jié)點(diǎn)的指針。

typedef struct Queue
{
	QNode* head;
	QNode* tail;
	int size;
}Queue;

這段代碼使用 typedef 關(guān)鍵字定義了一個(gè)名為 Queue 的結(jié)構(gòu)體。Queue 結(jié)構(gòu)體包含三個(gè)成員變量：

一個(gè)指向 QNode 結(jié)構(gòu)體的指針，名為 head，用于表示隊(duì)列中的第一個(gè)節(jié)點(diǎn)。
一個(gè)指向 QNode 結(jié)構(gòu)體的指針，名為 tail，用于表示隊(duì)列中的最后一個(gè)節(jié)點(diǎn)。
一個(gè)整型變量，名為 size，用于表示隊(duì)列中節(jié)點(diǎn)的數(shù)量。
這個(gè)結(jié)構(gòu)體可以用來(lái)實(shí)現(xiàn)一個(gè)隊(duì)列數(shù)據(jù)結(jié)構(gòu)，其中 head 指向隊(duì)列的開頭，tail 指向隊(duì)列的結(jié)尾，size 記錄隊(duì)列中節(jié)點(diǎn)的數(shù)量。通常情況下，向隊(duì)列中添加一個(gè)節(jié)點(diǎn)會(huì)使 tail 指針指向新的節(jié)點(diǎn)，從隊(duì)列中移除一個(gè)節(jié)點(diǎn)會(huì)使 head 指針指向下一個(gè)節(jié)點(diǎn)，并更新 size 的值。

//初始化隊(duì)列
void QueueInit(Queue* q)
{
	assert(q);
	q->head = q->tail = NULL;
	q->size = 0;
}

這段代碼定義了一個(gè)名為 QueueInit 的函數(shù)，用于初始化一個(gè)隊(duì)列。函數(shù)中傳入一個(gè)指向 Queue 結(jié)構(gòu)體的指針 q，并使用 assert 宏斷言 q 不為 NULL。

函數(shù)的實(shí)現(xiàn)非常簡(jiǎn)單，將 q 的 head 和 tail 成員都賦值為 NULL，將 size 成員賦值為 0，這樣就完成了隊(duì)列的初始化操作。由于 q 是一個(gè)指針，函數(shù)中對(duì)其進(jìn)行的操作實(shí)際上是對(duì)傳入的隊(duì)列進(jìn)行修改，因此不需要返回值。

// 隊(duì)尾入隊(duì)列
void QueuePush(Queue* q, QDataType data)
{
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}
	newnode->data = data;
	newnode->next = NULL;

	if (q->head == NULL)
	{
		assert(q->tail == NULL);
		q->head = q->tail = newnode;
	}
	else
	{
		q->tail->next = newnode;
		q->tail = newnode;
	}
	q->size++;

這段代碼定義了一個(gè)名為 QueuePush 的函數(shù)，用于將一個(gè)元素插入到隊(duì)列的尾部。函數(shù)中傳入一個(gè)指向 Queue 結(jié)構(gòu)體的指針 q，以及要插入的數(shù)據(jù) data。

函數(shù)的實(shí)現(xiàn)分為以下幾步：

使用 malloc 函數(shù)動(dòng)態(tài)分配一個(gè) QNode 結(jié)構(gòu)體大小的內(nèi)存空間，并將其強(qiáng)制轉(zhuǎn)換為指向 QNode 結(jié)構(gòu)體的指針 newnode。
檢查 newnode 是否為空，如果為空則輸出錯(cuò)誤信息并返回。
將 newnode 的 data 成員賦值為傳入的 data，將 newnode 的 next 成員賦值為 NULL，表示 newnode 是隊(duì)列中的最后一個(gè)節(jié)點(diǎn)。
檢查隊(duì)列是否為空。如果隊(duì)列為空，則將隊(duì)列的 head 和 tail 成員都指向 newnode，表示 newnode 是隊(duì)列中唯一的節(jié)點(diǎn)。
如果隊(duì)列不為空，則將隊(duì)列的 tail 節(jié)點(diǎn)的 next 指針指向 newnode，表示將 newnode 插入到隊(duì)列的尾部，并將 tail 指針指向 newnode，表示 newnode 現(xiàn)在是隊(duì)列中的最后一個(gè)節(jié)點(diǎn)。
將隊(duì)列的 size 成員加1，表示隊(duì)列中節(jié)點(diǎn)的數(shù)量增加了1。
由于隊(duì)列是由指針鏈表實(shí)現(xiàn)的，因此在插入節(jié)點(diǎn)時(shí)需要進(jìn)行動(dòng)態(tài)內(nèi)存分配，并將相鄰節(jié)點(diǎn)的指針進(jìn)行修改。

// 隊(duì)頭出隊(duì)列
void QueuePop(Queue* q)
{
	assert(q);
	assert(q->head != NULL);
	QNode* next = q->head->next;
	free(q->head);
	q->head = next;
	if (q->head == NULL)
		q->tail = NULL;
	q->size--;
}

這段代碼定義了一個(gè)名為 QueuePop 的函數(shù)，用于將隊(duì)列頭部的元素彈出隊(duì)列。函數(shù)中傳入一個(gè)指向 Queue 結(jié)構(gòu)體的指針 q。

函數(shù)的實(shí)現(xiàn)分為以下幾步：

使用 assert 宏檢查傳入的 q 不為空，以及隊(duì)列的 head 成員不為 NULL。如果檢查失敗，則直接返回。
將隊(duì)列的 head 節(jié)點(diǎn)的 next 指針賦值給 next，表示隊(duì)列頭部的下一個(gè)節(jié)點(diǎn)。
釋放隊(duì)列的 head 節(jié)點(diǎn)所占用的內(nèi)存空間。
將隊(duì)列的 head 指針指向 next，表示將隊(duì)列頭部的節(jié)點(diǎn)彈出隊(duì)列。
如果隊(duì)列的 head 成員為 NULL，則將隊(duì)列的 tail 成員也賦值為 NULL，表示隊(duì)列已經(jīng)為空。
將隊(duì)列的 size 成員減1，表示隊(duì)列中節(jié)點(diǎn)的數(shù)量減少了1。
由于隊(duì)列是由指針鏈表實(shí)現(xiàn)的，因此在彈出節(jié)點(diǎn)時(shí)需要釋放節(jié)點(diǎn)的內(nèi)存空間，并將相鄰節(jié)點(diǎn)的指針進(jìn)行修改。

// 獲取隊(duì)列頭部元素
QDataType QueueFront(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	return q->head->data;
}

這段代碼定義了一個(gè)名為 QueueFront 的函數(shù)，用于獲取隊(duì)列頭部的元素。函數(shù)中傳入一個(gè)指向 Queue 結(jié)構(gòu)體的指針 q。

函數(shù)的實(shí)現(xiàn)分為以下幾步：

使用 assert 宏檢查傳入的 q 不為空，以及隊(duì)列不為空。如果檢查失敗，則直接返回。
返回隊(duì)列的 head 節(jié)點(diǎn)的 data 成員，即隊(duì)列頭部的元素。
由于隊(duì)列是由指針鏈表實(shí)現(xiàn)的，因此可以通過(guò)訪問(wèn)隊(duì)列頭部節(jié)點(diǎn)的 data 成員來(lái)獲取隊(duì)列頭部的元素。

// 獲取隊(duì)列隊(duì)尾元素
QDataType QueueBack(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	return q->tail->data;
}

這段代碼定義了一個(gè)名為 QueueBack 的函數(shù)，用于獲取隊(duì)列尾部的元素。函數(shù)中傳入一個(gè)指向 Queue 結(jié)構(gòu)體的指針 q。

函數(shù)的實(shí)現(xiàn)分為以下幾步：

使用 assert 宏檢查傳入的 q 不為空，以及隊(duì)列不為空。如果檢查失敗，則直接返回。
返回隊(duì)列的 tail 節(jié)點(diǎn)的 data 成員，即隊(duì)列尾部的元素。
由于隊(duì)列是由指針鏈表實(shí)現(xiàn)的，因此可以通過(guò)訪問(wèn)隊(duì)列尾部節(jié)點(diǎn)的 data 成員來(lái)獲取隊(duì)列尾部的元素。

// 獲取隊(duì)列中有效元素個(gè)數(shù)
int QueueSize(Queue* q)
{
	assert(q);
	return q->size;
}

這段代碼定義了一個(gè)名為 QueueSize 的函數(shù)，用于獲取隊(duì)列中有效元素的數(shù)量。函數(shù)中傳入一個(gè)指向 Queue 結(jié)構(gòu)體的指針 q。

函數(shù)的實(shí)現(xiàn)非常簡(jiǎn)單，直接返回隊(duì)列的 size 成員，即隊(duì)列中有效元素的數(shù)量。由于 size 成員是在隊(duì)列的操作過(guò)程中動(dòng)態(tài)更新的，因此可以通過(guò)該成員來(lái)獲取隊(duì)列中有效元素的數(shù)量。

// 檢測(cè)隊(duì)列是否為空，如果為空返回非零結(jié)果，如果非空返回0
bool QueueEmpty(Queue* q)
{
	assert(q);
	return q->size == 0;
}

這段代碼定義了一個(gè)名為 QueueEmpty 的函數(shù)，用于判斷隊(duì)列是否為空。函數(shù)中傳入一個(gè)指向 Queue 結(jié)構(gòu)體的指針 q。

函數(shù)的實(shí)現(xiàn)非常簡(jiǎn)單，通過(guò)檢查隊(duì)列的 size 成員是否為0來(lái)判斷隊(duì)列是否為空。如果 size 等于0，則隊(duì)列為空，返回 true（非零結(jié)果），否則隊(duì)列非空，返回 false（0）。

// 銷毀隊(duì)列
void QueueDestroy(Queue* q)
{
	assert(q);
	QNode* cur = q->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	q->head = q->tail = NULL;
	q->size = 0;
}

這段代碼定義了一個(gè)名為 QueueDestroy 的函數(shù)，用于銷毀一個(gè)隊(duì)列。函數(shù)中傳入一個(gè)指向 Queue 結(jié)構(gòu)體的指針 q。

函數(shù)的實(shí)現(xiàn)分為以下幾步：

使用 assert 宏檢查傳入的 q 不為空。
將隊(duì)列的 head 指針賦值給 cur，表示從隊(duì)列的頭部開始銷毀節(jié)點(diǎn)。
循環(huán)遍歷隊(duì)列中的所有節(jié)點(diǎn)，每次將 cur 的 next 指針賦值給 next，然后釋放 cur 指向的節(jié)點(diǎn)所占用的內(nèi)存空間。
將 cur 指針指向 next，即將指針移動(dòng)到下一個(gè)節(jié)點(diǎn)，繼續(xù)進(jìn)行循環(huán)直到遍歷完所有節(jié)點(diǎn)。
將隊(duì)列的 head 和 tail 成員都賦值為 NULL，將隊(duì)列的 size 成員賦值為 0，表示隊(duì)列已經(jīng)被銷毀。
由于隊(duì)列是由指針鏈表實(shí)現(xiàn)的，因此在銷毀隊(duì)列時(shí)需要釋放每個(gè)節(jié)點(diǎn)所占用的內(nèi)存空間，并將指針移動(dòng)到下一個(gè)節(jié)點(diǎn)。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-498267.html

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
typedef int QDataType;
typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType data;
}QNode;
typedef struct Queue
{
	QNode* head;
	QNode* tail;
	int size;
}Queue;

// 初始化隊(duì)列
void QueueInit(Queue* q);
// 隊(duì)尾入隊(duì)列
void QueuePush(Queue* q, QDataType data);
// 隊(duì)頭出隊(duì)列
void QueuePop(Queue* q);
// 獲取隊(duì)列頭部元素
QDataType QueueFront(Queue* q);
// 獲取隊(duì)列隊(duì)尾元素
QDataType QueueBack(Queue* q);
// 獲取隊(duì)列中有效元素個(gè)數(shù)
int QueueSize(Queue* q);
// 檢測(cè)隊(duì)列是否為空，如果為空返回非零結(jié)果，如果非空返回0
bool QueueEmpty(Queue* q);
// 銷毀隊(duì)列
void QueueDestroy(Queue* q);

//初始化隊(duì)列
void QueueInit(Queue* q)
{
	assert(q);
	q->head = q->tail = NULL;
	q->size = 0;
}
// 隊(duì)尾入隊(duì)列
void QueuePush(Queue* q, QDataType data)
{
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}
	newnode->data = data;
	newnode->next = NULL;

	if (q->head == NULL)
	{
		assert(q->tail == NULL);
		q->head = q->tail = newnode;
	}
	else
	{
		q->tail->next = newnode;
		q->tail = newnode;
	}
	q->size++;

}
// 隊(duì)頭出隊(duì)列
void QueuePop(Queue* q)
{
	assert(q);
	assert(q->head != NULL);
	QNode* next = q->head->next;
	free(q->head);
	q->head = next;
	if (q->head == NULL)
		q->tail = NULL;
	q->size--;
}
// 獲取隊(duì)列頭部元素
QDataType QueueFront(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	return q->head->data;
}
// 獲取隊(duì)列隊(duì)尾元素
QDataType QueueBack(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	return q->tail->data;
}
// 獲取隊(duì)列中有效元素個(gè)數(shù)
int QueueSize(Queue* q)
{
	assert(q);
	return q->size;
}
// 檢測(cè)隊(duì)列是否為空，如果為空返回非零結(jié)果，如果非空返回0
bool QueueEmpty(Queue* q)
{
	assert(q);
	return q->size == 0;
}
// 銷毀隊(duì)列
void QueueDestroy(Queue* q)
{
	assert(q);
	QNode* cur = q->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	q->head = q->tail = NULL;
	q->size = 0;
}
int main()
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, 1);
	QueuePush(&q, 2);
	QueuePush(&q, 3);
	QueuePush(&q, 4);
	QueuePush(&q, 5);
	while (!QueueEmpty(&q))
	{
		printf("%d ", QueueFront(&q));
		QueuePop(&q);
	}
	printf("\n");
	
	QueueDestroy(&q);
	return 0;
}
	

到了這里，關(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)！