C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)算法基礎(chǔ)之循環(huán)隊(duì)列示例

更新時(shí)間：2022年06月06日 10:20:02 作者：jiangwei0512

這篇文章主要為大家介紹了C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)算法基礎(chǔ)之循環(huán)隊(duì)列，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪

說(shuō)明

循環(huán)隊(duì)列是一種先進(jìn)先出的，首尾相連的隊(duì)列。

大致的結(jié)構(gòu)如下圖：

用數(shù)組來(lái)抽象的表示一下的話，如下圖：

循環(huán)隊(duì)列有兩個(gè)指針指向數(shù)據(jù)，上圖中的start和end就是那兩個(gè)指針，它們指向相同的位置，表示的是空，即隊(duì)列是空的。

隨著數(shù)據(jù)的放入，隊(duì)列一般有下面的兩種形式：

需要注意第二種形式，從圖上看end在start的前面了，但是因?yàn)檠h(huán)關(guān)系，前后并不重要。

另外需要考慮的是隊(duì)列滿的情況：

但這種情況存在一個(gè)問題，即空隊(duì)列和滿隊(duì)列沒有辦法區(qū)分了，end和start都指向了相同的位置。

為了解決這個(gè)問題，一個(gè)方法是空出一個(gè)位置不放數(shù)據(jù)，當(dāng)end再加一個(gè)數(shù)據(jù)就等于start的時(shí)候就認(rèn)為隊(duì)列是滿的：

這時(shí)實(shí)際的數(shù)據(jù)長(zhǎng)度就會(huì)比分配的少1。

下面是隊(duì)列中空和滿的判斷：

1. 隊(duì)列為空時(shí)：end == start

2. 隊(duì)列為滿時(shí)：(end + 1) % size == start

這里的size是指分配的空間大小，而不是隊(duì)列長(zhǎng)度，隊(duì)列的實(shí)際長(zhǎng)度為(end - start + size) % size，最大長(zhǎng)度是size-1

這也是因?yàn)橐紤]循環(huán)的關(guān)系，所以要加上%size這個(gè)操作。

示例代碼

1. 首先定義結(jié)構(gòu)體：

//定義循環(huán)隊(duì)列
typedef struct _LoopQueue {
	int data[8];		//存放數(shù)據(jù)
	int start;		//頭指針
	int end;		//尾指針
} LoopQueue;

2. 定義各種算法：

#define TRUE	1
#define FALSE	0
#define SIZE	8
//初始化隊(duì)列
int init(LoopQueue *lq) {
	lq->start = 0;
	lq->end = 0;
	return TRUE;
}
//判斷隊(duì)列是否為空
int isEmpty(LoopQueue *lq) {
	if (lq->start == lq->end) {
		return TRUE;
	}
	return FALSE;
}
//判斷隊(duì)列是否為滿
int isFull(LoopQueue *lq) {
	if ((lq->end + 1) % SIZE == lq->start) {
		return TRUE;
	}
	return FALSE;
}
//獲取隊(duì)列的長(zhǎng)度
int getLength(LoopQueue *lq) {
	return (lq->end - lq->start + SIZE) % SIZE;
}
//插入數(shù)據(jù)
int pushQueue(LoopQueue *lq, int data) {
	if(isFull(lq)) {
		printf("Queue is full.\n");
		return FALSE;
	}
	lq->data[lq->end] = data;
	lq->end = (lq->end + 1) % SIZE;
	return TRUE;
}
//彈出數(shù)據(jù)
int popQueue(LoopQueue *lq, int *data) {
	if (isEmpty(lq)) {
		printf("Queue is empty.\n");
		return FALSE;
	}
	*data = lq->data[lq->start];
	lq->start = (lq->start + 1) % SIZE;
	return TRUE;
}
//顯示隊(duì)列中的數(shù)據(jù)
void printQueue(LoopQueue *lq) {
	int index;
	int count;
	count = getLength(lq);
	if (0 == count) {
		printf("No data.\n");
		return;
	}
	for (index = 0; index < count; index++) {
		printf("%d ", lq->data[index]);
	}
	printf("\n");
	return;
}

3. 測(cè)試：

int main()
{
	int index;
	int num;
	//隊(duì)列測(cè)試代碼
	LoopQueue *lq = (LoopQueue *)malloc(sizeof(LoopQueue));
	init(lq);
	printQueue(lq);
	for (index = 0; index < SIZE; index ++) {	//注意這里要放8個(gè)數(shù)據(jù)，但是實(shí)際上只能放7個(gè)，所以最后一個(gè)會(huì)報(bào)錯(cuò)
		pushQueue(lq, index);
	}
	printQueue(lq);
	for (index = 0; index < SIZE; index ++) {	//同上，會(huì)打印一個(gè)錯(cuò)誤
		if (popQueue(lq, &num)) {
			printf("%d\n", num);
		}
	}
	printQueue(lq);
	return 0;
}

4. 最后的結(jié)果：

以上就是C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)算法基礎(chǔ)之循環(huán)隊(duì)列的詳細(xì)內(nèi)容，更多關(guān)于C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)算法循環(huán)隊(duì)列的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: