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