數(shù)據(jù)結(jié)構(gòu)C語言版——隊列+循環(huán)隊列實(shí)現(xiàn)-創(chuàng)新互聯(lián)

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

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

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

在這里插入圖片描述

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

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

在這里插入圖片描述

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

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

隊列的定義

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

typedef int QDataType;

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

typedef struct Queue
{QNode* front;//隊頭
	QNode* rear;//隊尾
}Queue;

// 初始化隊列
void QueueInit(Queue* q);
// 動態(tài)申請節(jié)點(diǎn)
QNode* BuyQNode(QDataType data);
// 隊尾入隊列
void QueuePush(Queue* q, QDataType data);
// 隊頭出隊列
void QueuePop(Queue* q);
// 獲取隊列頭部元素
QDataType QueueFront(Queue* q);
// 獲取隊列隊尾元素
QDataType QueueBack(Queue* q);
// 獲取隊列中有效元素個數(shù)
int QueueSize(Queue* q);
// 檢測隊列是否為空，如果為空返回非零結(jié)果，如果非空返回0
int QueueEmpty(Queue* q);
// 銷毀隊列
void QueueDestroy(Queue* q);
初始化隊列

初始化隊列比較簡單，讓隊頭和隊尾指向NULL，因?yàn)榇藭r隊列里沒有任何元素。

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

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

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

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

// 隊尾入隊列
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;
	}
}
出隊列

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

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

	QNode* cur = q->front;
	q->front = q->front->next;
	free(cur);
}
獲取隊頭元素
// 獲取隊列頭部元素
QDataType QueueFront(Queue* q)
{assert(q);
	assert(!QueueEmpty(q));

	return q->front->data;
}
獲取隊尾元素
// 獲取隊列隊尾元素
QDataType QueueBack(Queue* q)
{assert(q);
	assert(!QueueEmpty(q));

	return q->rear->data;
}
獲取隊列中元素個數(shù)

和鏈表求長度是一樣的

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

	QNode* cur = q->front;
	int count = 0;
	while (cur != NULL)
	{count++;
		cur = cur->next;
	}
	
	return count;
}
判斷隊列是否為空

當(dāng)隊頭指向NULL時說明隊列為空

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

銷毀隊列遍歷一邊隊列，把每個節(jié)點(diǎn)給釋放掉。

// 銷毀隊列
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)隊列

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

在這里插入圖片描述

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

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

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

還有一個問題就是這是一個循環(huán)隊列，當(dāng)尾指針走到最后一個位置時如何走到下標(biāo)為0的位置，我們可以巧妙的用一個公式，假設(shè)隊列大小為 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大小的隊列，浪費(fèi)1個空間
    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;//滿了
    }
    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是頭就是滿
    if (obj->front == obj->rear)
    {return true;
    }
    return false;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {//約定 頭位相遇就是空，尾+1是頭就是滿
    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級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

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

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

廣告

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

搜索引擎優(yōu)化