文章目錄

• 隊(duì)列
• • 1.概念
  • 2. 生活中隊(duì)列應(yīng)用
  • 3. 隊(duì)列的實(shí)現(xiàn)
  • • 初始化隊(duì)列
    • 入隊(duì)列
    • 出隊(duì)列
    • 獲取隊(duì)頭元素
    • 獲取隊(duì)尾元素
    • 獲取隊(duì)列中元素個(gè)數(shù)
    • 判斷隊(duì)列是否為空
    • 銷(xiāo)毀隊(duì)列
  • 2. 循環(huán)隊(duì)列

創(chuàng)新互聯(lián)建站專(zhuān)注于成安網(wǎng)站建設(shè)服務(wù)及定制，我們擁有豐富的企業(yè)做網(wǎng)站經(jīng)驗(yàn)。 熱誠(chéng)為您提供成安營(yíng)銷(xiāo)型網(wǎng)站建設(shè)，成安網(wǎng)站制作、成安網(wǎng)頁(yè)設(shè)計(jì)、成安網(wǎng)站官網(wǎng)定制、重慶小程序開(kāi)發(fā)服務(wù)，打造成安網(wǎng)絡(luò)公司原創(chuàng)品牌,更為您提供成安網(wǎng)站排名全網(wǎng)營(yíng)銷(xiāo)落地服務(wù)。

---

隊(duì)列 1.概念

和棧相反，隊(duì)列(queue)是一種先進(jìn)先出的線(xiàn)性表，它只允許在一端進(jìn)行插入，而在另一端被刪除。這和生活中的排隊(duì)是類(lèi)似的，最先排隊(duì)的最先離開(kāi)。在隊(duì)列中運(yùn)行被插入的一端叫做隊(duì)尾，允許被刪除的一端叫做隊(duì)尾。

2. 生活中隊(duì)列應(yīng)用

比如我們?nèi)ャy行辦理業(yè)務(wù)的時(shí)候需要去抽號(hào)機(jī)器上取一個(gè)號(hào)碼，這起始就是隊(duì)列的應(yīng)用。每當(dāng)有一個(gè)人取號(hào)后機(jī)器就會(huì)把這個(gè)號(hào)碼入隊(duì)列進(jìn)行排隊(duì)。等窗口工作人員進(jìn)行叫號(hào)辦理業(yè)務(wù)。

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

隊(duì)列可以用數(shù)組或者鏈表實(shí)現(xiàn)，使用鏈表實(shí)現(xiàn)會(huì)更加合適一些，因?yàn)槿绻褂脭?shù)組實(shí)現(xiàn)在出隊(duì)的時(shí)候效率會(huì)比較低。

隊(duì)列的定義

因?yàn)槭擎湵韺?shí)現(xiàn)所以還要定義一個(gè)節(jié)點(diǎn)結(jié)構(gòu)體，隊(duì)列的結(jié)構(gòu)題包含兩個(gè)指針一個(gè)隊(duì)頭指針和一個(gè)隊(duì)尾指針

typedef int QDataType;

typedef struct QListNode {QDataType data;
	struct QListNode* next;//下一個(gè)節(jié)點(diǎn)
}QNode;

typedef struct Queue
{QNode* front;//隊(duì)頭
	QNode* rear;//隊(duì)尾
}Queue;

// 初始化隊(duì)列
void QueueInit(Queue* q);
// 動(dòng)態(tài)申請(qǐng)節(jié)點(diǎn)
QNode* BuyQNode(QDataType data);
// 隊(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
int QueueEmpty(Queue* q);
// 銷(xiāo)毀隊(duì)列
void QueueDestroy(Queue* q);

初始化隊(duì)列

初始化隊(duì)列比較簡(jiǎn)單，讓隊(duì)頭和隊(duì)尾指向NULL，因?yàn)榇藭r(shí)隊(duì)列里沒(méi)有任何元素。

// 初始化隊(duì)列
void QueueInit(Queue* q)
{assert(q);
	q->front = NULL;
	q->rear = NULL;
}

因?yàn)檫@是鏈表實(shí)現(xiàn)所以還要定義個(gè)動(dòng)態(tài)申請(qǐng)節(jié)點(diǎn)的函數(shù)

// 動(dòng)態(tài)申請(qǐng)節(jié)點(diǎn)
QNode* BuyQNode(QDataType data)
{QNode* node = (QNode*)(malloc(sizeof(QNode)));
	if (node == NULL)
	{printf("申請(qǐng)失敗\n");
		exit(-1);
	}
	node->data = data;
	node->next = NULL;
	return node;
}

入隊(duì)列

入隊(duì)列需要考慮兩種情況，第一種是隊(duì)列為空的情況，隊(duì)列為空要把隊(duì)頭和隊(duì)尾指針都指向第一個(gè)元素，其他情況只需要把節(jié)點(diǎn)插入到隊(duì)尾指針后面，再讓對(duì)隊(duì)尾指針往后走即可。

// 隊(duì)尾入隊(duì)列
void QueuePush(Queue* q, QDataType data)
{assert(q);
	QNode* node = BuyQNode(data);
	if (q->front == NULL)
	{q->front = node;
		q->rear = node;
	}
	else
	{q->rear->next = node;
		q->rear = q->rear->next;
	}
}

出隊(duì)列

出隊(duì)列要考慮到隊(duì)列是否為空，為空是不能進(jìn)行出隊(duì)列操作的。出隊(duì)列只需要讓隊(duì)頭指針往后走，再釋放隊(duì)頭節(jié)點(diǎn)。

// 隊(duì)頭出隊(duì)列
void QueuePop(Queue* q)
{assert(q);
	assert(!QueueEmpty(q));

	QNode* cur = q->front;
	q->front = q->front->next;
	free(cur);
}

獲取隊(duì)頭元素

// 獲取隊(duì)列頭部元素
QDataType QueueFront(Queue* q)
{assert(q);
	assert(!QueueEmpty(q));

	return q->front->data;
}

獲取隊(duì)尾元素

// 獲取隊(duì)列隊(duì)尾元素
QDataType QueueBack(Queue* q)
{assert(q);
	assert(!QueueEmpty(q));

	return q->rear->data;
}

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

和鏈表求長(zhǎng)度是一樣的

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

	QNode* cur = q->front;
	int count = 0;
	while (cur != NULL)
	{count++;
		cur = cur->next;
	}
	
	return count;
}

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

當(dāng)隊(duì)頭指向NULL時(shí)說(shuō)明隊(duì)列為空

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

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

銷(xiāo)毀隊(duì)列遍歷一邊隊(duì)列，把每個(gè)節(jié)點(diǎn)給釋放掉。

// 銷(xiāo)毀隊(duì)列
void QueueDestroy(Queue* q)
{assert(q);
	QNode* cur = q->front;
	while (cur != NULL)
	{q->front = cur->next;
		free(cur);
		cur = q->front;
	}
	q->front = NULL;
	q->rear = NULL;
}

2. 循環(huán)隊(duì)列

循環(huán)隊(duì)列也是一種隊(duì)列，再隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)中，除了用一組連續(xù)的存儲(chǔ)單元依次存放隊(duì)頭到隊(duì)尾元素外，還需要兩指針 front 和 rear 分別指向隊(duì)頭和隊(duì)尾。

我們約定，初始化空隊(duì)列時(shí)，讓 front 和 rear 都賦為0，也就是指向數(shù)組的0下標(biāo)。每當(dāng)插入元素時(shí)尾指針加1，每當(dāng)刪除元素時(shí)頭指針加1。

因?yàn)檫@時(shí)一個(gè)循環(huán)隊(duì)列，當(dāng) f r o n t = = r e a r front == rear front==rear時(shí)，無(wú)法判斷循環(huán)是滿(mǎn)還是空。所以可以有兩種選擇，一種是做一個(gè)標(biāo)記判斷是否為滿(mǎn)了，而是創(chuàng)建隊(duì)列的時(shí)候多開(kāi)一個(gè)空間，浪費(fèi)掉這個(gè)空間方便判斷。

我們采用第二種方式，約定 f r o n = = r e a r fron == rear fron==rear表示隊(duì)列為空， r e a r + 1 = = f r o n rear+1 == fron rear+1==fron表示隊(duì)列滿(mǎn)了。

還有一個(gè)問(wèn)題就是這是一個(gè)循環(huán)隊(duì)列，當(dāng)尾指針走到最后一個(gè)位置時(shí)如何走到下標(biāo)為0的位置，我們可以巧妙的用一個(gè)公式，假設(shè)隊(duì)列大小為 size。

頭指針向后走： ( f r o n + 1 ) % s i z e (fron+1)\%size (fron+1)%size

尾指針向后走： ( r e a r + 1 ) % s i z e (rear + 1)\%size (rear+1)%size

代碼實(shí)現(xiàn)

typedef struct {int* arr;
    int front;
    int rear;
    int size;//容量
} MyCircularQueue;

bool myCircularQueueIsEmpty(MyCircularQueue* obj);
bool myCircularQueueIsFull(MyCircularQueue* obj);
MyCircularQueue* QUeue(int k) {MyCircularQueue* obj = (MyCircularQueue*)(malloc(sizeof(MyCircularQueue)));

    //創(chuàng)建容量為k+1大小的隊(duì)列，浪費(fèi)1個(gè)空間
    obj->arr = (int*)(malloc(sizeof(int)*(k+1)));
    obj->front = 0;
    obj->rear = 0;
    obj->size = k+1;
    return obj;
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if (myCircularQueueIsFull(obj) == true)
    {return false;//滿(mǎn)了
    }
    else
    {obj->arr[obj->rear] = value;
        obj->rear = (obj->rear+1) % (obj->size);
        return true;
    }

    
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj))
    {return false;
    }
    else
    {obj->front = (obj->front+1) % (obj->size);
        return true;
    }
}

int myCircularQueueFront(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj) == true)
    {return -1;
    }
    return obj->arr[obj->front];
}

int myCircularQueueRear(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj))
    {return -1;
    }
    return (obj->rear == 0) ? (obj->arr[obj->size-1]) : (obj->arr[obj->rear-1]);
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {//約定 頭位相遇就是空，尾+1是頭就是滿(mǎn)
    if (obj->front == obj->rear)
    {return true;
    }
    return false;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {//約定 頭位相遇就是空，尾+1是頭就是滿(mǎn)
    if (((obj->rear)+1)%obj->size == (obj->front))
    {return true;
    }
    return false;
}

void myCircularQueueFree(MyCircularQueue* obj) {free(obj->arr);
    obj->front = NULL;
    obj->rear = NULL;
    free(obj);
}

---

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

網(wǎng)站名稱(chēng)：數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版——隊(duì)列+循環(huán)隊(duì)列實(shí)現(xiàn)-創(chuàng)新互聯(lián)
標(biāo)題URL：http://vcdvsql.cn/article28/dsdhcp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供軟件開(kāi)發(fā)、App開(kāi)發(fā)、云服務(wù)器、微信小程序、品牌網(wǎng)站設(shè)計(jì)、ChatGPT

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶(hù)投稿、用戶(hù)轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話(huà)：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)