前言

??當(dāng)我們編寫程序時，經(jīng)常需要處理各種數(shù)據(jù)結(jié)構(gòu)。隊列是一種常見的數(shù)據(jù)結(jié)構(gòu)，它有著廣泛的應(yīng)用場景。隊列的基本操作包括入隊和出隊，應(yīng)用于模擬等待隊列、消息隊列、計算機緩存等場合。

??在實際編程中，我們可以用不同的數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)隊列。本文主要介紹了三種不同的隊列實現(xiàn)方式，包括帶頭結(jié)點單向隊列、不帶頭結(jié)點單向隊列和循環(huán)隊列。這些隊列實現(xiàn)方式分別使用了鏈表、數(shù)組等不同的數(shù)據(jù)結(jié)構(gòu)，在實現(xiàn)細(xì)節(jié)、時間復(fù)雜度和空間利用率等方面具有不同的特點。對于程序員來說，了解不同的隊列實現(xiàn)方式，可以更好地選擇適合自己應(yīng)用場景的隊列實現(xiàn)方式，提高程序的效率。

隊列實現(xiàn)

??隊列是一種先進(jìn)先出（First-In-First-Out, FIFO）的數(shù)據(jù)結(jié)構(gòu)，它的基本操作包括入隊（將元素插入隊尾）和出隊（將隊首元素刪除）。

帶頭結(jié)點單向隊列

• 帶頭結(jié)點單向隊列是一種使用鏈表實現(xiàn)的隊列，與普通鏈表不同的是，帶頭結(jié)點單向隊列在鏈表頭部添加一個不存儲數(shù)據(jù)的節(jié)點，作為鏈表的頭結(jié)點，用于方便隊列的操作。

• 在帶頭結(jié)點單向隊列中，入隊操作是將新元素插入到鏈表尾部，出隊操作是將隊首元素的后繼節(jié)點作為新的隊首節(jié)點。

• 由于鏈表的特性，帶頭結(jié)點單向隊列的入隊操作是 $O(1)$ 的，而出隊操作需要遍歷整個鏈表，因此其時間復(fù)雜度為 $O(n)$，其中 $n$ 表示隊列的元素個數(shù)。

??下面展示一張圖表示隊列插入的邏輯：

??隊列節(jié)點結(jié)構(gòu)體設(shè)計：

// 節(jié)點結(jié)構(gòu)體
struct queueNode
{
	// 數(shù)據(jù)元素
	int elem;
	// 指向下一個元素
	struct queueNode *next;
};

struct queue
{
	// 尾部
	struct queueNode *rear;
	// 頭部
	struct queueNode *front;
	// 長度
	int lenth;
};

??代碼實現(xiàn)：

/********************** 含頭結(jié)點 ***************/
// 隊列初始化
struct queue*queueInit()
{
	// 申請空間并且初始化
	struct queue*res = (struct queue*)malloc(sizeof(struct queue));
	// 初始化一個虛擬節(jié)點
	struct queueNode*node = (struct queueNode*)malloc(sizeof(struct queueNode));
	res->front = node;
	res->rear = node;
	res->lenth = 0;
	return res;
}

// 入隊列
void pushQueueNode(struct queue*queue, int elem)
{
	// 新建一個節(jié)點
	struct queueNode*node = (struct queueNode*)malloc(sizeof(struct queueNode));
	node->elem = elem;
	node->next = NULL;

	// 添加到尾部
	queue->rear->next = node;
	queue->rear = node;
	queue->lenth++;
}

// 出隊列
bool pullQueueNode(struct queue*queue, int&elem)
{
	// 判斷隊列是否為空
	if (queueIsEmpty(queue))
		return true;

	// 移除隊列中的首元素
	struct queueNode*p = queue->front->next;
	elem = p->elem;
	queue->front->next = p->next;
	queue->lenth--;
	// 隊列中只有一個元素應(yīng)該改變隊尾指針
	if (queue->rear == p)
		queue->rear = queue->front;
	free(p);
	return false;
}

// 判斷隊列是否空
bool queueIsEmpty(struct queue*queue)
{
	return queue->lenth == 0;
}

// 打印隊列
void outPutQueue(struct queue*queue)
{
	// 判斷隊列是否為空
	if (queue->lenth == 0)
		return;
	struct queueNode*p = queue->front->next;
	// 遍歷隊列并打印
	printf("queue:");
	while (p)
	{
		printf("%d ",p->elem);
		p = p->next;
	}
	printf("\n");
}

不帶頭結(jié)點單向隊列

• 與帶頭結(jié)點單向隊列相比，不帶頭結(jié)點單向隊列不使用頭結(jié)點，直接從鏈表的第一個節(jié)點開始存儲數(shù)據(jù)。

• 在不帶頭結(jié)點單向隊列中，入隊操作是將新元素插入到鏈表尾部，出隊操作是刪除鏈表的頭結(jié)點，并將頭結(jié)點的后繼節(jié)點作為新的隊首節(jié)點。

• 由于每次出隊操作都需要刪除鏈表的頭結(jié)點，因此不帶頭結(jié)點單向隊列中的實現(xiàn)會導(dǎo)致頻繁的內(nèi)存分配和釋放，效率比較低。

??其插入操作的圖解為：

??隊列節(jié)點結(jié)構(gòu)體設(shè)計：

struct queueNode
{
	// 數(shù)據(jù)元素
	int elem;
	// 指向下一個元素
	struct queueNode *next;
};

??代碼實現(xiàn)：

/********************** 不含頭結(jié)點 ***************/
// 隊列初始化
struct queue*vQueueInit()
{
	// 申請空間并且賦值
	struct queue*res = (struct queue*)malloc(sizeof(struct queue));
	res->lenth = 0;
	res->front = res->rear = NULL;
	return res;
}

// 打印隊列
void vOutPutQueue(struct queue*queue)
{
	printf("queue:");
	struct queueNode*p = queue->front;
	// 遍歷打印
	while (p)
	{
		printf("%d ",p->elem);
		p = p->next;
	}
	printf("\n");
}

// 入隊列
void vPushQueueNode(struct queue*queue, int elem)
{
	// 申請一個節(jié)點
	struct queueNode *p = (struct queueNode*)malloc(sizeof(struct queueNode));
	p->elem = elem;
	p->next = NULL;
	// 隊列為空時入隊列
	if (queue->lenth == 0) 
	{
		queue->front = p;
		queue->rear = p;
	}
	else
	{
		// 先將節(jié)點接到隊列上
		queue->rear->next = p;
		// 再移動隊列尾指針
		queue->rear = p;
	}
	queue->lenth++;
}

// 出隊列
bool vPullQueueNode(struct queue*queue, int&elem)
{
	// 判斷隊列是否為空
	if (vQueueIsEmpty(queue))
		return false;

	// 獲取隊列首元素 并返回
	struct queueNode*p = queue->front;
	elem = p->elem;
	queue->front = p->next;
	queue->lenth--;

	return true;
}

// 判斷隊列是否空
bool vQueueIsEmpty(struct queue*queue)
{
	return queue->lenth == 0;
}

??與含頭結(jié)點隊列操作上的區(qū)別：主要在于入隊列與出隊列時需要判斷隊列是否為空。

循環(huán)隊列

• 循環(huán)隊列是一種使用數(shù)組實現(xiàn)的隊列，與普通數(shù)組不同的是，循環(huán)隊列的隊尾指針和隊首指針可以在達(dá)到數(shù)組的末尾位置時循環(huán)到數(shù)組的開頭位置。

• 在循環(huán)隊列中，需要使用兩個指針分別指向隊首和隊尾，或者使用一個指針和隊列長度維護隊首和隊尾位置。

• 在循環(huán)隊列中，入隊操作是將新元素插入到隊尾，如果隊列滿了，則會返回隊列已滿的錯誤；出隊操作是將隊首元素刪除，并將隊首指針指向下一個元素。

• 循環(huán)隊列的主要優(yōu)點是空間利用率比較高，可以實現(xiàn)環(huán)形存儲，而且操作的時間復(fù)雜度比帶頭結(jié)點單向隊列和不帶頭結(jié)點單向隊列都要高效，都是 $O(1)$。

??隊列結(jié)構(gòu)體設(shè)計：

// 隊列的最大長度
#define QUEUEMAXSIZE 10
// 隊列結(jié)構(gòu)體
struct queueCirculate
{
	// 存儲數(shù)據(jù)
	int data[QUEUEMAXSIZE];
	// 記錄數(shù)量
	int count;
	// 記錄隊列隊頭
	int front;
	// 記錄隊列隊尾
	int rear;
};

??隊列節(jié)點結(jié)構(gòu)體設(shè)計：

******************** 循環(huán)隊列 ******************/
// 初始化循環(huán)隊列
struct queueCirculate*queueCirculateInit(void)
{
	// 申請空間
	struct queueCirculate*res = (struct queueCirculate*)malloc(sizeof(struct queueCirculate));
	// 初始化隊列的數(shù)量 隊頭隊尾的位置
	res->count = 0;
	res->front = 0;
	res->rear = 0;

	return res;
}

// 入隊列
bool pushQueueCirculate(struct queueCirculate*queue,int elem)
{
	// 判斷隊列是否已滿
	if (queue->count == QUEUEMAXSIZE)
		return false;
	// 入隊列
	queue->data[queue->rear] = elem;
	// 改變隊尾指針的位置 以及 隊列的數(shù)量
	queue->count++;
	if (queue->count < QUEUEMAXSIZE)
		queue->rear = (queue->rear + 1) % QUEUEMAXSIZE;
	return true;
}

// 出隊列
bool pullQueueCirculate(struct queueCirculate*queue, int&elem)
{
	// 判斷隊列是否為空
	if (queue->count == 0)
		return false;
	// 出隊列
	elem = queue->data[queue->front];
	// 移動隊頭指針 并且 改變隊列元素數(shù)量
	queue->front = (queue->front + 1) % QUEUEMAXSIZE;
	queue->count--;
	return true;
}

// 隊列是否為空
bool queueCirculateIsEmpty(struct queueCirculate*queue)
{
	return queue->count == 0;
}

// 打印隊列
void outPutQueueCirculate(struct queueCirculate*queue)
{
	int count = queue->count;
	printf("queue: ");
	for (int i = 0; i < count; ++i)
	{
		int temp = -1;
		pullQueueCirculate(queue, temp);
		printf("%d ", temp);
	}
	printf("\n");
}

總結(jié)

??帶頭結(jié)點單向隊列、不帶頭結(jié)點單向隊列和循環(huán)隊列各有優(yōu)缺點，適用于不同的應(yīng)用場景：

??帶頭結(jié)點單向隊列適用于需要實現(xiàn)入隊操作頻繁、出隊操作較少的場景。它可以利用鏈表的特性，實現(xiàn)入隊操作的時間復(fù)雜度為 O(1)，缺點是出隊操作的時間復(fù)雜度為 O(n)。

??不帶頭結(jié)點單向隊列適用于隊列長度較短的需要入隊和出隊操作都比較頻繁的場景。由于不使用頭結(jié)點，可以節(jié)省一些空間，但出隊操作需要頻繁的內(nèi)存分配和釋放，效率比較低。

??循環(huán)隊列適用于隊列長度較大且入隊和出隊操作都比較頻繁的場景。它的環(huán)形存儲結(jié)構(gòu)可以充分利用數(shù)組的連續(xù)存儲空間，實現(xiàn)了空間的高效利用。同時，入隊和出隊操作的時間復(fù)雜度都為 O(1)，效率比較高。但是，循環(huán)隊列需要事先定義一個最大長度，如果隊列長度超過了最大長度，需要進(jìn)行擴容操作。此外，由于環(huán)形結(jié)構(gòu)的特殊性，實現(xiàn)起來也比較復(fù)雜。

??因此，在選擇隊列實現(xiàn)方式時，需要根據(jù)具體的應(yīng)用場景綜合考慮時間復(fù)雜度、空間利用率和實現(xiàn)難度等因素，選擇最適合自己的隊列實現(xiàn)方式。文章來源地址http://www.zghlxwxcb.cn/news/detail-478720.html

到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)與算法分析】使用C語言實現(xiàn)隊列的兩種（帶頭結(jié)點與不帶頭結(jié)點）鏈?zhǔn)酱鎯?，并且給出一種循環(huán)隊列的設(shè)計思想的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！