據(jù)結(jié)構(gòu)】C語言實現(xiàn)循環(huán)隊列)
?前言隊列是數(shù)據(jù)結(jié)構(gòu)中經(jīng)典的先進(jìn)先出FIFO線性結(jié)構(gòu)普通順序隊列會出現(xiàn)「假溢出」問題而循環(huán)隊列完美解決了數(shù)組隊列的空間浪費問題。本文手把手帶你用C語言實現(xiàn)靜態(tài)數(shù)組版循環(huán)隊列包含初始化、入隊、出隊、判空、判滿、遍歷等全套操作代碼帶詳細(xì)注釋零基礎(chǔ)輕松看懂[TOC](文章目錄)一、為什么需要循環(huán)隊列1. 普通順序隊列的缺陷普通數(shù)組順序隊列進(jìn)行多次入隊、出隊后front指針不斷后移數(shù)組前面的空間無法重復(fù)使用隊列看似滿了實際存在大量空閑空間這種現(xiàn)象叫做假溢出。2. 循環(huán)隊列的優(yōu)化思路將數(shù)組首尾相連形成環(huán)狀結(jié)構(gòu)通過取模運算 %讓指針移動到數(shù)組末尾后自動回到頭部徹底解決假溢出問題最大化利用數(shù)組空間。二、循環(huán)隊列核心原理1. 結(jié)構(gòu)體設(shè)計data[]存儲隊列元素的數(shù)組front隊首指針指向隊首元素rear隊尾指針指向下一個入隊位置2. 核心判定公式經(jīng)典留白法本文采用業(yè)界通用的犧牲一個存儲位區(qū)分空/滿的方式隊列為空front rear隊列已滿(rear 1) % MAX_SIZE front隊列長度(rear - front MAX_SIZE) % MAX_SIZE三、完整可運行源碼純C語言實現(xiàn)無多余依賴支持入隊、出隊、取隊首、求長度、遍歷打印直接復(fù)制可編譯運行。#include stdio.h #include stdlib.h #define MAX_SIZE 100 // 循環(huán)隊列結(jié)構(gòu)體定義 typedef struct { int data[MAX_SIZE]; // 存儲隊列數(shù)據(jù) int front; // 隊首指針 int rear; // 隊尾指針 } Queue; /** * brief 初始化循環(huán)隊列 */ void initQueue(Queue *q) { q-front 0; q-rear 0; } /** * brief 判斷隊列是否為空 * return 1為空 0不為空 */ int isEmpty(Queue *q) { return q-front q-rear; } /** * brief 判斷隊列是否已滿 * return 1為滿 0未滿 */ int isFull(Queue *q) { return (q-rear 1) % MAX_SIZE q-front; } /** * brief 入隊操作 * param value 入隊元素 * return 成功返回1失敗返回0 */ int enqueue(Queue *q, int value) { if (isFull(q)) { printf(隊列已滿無法入隊\n); return 0; } q-data[q-rear] value; q-rear (q-rear 1) % MAX_SIZE; return 1; } /** * brief 出隊操作 * param value 保存出隊元素 * return 成功返回1失敗返回0 */ int dequeue(Queue *q, int *value) { if (isEmpty(q)) { printf(隊列已空無法出隊\n); return 0; } *value q-data[q-front]; q-front (q-front 1) % MAX_SIZE; return 1; } /** * brief 獲取隊首元素不刪除 */ int getFront(Queue *q, int *value) { if (isEmpty(q)) { printf(隊列已空\n); return 0; } *value q-data[q-front]; return 1; } /** * brief 獲取當(dāng)前隊列有效元素個數(shù) */ int getSize(Queue *q) { return (q-rear - q-front MAX_SIZE) % MAX_SIZE; } /** * brief 打印隊列所有元素 */ void printQueue(Queue *q) { if (isEmpty(q)) { printf(隊列已空\n); return; } printf(隊列元素); int i q-front; while (i ! q-rear) { printf(%d , q-data[i]); i (i 1) % MAX_SIZE; } printf(\n); } // 主函數(shù)測試 int main() { Queue q; initQueue(q); // 元素入隊 enqueue(q, 10); enqueue(q, 20); enqueue(q, 30); printQueue(q); // 元素出隊 int value; if (dequeue(q, value)) { printf(出隊元素%d\n, value); } printQueue(q); // 獲取隊首元素 if (getFront(q, value)) { printf(隊首元素%d\n, value); } // 獲取隊列長度 printf(隊列長度%d\n, getSize(q)); return 0; }四、函數(shù)功能逐行詳解1. 隊列初始化 initQueue將 front 和 rear 指針置0表示隊列為空完成隊列初始化所有數(shù)據(jù)位初始為默認(rèn)值。2. 判空 判滿循環(huán)隊列最核心難點通過預(yù)留一個空位區(qū)分空和滿避免歧義。如果不預(yù)留空位frontrear 無法判斷是空隊列還是滿隊列。3. 入隊 enqueue先判斷隊列是否已滿未滿則將元素存入 rear 指針位置再通過取模運算更新 rear 指針實現(xiàn)環(huán)形移動。4. 出隊 dequeue判斷隊列非空取出 front 指針指向的元素向后移動 front 指針完成出隊遵循先進(jìn)先出規(guī)則。5. 長度計算 getSize加入 MAX_SIZE 再取模是為了避免 rear front 時出現(xiàn)負(fù)數(shù)保證長度計算結(jié)果永遠(yuǎn)為正數(shù)。6. 隊列遍歷 printQueue從 front 開始遍歷直到等于 rear 結(jié)束精準(zhǔn)打印所有有效元素不打印預(yù)留空位。五、程序運行結(jié)果編譯運行代碼輸出結(jié)果如下隊列元素10 20 30 出隊元素10 隊列元素20 30 隊首元素20 隊列長度2結(jié)果解析依次入隊 10、20、30隊列正常存儲數(shù)據(jù)出隊隊首 10符合先進(jìn)先出特性剩余隊首為20有效元素個數(shù)為2六、循環(huán)隊列優(yōu)缺點?優(yōu)點解決普通順序隊列假溢出問題空間利用率極高數(shù)組實現(xiàn)讀寫速度快時間復(fù)雜度 O(1)結(jié)構(gòu)簡單、穩(wěn)定性強常用于操作系統(tǒng)任務(wù)隊列、緩沖區(qū)?缺點靜態(tài)數(shù)組實現(xiàn)隊列容量固定無法動態(tài)擴(kuò)容需要犧牲一個存儲空間用來區(qū)分空滿狀態(tài)七、拓展優(yōu)化方向動態(tài)循環(huán)隊列使用動態(tài)內(nèi)存 malloc 實現(xiàn)可擴(kuò)容隊列計數(shù)器法判空滿新增size變量無需犧牲存儲空間鏈?zhǔn)疥犃薪鉀Q固定容量問題支持無限擴(kuò)容八、總結(jié)循環(huán)隊列是數(shù)據(jù)結(jié)構(gòu)面試、期末考試、工程開發(fā)中的高頻考點。核心精髓就是利用取模運算實現(xiàn)指針環(huán)形移動解決順序隊列的空間浪費問題。本文代碼完整、注釋詳盡、邏輯清晰非常適合新手學(xué)習(xí)、課程作業(yè)與面試復(fù)習(xí) 【數(shù)據(jù)結(jié)構(gòu)】C語言實現(xiàn)循環(huán)隊列
?前言隊列是數(shù)據(jù)結(jié)構(gòu)中經(jīng)典的先進(jìn)先出FIFO線性結(jié)構(gòu)普通順序隊列會出現(xiàn)「假溢出」問題而循環(huán)隊列完美解決了數(shù)組隊列的空間浪費問題。本文手把手帶你用C語言實現(xiàn)靜態(tài)數(shù)組版循環(huán)隊列包含初始化、入隊、出隊、判空、判滿、遍歷等全套操作代碼帶詳細(xì)注釋零基礎(chǔ)輕松看懂[TOC](文章目錄)一、為什么需要循環(huán)隊列1. 普通順序隊列的缺陷普通數(shù)組順序隊列進(jìn)行多次入隊、出隊后front指針不斷后移數(shù)組前面的空間無法重復(fù)使用隊列看似滿了實際存在大量空閑空間這種現(xiàn)象叫做假溢出。2. 循環(huán)隊列的優(yōu)化思路將數(shù)組首尾相連形成環(huán)狀結(jié)構(gòu)通過取模運算 %讓指針移動到數(shù)組末尾后自動回到頭部徹底解決假溢出問題最大化利用數(shù)組空間。二、循環(huán)隊列核心原理1. 結(jié)構(gòu)體設(shè)計data[]存儲隊列元素的數(shù)組front隊首指針指向隊首元素rear隊尾指針指向下一個入隊位置2. 核心判定公式經(jīng)典留白法本文采用業(yè)界通用的犧牲一個存儲位區(qū)分空/滿的方式隊列為空front rear隊列已滿(rear 1) % MAX_SIZE front隊列長度(rear - front MAX_SIZE) % MAX_SIZE三、完整可運行源碼純C語言實現(xiàn)無多余依賴支持入隊、出隊、取隊首、求長度、遍歷打印直接復(fù)制可編譯運行。#include stdio.h #include stdlib.h #define MAX_SIZE 100 // 循環(huán)隊列結(jié)構(gòu)體定義 typedef struct { int data[MAX_SIZE]; // 存儲隊列數(shù)據(jù) int front; // 隊首指針 int rear; // 隊尾指針 } Queue; /** * brief 初始化循環(huán)隊列 */ void initQueue(Queue *q) { q-front 0; q-rear 0; } /** * brief 判斷隊列是否為空 * return 1為空 0不為空 */ int isEmpty(Queue *q) { return q-front q-rear; } /** * brief 判斷隊列是否已滿 * return 1為滿 0未滿 */ int isFull(Queue *q) { return (q-rear 1) % MAX_SIZE q-front; } /** * brief 入隊操作 * param value 入隊元素 * return 成功返回1失敗返回0 */ int enqueue(Queue *q, int value) { if (isFull(q)) { printf(隊列已滿無法入隊\n); return 0; } q-data[q-rear] value; q-rear (q-rear 1) % MAX_SIZE; return 1; } /** * brief 出隊操作 * param value 保存出隊元素 * return 成功返回1失敗返回0 */ int dequeue(Queue *q, int *value) { if (isEmpty(q)) { printf(隊列已空無法出隊\n); return 0; } *value q-data[q-front]; q-front (q-front 1) % MAX_SIZE; return 1; } /** * brief 獲取隊首元素不刪除 */ int getFront(Queue *q, int *value) { if (isEmpty(q)) { printf(隊列已空\n); return 0; } *value q-data[q-front]; return 1; } /** * brief 獲取當(dāng)前隊列有效元素個數(shù) */ int getSize(Queue *q) { return (q-rear - q-front MAX_SIZE) % MAX_SIZE; } /** * brief 打印隊列所有元素 */ void printQueue(Queue *q) { if (isEmpty(q)) { printf(隊列已空\n); return; } printf(隊列元素); int i q-front; while (i ! q-rear) { printf(%d , q-data[i]); i (i 1) % MAX_SIZE; } printf(\n); } // 主函數(shù)測試 int main() { Queue q; initQueue(q); // 元素入隊 enqueue(q, 10); enqueue(q, 20); enqueue(q, 30); printQueue(q); // 元素出隊 int value; if (dequeue(q, value)) { printf(出隊元素%d\n, value); } printQueue(q); // 獲取隊首元素 if (getFront(q, value)) { printf(隊首元素%d\n, value); } // 獲取隊列長度 printf(隊列長度%d\n, getSize(q)); return 0; }四、函數(shù)功能逐行詳解1. 隊列初始化 initQueue將 front 和 rear 指針置0表示隊列為空完成隊列初始化所有數(shù)據(jù)位初始為默認(rèn)值。2. 判空 判滿循環(huán)隊列最核心難點通過預(yù)留一個空位區(qū)分空和滿避免歧義。如果不預(yù)留空位frontrear 無法判斷是空隊列還是滿隊列。3. 入隊 enqueue先判斷隊列是否已滿未滿則將元素存入 rear 指針位置再通過取模運算更新 rear 指針實現(xiàn)環(huán)形移動。4. 出隊 dequeue判斷隊列非空取出 front 指針指向的元素向后移動 front 指針完成出隊遵循先進(jìn)先出規(guī)則。5. 長度計算 getSize加入 MAX_SIZE 再取模是為了避免 rear front 時出現(xiàn)負(fù)數(shù)保證長度計算結(jié)果永遠(yuǎn)為正數(shù)。6. 隊列遍歷 printQueue從 front 開始遍歷直到等于 rear 結(jié)束精準(zhǔn)打印所有有效元素不打印預(yù)留空位。五、程序運行結(jié)果編譯運行代碼輸出結(jié)果如下隊列元素10 20 30 出隊元素10 隊列元素20 30 隊首元素20 隊列長度2結(jié)果解析依次入隊 10、20、30隊列正常存儲數(shù)據(jù)出隊隊首 10符合先進(jìn)先出特性剩余隊首為20有效元素個數(shù)為2六、循環(huán)隊列優(yōu)缺點?優(yōu)點解決普通順序隊列假溢出問題空間利用率極高數(shù)組實現(xiàn)讀寫速度快時間復(fù)雜度 O(1)結(jié)構(gòu)簡單、穩(wěn)定性強常用于操作系統(tǒng)任務(wù)隊列、緩沖區(qū)?缺點靜態(tài)數(shù)組實現(xiàn)隊列容量固定無法動態(tài)擴(kuò)容需要犧牲一個存儲空間用來區(qū)分空滿狀態(tài)七、拓展優(yōu)化方向動態(tài)循環(huán)隊列使用動態(tài)內(nèi)存 malloc 實現(xiàn)可擴(kuò)容隊列計數(shù)器法判空滿新增size變量無需犧牲存儲空間鏈?zhǔn)疥犃薪鉀Q固定容量問題支持無限擴(kuò)容八、總結(jié)循環(huán)隊列是數(shù)據(jù)結(jié)構(gòu)面試、期末考試、工程開發(fā)中的高頻考點。核心精髓就是利用取模運算實現(xiàn)指針環(huán)形移動解決順序隊列的空間浪費問題。本文代碼完整、注釋詳盡、邏輯清晰非常適合新手學(xué)習(xí)、課程作業(yè)與面試復(fù)習(xí)