快捷導(dǎo)航

C語(yǔ)言中隊(duì)列的結(jié)構(gòu)和函數(shù)接口的使用示例

更新時(shí)間：2023年02月14日 14:32:11 作者：[Pokemon]大貓貓

隊(duì)列只允許一端進(jìn)行插入數(shù)據(jù)操作，在另一端進(jìn)行刪除數(shù)據(jù)操作的特殊線性表，隊(duì)列具有先進(jìn)先出FIFO的性質(zhì)；隊(duì)列可用數(shù)組和鏈表的方法實(shí)現(xiàn)，使用鏈表的結(jié)構(gòu)實(shí)現(xiàn)更優(yōu)一些，因?yàn)槿绻褂脭?shù)組節(jié)，出隊(duì)列時(shí)刪去首元素需要將整個(gè)數(shù)組前移，效率比較低

一、隊(duì)列的結(jié)構(gòu)

隊(duì)列：一種操作受限的線性表，只允許在線性表的一端進(jìn)行插入，另一端進(jìn)行刪除，插入的一端稱為隊(duì)尾，刪除的一端稱為隊(duì)頭

通過(guò) 動(dòng)態(tài)順序表的實(shí)現(xiàn)，可以發(fā)現(xiàn)在數(shù)組的頭部進(jìn)行插入刪除操作時(shí)，需要移動(dòng)數(shù)據(jù)，效率較低，因此不采用數(shù)組來(lái)實(shí)現(xiàn)隊(duì)列

但通過(guò) 單鏈表的實(shí)現(xiàn)，可以發(fā)現(xiàn)在對(duì)單鏈表進(jìn)行頭插時(shí)效率很高，而進(jìn)行尾插時(shí)，需要找尾數(shù)據(jù)，較為麻煩，但是可以通過(guò)增加一個(gè)尾指針的方式來(lái)提升效率，因此用單鏈表的頭尾指針來(lái)實(shí)現(xiàn)隊(duì)列，結(jié)構(gòu)如下：

//隊(duì)列的元素類型
typedef int QueueDataType;
//隊(duì)列的結(jié)點(diǎn)結(jié)構(gòu)
typedef struct QueueNode
{
	QueueDataType data;
	struct QueueNode* next;
}QNode;
//隊(duì)列結(jié)構(gòu)，需要包含指向鏈表的頭指針和尾指針
//為了求隊(duì)列數(shù)據(jù)個(gè)數(shù)時(shí)，時(shí)間復(fù)雜度為 O(1)，這里增加一個(gè) size 變量
typedef struct Queue
{
	QNode* head;
	QNode* tail;
	int size;
}Queue;

二、隊(duì)列的函數(shù)接口

1. 初始化和銷毀

初始化函數(shù)如下：

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

鏈表的結(jié)點(diǎn)都是動(dòng)態(tài)開(kāi)辟的，不用隊(duì)列時(shí)，應(yīng)當(dāng)銷毀

銷毀函數(shù)如下：

void QueueDestroy(Queue* pq)
{
	assert(pq);
	//從頭結(jié)點(diǎn)開(kāi)始銷毀
	QNode* cur = pq->head;
	while (cur)
	{
		//保存下一個(gè)結(jié)點(diǎn)
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;
	pq->size = 0;
}

2. 入隊(duì)和出隊(duì)

入隊(duì)：在隊(duì)尾插入元素

入隊(duì)函數(shù)如下：

void QueuePush(Queue* pq, QueueDataType x)
{
	assert(pq);
	//創(chuàng)建新結(jié)點(diǎn)
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	//沒(méi)有結(jié)點(diǎn)時(shí)，插入元素，需要改變隊(duì)列的頭尾指針
	//有結(jié)點(diǎn)時(shí)，直接鏈接在尾結(jié)點(diǎn)之后，tail 變成新的尾
	if (pq->tail == NULL)
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
	//插入元素后，數(shù)據(jù)個(gè)數(shù)需要自增
	pq->size++;
}

出隊(duì)：刪除隊(duì)頭元素

出隊(duì)函數(shù)如下：

void QueuePop(Queue* pq)
{
	assert(pq);
	//沒(méi)有元素時(shí)，不能刪除，這里直接調(diào)用判空函數(shù)
	assert(!QueueEmpty(pq));
	//如果只有一個(gè)結(jié)點(diǎn)時(shí)，需要改變隊(duì)列的頭尾指針
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
	//刪除元素后，數(shù)據(jù)個(gè)數(shù)需要自減
	pq->size--;
}

3. 訪問(wèn)隊(duì)頭和隊(duì)尾元素

訪問(wèn)隊(duì)頭元素函數(shù)如下：

QueueDataType QueueFront(Queue* pq)
{
	assert(pq);
	//沒(méi)有元素時(shí)，不能取隊(duì)頭元素，這里直接調(diào)用判空函數(shù)
	assert(!QueueEmpty(pq));
	return pq->head->data;
}

訪問(wèn)隊(duì)尾元素函數(shù)如下：

QueueDataType QueueBack(Queue* pq)
{
	assert(pq);
	//沒(méi)有元素時(shí)，不能取隊(duì)尾元素，這里直接調(diào)用判空函數(shù)
	assert(!QueueEmpty(pq));
	return pq->tail->data;
}

4. 判空和元素個(gè)數(shù)

判空函數(shù)如下：

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

元素個(gè)數(shù)函數(shù)如下：

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

到此這篇關(guān)于C語(yǔ)言中隊(duì)列的結(jié)構(gòu)和函數(shù)接口的使用示例的文章就介紹到這了,更多相關(guān)C語(yǔ)言隊(duì)列結(jié)構(gòu)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: