目錄

前言

1.為啥要使用循環(huán)隊(duì)列

2.隊(duì)列的順序表示和實(shí)現(xiàn)

1.定義

2.初始化

3.銷(xiāo)毀

4.清空

5.空隊(duì)列

6.隊(duì)列長(zhǎng)度

7.獲取隊(duì)頭

8.入隊(duì)

9.出隊(duì)

?10.遍歷隊(duì)列

11.完整代碼

---

前言

? ? 本篇博客介紹棧和隊(duì)列的表示和實(shí)現(xiàn)。

1.為啥要使用循環(huán)隊(duì)列

? ? 上篇文章中我們知道了順序隊(duì)列的用法，但是順序隊(duì)列有個(gè)缺點(diǎn)就是會(huì)“假溢出”，浪費(fèi)大量的存儲(chǔ)空間，關(guān)于假溢出的問(wèn)題，個(gè)人感覺(jué)數(shù)據(jù)結(jié)構(gòu)里里面的這段解釋比較好，就直接截圖放下面了，大家自行閱讀吧。

圖1.順序隊(duì)列假溢出的問(wèn)題

2.隊(duì)列的順序表示和實(shí)現(xiàn)

1.定義

#define MAX_QUEUE_SIZE 100 // 循環(huán)隊(duì)列的最大容量typedef int Status;
typedef int ElemType;typedef struct {ElemType *data; // 存儲(chǔ)數(shù)據(jù)的數(shù)組int front;      // 頭指針，指向隊(duì)首元素int rear;       // 尾指針，指向隊(duì)尾元素的下一個(gè)位置int maxSize;    // 循環(huán)隊(duì)列的最大容量
} CircularQueue;

2.初始化

? ? ? ? 隊(duì)列初始化的時(shí)候，隊(duì)頭和隊(duì)尾指針均為0

// 初始化循環(huán)隊(duì)列
Status initCircularQueue(CircularQueue *queue, int maxSize) {queue->data = (ElemType *)malloc(sizeof(ElemType) * maxSize);if (!queue->data) {return 0; // 內(nèi)存分配失敗}queue->front = queue->rear = 0;queue->maxSize = maxSize;return 1; // 初始化成功
}

3.銷(xiāo)毀

? ? ? ? ? 釋放隊(duì)列存儲(chǔ)空間

// 銷(xiāo)毀循環(huán)隊(duì)列
void destroyCircularQueue(CircularQueue *queue) {free(queue->data);
}

4.清空

// 清空循環(huán)隊(duì)列
void clearCircularQueue(CircularQueue *queue) {queue->front = queue->rear = 0;
}

5.空隊(duì)列

? ? ? ? 隊(duì)頭和隊(duì)尾相同的時(shí)候?yàn)榭贞?duì)列。

// 判斷循環(huán)隊(duì)列是否為空
Status isEmptyCircularQueue(CircularQueue *queue) {return queue->front == queue->rear;
}

6.隊(duì)列長(zhǎng)度

? ? ? ? 比較棧頂和棧頂?shù)闹羔?/p>

// 獲取循環(huán)隊(duì)列長(zhǎng)度
int circularQueueLength(CircularQueue *queue) {return (queue->rear - queue->front + queue->maxSize) % queue->maxSize;
}

7.獲取隊(duì)頭

? ? ? ? 獲取隊(duì)頭元素。

// 獲取循環(huán)隊(duì)列的隊(duì)首元素
Status getCircularQueueFront(CircularQueue *queue, ElemType *element) {if (isEmptyCircularQueue(queue)) {return 0; // 隊(duì)列為空}*element = queue->data[queue->front];return 1; // 成功獲取隊(duì)首元素
}

8.入隊(duì)

// 入隊(duì)
Status enCircularQueue(CircularQueue *queue, ElemType element) {if ((queue->rear + 1) % queue->maxSize == queue->front) {return 0; // 隊(duì)列已滿(mǎn)}queue->data[queue->rear] = element;queue->rear = (queue->rear + 1) % queue->maxSize;return 1; // 入隊(duì)成功
}

9.出隊(duì)

// 出隊(duì)
Status deCircularQueue(CircularQueue *queue, ElemType *element) {if (isEmptyCircularQueue(queue)) {return 0; // 隊(duì)列為空}*element = queue->data[queue->front];queue->front = (queue->front + 1) % queue->maxSize;return 1; // 出隊(duì)成功
}

?10.遍歷隊(duì)列

// 遍歷循環(huán)隊(duì)列
void traverseCircularQueue(CircularQueue *queue) {for (int i = queue->front; i != queue->rear; i = (i + 1) % queue->maxSize) {printf("%d ", queue->data[i]);}printf("\n");
}

11.完整代碼

int main(int argc, const char *argv[]) {CircularQueue queue;int maxSize = 10; // 循環(huán)隊(duì)列的最大容量initCircularQueue(&queue, maxSize); // 初始化循環(huán)隊(duì)列// 測(cè)試入隊(duì)for (int i = 1; i <= 5; ++i) {enCircularQueue(&queue, i * 10);}// 輸出隊(duì)列元素printf("隊(duì)列元素：");traverseCircularQueue(&queue);// 獲取隊(duì)首元素ElemType frontElement;if (getCircularQueueFront(&queue, &frontElement)) {printf("隊(duì)首元素：%d\n", frontElement);}// 測(cè)試出隊(duì)ElemType element;for (int i = 0; i < 3; ++i) {if (deCircularQueue(&queue, &element)) {printf("出隊(duì)元素：%d\n", element);}}// 輸出隊(duì)列元素printf("隊(duì)列元素：");traverseCircularQueue(&queue);// 判斷隊(duì)列是否為空if (isEmptyCircularQueue(&queue)) {printf("隊(duì)列為空\(chéng)n");} else {printf("隊(duì)列不為空\(chéng)n");}// 獲取隊(duì)列長(zhǎng)度printf("隊(duì)列長(zhǎng)度：%d\n", circularQueueLength(&queue));// 清空隊(duì)列clearCircularQueue(&queue);// 判斷隊(duì)列是否為空if (isEmptyCircularQueue(&queue)) {printf("清空隊(duì)列后，隊(duì)列為空\(chéng)n");} else {printf("清空隊(duì)列后，隊(duì)列不為空\(chéng)n");}// 銷(xiāo)毀隊(duì)列destroyCircularQueue(&queue);return 0;
}