目錄

前言

1.為啥要使用循環隊列

2.隊列的順序表示和實現

1.定義

2.初始化

3.銷毀

4.清空

5.空隊列

6.隊列長度

7.獲取隊頭

8.入隊

9.出隊

?10.遍歷隊列

11.完整代碼

---

前言

? ? 本篇博客介紹棧和隊列的表示和實現。

1.為啥要使用循環隊列

? ? 上篇文章中我們知道了順序隊列的用法，但是順序隊列有個缺點就是會“假溢出”，浪費大量的存儲空間，關于假溢出的問題，個人感覺數據結構里里面的這段解釋比較好，就直接截圖放下面了，大家自行閱讀吧。

圖1.順序隊列假溢出的問題

2.隊列的順序表示和實現

1.定義

#define MAX_QUEUE_SIZE 100 // 循環隊列的最大容量typedef int Status;
typedef int ElemType;typedef struct {ElemType *data; // 存儲數據的數組int front;      // 頭指針，指向隊首元素int rear;       // 尾指針，指向隊尾元素的下一個位置int maxSize;    // 循環隊列的最大容量
} CircularQueue;

2.初始化

? ? ? ? 隊列初始化的時候，隊頭和隊尾指針均為0

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

3.銷毀

? ? ? ? ? 釋放隊列存儲空間

// 銷毀循環隊列
void destroyCircularQueue(CircularQueue *queue) {free(queue->data);
}

4.清空

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

5.空隊列

? ? ? ? 隊頭和隊尾相同的時候為空隊列。

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

6.隊列長度

? ? ? ? 比較棧頂和棧頂的指針

// 獲取循環隊列長度
int circularQueueLength(CircularQueue *queue) {return (queue->rear - queue->front + queue->maxSize) % queue->maxSize;
}

7.獲取隊頭

? ? ? ? 獲取隊頭元素。

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

8.入隊

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

9.出隊

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

?10.遍歷隊列

// 遍歷循環隊列
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; // 循環隊列的最大容量initCircularQueue(&queue, maxSize); // 初始化循環隊列// 測試入隊for (int i = 1; i <= 5; ++i) {enCircularQueue(&queue, i * 10);}// 輸出隊列元素printf("隊列元素：");traverseCircularQueue(&queue);// 獲取隊首元素ElemType frontElement;if (getCircularQueueFront(&queue, &frontElement)) {printf("隊首元素：%d\n", frontElement);}// 測試出隊ElemType element;for (int i = 0; i < 3; ++i) {if (deCircularQueue(&queue, &element)) {printf("出隊元素：%d\n", element);}}// 輸出隊列元素printf("隊列元素：");traverseCircularQueue(&queue);// 判斷隊列是否為空if (isEmptyCircularQueue(&queue)) {printf("隊列為空\n");} else {printf("隊列不為空\n");}// 獲取隊列長度printf("隊列長度：%d\n", circularQueueLength(&queue));// 清空隊列clearCircularQueue(&queue);// 判斷隊列是否為空if (isEmptyCircularQueue(&queue)) {printf("清空隊列后，隊列為空\n");} else {printf("清空隊列后，隊列不為空\n");}// 銷毀隊列destroyCircularQueue(&queue);return 0;
}