【數(shù)據(jù)結(jié)構(gòu)】C語(yǔ)言隊(duì)列(詳解)

這篇具有很好參考價(jià)值的文章主要介紹了【數(shù)據(jù)結(jié)構(gòu)】C語(yǔ)言隊(duì)列(詳解)。希望對(duì)大家有所幫助。如果存在錯(cuò)誤或未考慮完全的地方，請(qǐng)大家不吝賜教，您也可以點(diǎn)擊"舉報(bào)違法"按鈕提交疑問(wèn)。

前言:

????個(gè)人主頁(yè):??????Dream_Chaser～?????

??專(zhuān)欄:http://t.csdn.cn/oXkBa

??本篇內(nèi)容:c語(yǔ)言數(shù)據(jù)結(jié)構(gòu)--C語(yǔ)言實(shí)現(xiàn)隊(duì)列

一.隊(duì)列概念及結(jié)構(gòu)

1.1隊(duì)列的概念

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

二.隊(duì)列的實(shí)現(xiàn)

2.1頭文件

2.2鏈?zhǔn)疥?duì)列的結(jié)構(gòu)定義

2.3隊(duì)列接口的定義

2.4初始化隊(duì)列

2.5判斷隊(duì)列是否為空

2.6銷(xiāo)毀隊(duì)列

2.7隊(duì)尾入隊(duì)列

2.8隊(duì)頭出隊(duì)列

2.9獲取隊(duì)列頭部元素

2.10獲取隊(duì)列隊(duì)尾元素

2.11獲取隊(duì)列中有效元素個(gè)數(shù)

2.12打印隊(duì)列元素

Test.c

Queue.h

Queue.c

一.隊(duì)列概念及結(jié)構(gòu)

1.1隊(duì)列的概念

隊(duì)列：只允許 在一端進(jìn)行插入數(shù)據(jù)操作，在 另一端進(jìn)行刪除數(shù)據(jù)操作的特殊線(xiàn)性表，隊(duì)列具有 先進(jìn)先出 FIFO(First In First Out)

入隊(duì)列： 進(jìn)行插入操作的一端稱(chēng)為 隊(duì)尾

出隊(duì)列： 進(jìn)行刪除操作的一端稱(chēng)為 隊(duì)頭

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

二.隊(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ì)比較低

2.1頭文件

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

2.2鏈?zhǔn)疥?duì)列的結(jié)構(gòu)定義

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

typedef struct Queue
{
	QNode* phead;
	QNode* ptail;
	int size;
}Queue;//表示隊(duì)列整體,一個(gè)是出數(shù)據(jù)，一個(gè)是入數(shù)據(jù).

? QueueNode結(jié)構(gòu)體表示隊(duì)列中的節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)包含一個(gè)數(shù)據(jù)項(xiàng)?data?和一個(gè)指向下一個(gè)節(jié)點(diǎn)的指針?next。Queue結(jié)構(gòu)體表示整個(gè)隊(duì)列，包含指向隊(duì)列頭部和尾部節(jié)點(diǎn)的指針?phead?和?ptail，以及記錄隊(duì)列大小的變量?size

2.3隊(duì)列接口的定義

void QueueInit(Queue* pq);// 初始化隊(duì)列

void QueueDestroy(Queue* pq);// 銷(xiāo)毀隊(duì)列

void QueuePush(Queue* pq, QDataType x);// 隊(duì)尾入隊(duì)列

void QueuePop(Queue* pq);// 隊(duì)頭出隊(duì)列

QDataType QueueFront(Queue* pq);// 獲取隊(duì)列頭部元素

QDataType QueueBack(Queue* pq);// 獲取隊(duì)列隊(duì)尾元素

int QueueSize(Queue* pq);// 獲取隊(duì)列中有效元素個(gè)數(shù)

bool QueueEmpty(Queue* pq);// 檢測(cè)隊(duì)列是否為空，如果為空返回非零結(jié)果，如果非空返回0

2.4初始化隊(duì)列

void QueueInit(Queue* pq)
{
	assert(pq);// 檢查指針是否為空
	pq->phead=NULL; //將隊(duì)列的頭指針置為空
	pq->ptail = NULL;//將隊(duì)列的尾指針置為空
	pq->size = 0;// 將隊(duì)列的頭指針置為空
}

2.5判斷隊(duì)列是否為空

bool QueueEmpty(Queue* pq)
{
	assert(pq);
	
	//方法一,將隊(duì)列的頭指針以及尾指針置空
	//return pq->phead = NULL && pq->ptail==NULL;
	
	//方法二,將隊(duì)列的有效元素置空
	return pq->size == 0;
}

2.6銷(xiāo)毀隊(duì)列

代碼解析:

assert(pq)?用于斷言?pq?指針不為空，確保傳入的指針有效。

創(chuàng)建一個(gè)指針?cur，并將其初始化為隊(duì)列的頭指針?pq->phead。

進(jìn)入循環(huán)，遍歷隊(duì)列中的每個(gè)節(jié)點(diǎn)。

在循環(huán)中，首先保存當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)指針為?next，以便在釋放當(dāng)前節(jié)點(diǎn)后能夠訪(fǎng)問(wèn)下一個(gè)節(jié)點(diǎn)。

使用?free(cur)?釋放當(dāng)前節(jié)點(diǎn)的內(nèi)存。

將指針?cur?移動(dòng)到下一個(gè)節(jié)點(diǎn)，即?cur = next。

循環(huán)繼續(xù)，直到遍歷完隊(duì)列中的所有節(jié)點(diǎn)。

在循環(huán)結(jié)束后，將隊(duì)列的頭指針和尾指針?pq->phead、pq->ptail?都置為空，表示隊(duì)列已經(jīng)為空。

將隊(duì)列的大小?pq->size?置為 0，表示隊(duì)列中沒(méi)有元素。

void QueueDestroy(Queue* pq)
{
	assert(pq);// 檢查指針是否為空
	QNode* cur = pq->phead;// 創(chuàng)建一個(gè)指針 cur，指向隊(duì)列的頭指針
	while (cur)
	{
		QNode* next = cur->next;// 創(chuàng)建一個(gè)指針 cur，指向隊(duì)列的頭指針
		free(cur);// 釋放當(dāng)前節(jié)點(diǎn)的內(nèi)存
		cur = next;// 將指針 cur 移動(dòng)到下一個(gè)節(jié)點(diǎn)
	}
	pq->phead = pq->ptail = NULL;// 將隊(duì)列的頭指針和尾指針置為空
	pq->size = 0;// 將隊(duì)列的大小置為0
}

2.7隊(duì)尾入隊(duì)列

第一種情況:尾插第一個(gè)隊(duì)列元素

第二種情況:已有元素前提下尾插節(jié)點(diǎn)

先尾插節(jié)點(diǎn)，后把新節(jié)點(diǎn)的地址給ptail(讓ptail指向新節(jié)點(diǎn))

void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));// 創(chuàng)建一個(gè)新的節(jié)點(diǎn)

	if (newnode == NULL)
	{
		perror("malloc fail\n");// 檢查內(nèi)存分配是否成功
		return;
	}
	newnode->data = x;// 設(shè)置新節(jié)點(diǎn)的數(shù)據(jù)為傳入的元素值
	newnode->next = NULL;// 將新節(jié)點(diǎn)的指針域置空

	//一個(gè)節(jié)點(diǎn)
	
	if (pq->ptail == NULL)// 判斷隊(duì)列是否為空
	{
		assert(pq->phead == NULL);// 如果隊(duì)列為空，頭指針也應(yīng)為空
		pq->phead = pq->ptail = newnode;// 將新節(jié)點(diǎn)同時(shí)設(shè)置為隊(duì)列的頭節(jié)點(diǎn)和尾節(jié)點(diǎn)
	}
    //多個(gè)節(jié)點(diǎn)
	else
	{
		pq->ptail->next = newnode;// 將新節(jié)點(diǎn)同時(shí)設(shè)置為隊(duì)列的頭節(jié)點(diǎn)和尾節(jié)點(diǎn)
		pq->ptail = newnode;// 更新隊(duì)列的尾指針為新節(jié)點(diǎn)
	}
	pq->size++;// 增加隊(duì)列的大小計(jì)數(shù)
}

代碼執(zhí)行:?

【數(shù)據(jù)結(jié)構(gòu)】C語(yǔ)言隊(duì)列(詳解),C--數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),c語(yǔ)言,算法,鏈表,開(kāi)發(fā)語(yǔ)言,筆記

2.8隊(duì)頭出隊(duì)列

第一種:隊(duì)列只有一個(gè)元素時(shí)

第二種:隊(duì)列有多個(gè)元素時(shí)

void QueuePop(Queue* pq)
{
	assert(pq);// 檢查指針是否為空
	assert(!QueueEmpty(pq));// 檢查隊(duì)列是否非空
	assert(pq->phead);// 檢查隊(duì)列的頭指針是否存在
	//1.一個(gè)節(jié)點(diǎn)
	if (pq->phead->next == NULL) // 隊(duì)列只有一個(gè)節(jié)點(diǎn)的情況
	{
		free(pq->phead); // 釋放隊(duì)列頭節(jié)點(diǎn)的內(nèi)存
		pq->phead = pq->ptail = NULL;// 將隊(duì)列的頭指針和尾指針置為空
	}
    //2.多個(gè)節(jié)點(diǎn)
	else
	{
		QNode* next = pq->phead->next; //保存隊(duì)列頭節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)指針
		free(pq->phead);// 釋放隊(duì)列頭節(jié)點(diǎn)的內(nèi)存
		pq->phead = next;// 更新隊(duì)列的頭指針為下一個(gè)節(jié)點(diǎn)
	}
	pq->size--;//減少隊(duì)列的大小計(jì)數(shù)
}

代碼執(zhí)行:?

2.9獲取隊(duì)列頭部元素

QDataType QueueFront(Queue* pq)
{
	assert(pq);// 檢查指針是否為空
	assert(!QueueEmpty(pq));// 檢查隊(duì)列是否非空
	assert(pq->phead);// 檢查隊(duì)列的頭指針是否存在
 
	return pq->phead->data;// 返回隊(duì)列頭節(jié)點(diǎn)的數(shù)據(jù)
}

代碼執(zhí)行:

2.10獲取隊(duì)列隊(duì)尾元素

QDataType QueueBack(Queue* pq)
{
	assert(pq);// 檢查隊(duì)列是否非空
	assert(!QueueEmpty(pq));// 檢查隊(duì)列是否非空
	assert(pq->ptail);// 檢查隊(duì)列的尾指針是否存在
	
	return pq->ptail->data;//返回隊(duì)列尾節(jié)點(diǎn)的數(shù)據(jù)
}

代碼執(zhí)行:

2.11獲取隊(duì)列中有效元素個(gè)數(shù)

int QueueSize(Queue* pq)
{
	assert(pq);//檢查指針是否為空

	return pq->size;//返回隊(duì)列的大小（元素個(gè)數(shù)）
}

代碼執(zhí)行:

2.12打印隊(duì)列元素

void QPrint(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->phead;
	QNode* next = cur;
	while (cur != NULL)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
}

代碼執(zhí)行:?

Test.c

#include"Queue.h"
void TestQueue1()//元素入隊(duì)列
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q,1);
	QueuePush(&q,2);	
	//printf("%d ", QueueFront(&q));
	//QueuePop(&q);
	QueuePush(&q,3);
	QueuePush(&q,4);
	//printf("Size:%d\n", QueueSize(&q));
	//QPrint(&q);
	while (!QueueEmpty(&q))
	{
		printf("%d ", QueueFront(&q));
		QueuePop(&q);
	}
	printf("\n");
}
void TestQueue2()//元素出隊(duì)列
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, 1);
	QueuePush(&q, 2);
	QueuePush(&q, 3);
	QueuePush(&q, 4);
	printf("%d\n", QueueFront(&q));
	QueuePop(&q);
	printf("%d\n", QueueFront(&q));
	QueuePop(&q);
	printf("%d\n", QueueFront(&q));
	QueuePop(&q);
	printf("%d\n", QueueFront(&q));
	
	printf("\n");
}
void TestQueue3()//獲取隊(duì)列頭部和尾部元素,和隊(duì)列元素個(gè)數(shù)
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, 1);
	QueuePush(&q, 2);
	QueuePush(&q, 3);
	QueuePush(&q, 4);
	printf("隊(duì)列頭部元素:%d\n",QueueFront(&q));
	printf("隊(duì)列尾部元素:%d\n", QueueBack(&q));
	printf("Size:%d\n", QueueSize(&q));

	/*while (!QueueEmpty(&q))
	{
		printf("%d ", QueueFront(&q));
		QueuePop(&q);
	}*/
	printf("\n");
}
void TestQueue4()//打印隊(duì)列
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, 1);
	QueuePush(&q, 2);
	QueuePush(&q, 3);
	QueuePush(&q, 4);
	QPrint(&q);
	printf("\n");
}
int main()
{
	//TestQueue1();//元素入隊(duì)列
	//TestQueue2();//元素出隊(duì)列
	//TestQueue3();//獲取隊(duì)列頭部和尾部元素,和隊(duì)列元素個(gè)數(shù)
	TestQueue4();
}

Queue.h

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdbool.h>
#include<stdlib.h>
typedef int QDataType;
typedef struct QueueNode
{	
	QDataType data;
	struct QueueNode* next;
}QNode;

typedef struct Queue
{
	QNode* phead;
	QNode* ptail;
	int size;
}Queue;//表示隊(duì)列整體,一個(gè)是出數(shù)據(jù)，一個(gè)是入數(shù)據(jù).

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

Queue.c

#include"Queue.h"
void QueueInit(Queue* pq)
{
	assert(pq);// 檢查指針是否為空
	pq->phead=NULL; // 將隊(duì)列的頭指針置為空
	pq->ptail = NULL;// 將隊(duì)列的頭指針置為空
	pq->size = 0;// 將隊(duì)列的頭指針置為空
}

void QPrint(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->phead;
	QNode* next = cur;
	while (cur != NULL)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
}

void QueueDestroy(Queue* pq)
{
	assert(pq);// 檢查指針是否為空
	QNode* cur = pq->phead;// 創(chuàng)建一個(gè)指針 cur，指向隊(duì)列的頭指針
	while (cur)
	{
		QNode* next = cur->next;// 創(chuàng)建一個(gè)指針 cur，指向隊(duì)列的頭指針
		free(cur);// 釋放當(dāng)前節(jié)點(diǎn)的內(nèi)存
		cur = next;// 將指針 cur 移動(dòng)到下一個(gè)節(jié)點(diǎn)
	}
	pq->phead = pq->ptail = NULL;// 將隊(duì)列的頭指針和尾指針置為空
	pq->size = 0;// 將隊(duì)列的大小置為0
}

void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));// 創(chuàng)建一個(gè)新的節(jié)點(diǎn)

	if (newnode == NULL)
	{
		perror("malloc fail\n");// 檢查內(nèi)存分配是否成功
		return;
	}
	newnode->data = x;// 設(shè)置新節(jié)點(diǎn)的數(shù)據(jù)為傳入的元素值
	newnode->next = NULL;// 將新節(jié)點(diǎn)的指針域置空

	//一個(gè)節(jié)點(diǎn)
	//多個(gè)節(jié)點(diǎn)
	if (pq->ptail == NULL)// 判斷隊(duì)列是否為空
	{
		assert(pq->phead == NULL);// 如果隊(duì)列為空，頭指針也應(yīng)為空
		pq->phead = pq->ptail = newnode;// 將新節(jié)點(diǎn)同時(shí)設(shè)置為隊(duì)列的頭節(jié)點(diǎn)和尾節(jié)點(diǎn)
	}
	else
	{
		pq->ptail->next = newnode;// 將新節(jié)點(diǎn)同時(shí)設(shè)置為隊(duì)列的頭節(jié)點(diǎn)和尾節(jié)點(diǎn)
		pq->ptail = newnode;// 更新隊(duì)列的尾指針為新節(jié)點(diǎn)
	}
	pq->size++;// 增加隊(duì)列的大小計(jì)數(shù)
}

void QueuePop(Queue* pq)
{
	assert(pq);// 檢查指針是否為空
	assert(!QueueEmpty(pq));// 檢查隊(duì)列是否非空
	assert(pq->phead);// 檢查隊(duì)列的頭指針是否存在
	//1.一個(gè)節(jié)點(diǎn)
	if (pq->phead->next == NULL) // 隊(duì)列只有一個(gè)節(jié)點(diǎn)的情況
	{
		free(pq->phead); // 釋放隊(duì)列頭節(jié)點(diǎn)的內(nèi)存
		pq->phead = pq->ptail = NULL;// 將隊(duì)列的頭指針和尾指針置為空
	}
	else
	{
		//頭刪
		QNode* next = pq->phead->next; //保存隊(duì)列頭節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)指針
		free(pq->phead);// 釋放隊(duì)列頭節(jié)點(diǎn)的內(nèi)存
		pq->phead = next;// 更新隊(duì)列的頭指針為下一個(gè)節(jié)點(diǎn)
	}
	pq->size--;//減少隊(duì)列的大小計(jì)數(shù)
}

QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));// 檢查隊(duì)列是否非空
	assert(pq->phead);// 檢查隊(duì)列的頭指針是否存在
 
	return pq->phead->data;// 返回隊(duì)列頭節(jié)點(diǎn)的數(shù)據(jù)
}
  
QDataType QueueBack(Queue* pq)
{
	assert(pq);// 檢查隊(duì)列是否非空
	assert(!QueueEmpty(pq));// 檢查隊(duì)列是否非空
	assert(pq->phead);// 檢查隊(duì)列的頭指針是否存在
	
	return pq->ptail->data;//返回隊(duì)列尾節(jié)點(diǎn)的數(shù)據(jù)
}

int QueueSize(Queue* pq)
{
	assert(pq);//檢查指針是否為空

	return pq->size;//返回隊(duì)列的大?。ㄔ貍€(gè)數(shù)）
}
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	
	//方法一,將隊(duì)列的頭指針以及尾指針置空
	//return pq->phead = NULL && pq->ptail==NULL;
	
	//方法二,將隊(duì)列的有效元素置空
	return pq->size == 0;
}

? ? ? ? 本篇結(jié)束，如有錯(cuò)誤，歡迎大家指正，感謝來(lái)訪(fǎng)！文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-689153.html

到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】C語(yǔ)言隊(duì)列(詳解)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！