前言承接上一篇順序棧的實現(xiàn)本篇完成「先進先出」的鏈式隊列手寫。 全文圍繞三個核心問題展開為什么隊列優(yōu)先選單鏈表實現(xiàn)、frontrear雙指針的設計意義、size成員的價值同時附上完整可運行代碼與真實實現(xiàn)過程中的踩坑復盤。本文全部代碼已托管至 Gitee代碼采用頭文件與實現(xiàn)文件分離的模塊化寫法測試用例覆蓋空隊列、單節(jié)點、多次入出隊等全部邊界場景可直接拉取本地編譯調試。Gitee 倉庫地址數(shù)據(jù)結構/8.17 隊列練習Queue · Luminous/Code_2026 - 碼云 - 開源中國一、隊列基礎先進先出的線性表隊列是操作受限的線性表僅允許在隊尾rear插入、隊頭front刪除遵循FIFOFirst In First Out先進先出規(guī)則。典型應用場景二叉樹層序遍歷、圖的廣度優(yōu)先搜索BFS操作系統(tǒng)任務調度、請求排隊生產者消費者模型、消息緩沖區(qū)二、實現(xiàn)選型為什么隊列更適合用單鏈表實現(xiàn)隊列有「順序表」和「鏈表」兩條路線選擇單鏈表并非習慣而是由隊列的操作特性決定的。2.1 順序表實現(xiàn)隊列的天然缺陷如果用數(shù)組實現(xiàn)隊列會直接撞上「頭刪低效」的問題普通數(shù)組隊頭刪除需要整體搬移后續(xù)元素時間復雜度O(N)效率極低循環(huán)隊列通過雙下標規(guī)避搬移但又引入新問題——容量固定無法動態(tài)擴容、「隊空/隊滿」邊界判斷繁瑣、存在空間浪費本質上順序表是在彌補「頭刪」的天生短板需要額外處理大量環(huán)形邏輯。2.2 單鏈表的天然適配性單鏈表的特性剛好匹配隊列的操作模式隊頭刪除 鏈表頭刪天然O(1)隊尾插入 鏈表尾插只要增加一個尾指針rear也能做到O(1)動態(tài)申請節(jié)點無固定容量上限元素數(shù)量不確定的場景更友好2.3 為什么不用雙向鏈表雙向鏈表雖然自帶尾指針但每個節(jié)點多一個prev指針會額外占用內存。隊列僅涉及頭刪、尾插完全不需要向前遍歷雙向鏈表屬于冗余設計。所以單鏈表 尾指針是實現(xiàn)隊列性價比最高的方案。三、鏈式隊列的結構設計采用「節(jié)點結構體 隊列管理結構體」的分層設計職責分離更清晰。3.1 節(jié)點結構體typedef struct QueueNode { QDataType data; // 存儲數(shù)據(jù) struct QueueNode* next; // 指向后繼節(jié)點 } QueueNode;與普通單鏈表節(jié)點完全一致負責存儲數(shù)據(jù)與維系鏈表關系。3.2 隊列管理結構體typedef struct Queue { QueueNode* front; // 隊頭指針指向第一個節(jié)點 QueueNode* rear; // 隊尾指針指向最后一個節(jié)點 int size; // 記錄有效元素個數(shù) } Queue;三個成員共同描述隊列的完整狀態(tài)front服務隊頭出隊、取隊頭元素rear服務隊尾入隊、取隊尾元素將尾插從 O(N) 優(yōu)化到 O(1)size記錄元素總數(shù)是性價比極高的可選優(yōu)化四、深度解析size 成員的設計價值size不是鏈式隊列的必需成員但屬于「極小成本換極大收益」的經(jīng)典設計核心價值有三點長度查詢從 O(N) 降為 O(1)無size時求隊列長度必須從頭遍歷鏈表加入size后入隊1、出隊-1查詢直接返回數(shù)值頻繁查詢長度的場景性能提升顯著。輔助校驗隊列狀態(tài)size是獨立于指針的第二維度狀態(tài)。正常情況下size 0必然對應front NULL rear NULL。調試時如果兩者不一致可以快速定位出入隊/出隊/銷毀操作的狀態(tài)維護錯誤?？臻g成本極低僅占用一個int的內存通常4字節(jié)換來常數(shù)級的查詢效率與更清晰的代碼語義。注意size并不天然比指針判空更安全。如果代碼本身維護錯誤size同樣會失真。核心是始終維護隊列的不變量空隊列時front NULL rear NULL size 0。五、完整代碼實現(xiàn)采用模塊化拆分Queue.h聲明接口Queue.c實現(xiàn)邏輯test.c測試驗證。5.1 Queue.h 頭文件#pragma once #includestdio.h #includestdlib.h #includeassert.h typedef int QDataType; // 隊列節(jié)點 typedef struct QueueNode { QDataType data; struct QueueNode* next; } QueueNode; // 隊列管理結構體 typedef struct Queue { QueueNode* front; QueueNode* rear; int size; } Queue; void QueueInit(Queue* q); // 初始化 void QueuePush(Queue* q, QDataType data); // 隊尾入隊 void QueuePop(Queue* q); // 隊頭出隊 QDataType QueueFront(Queue* q); // 獲取隊頭元素 QDataType QueueBack(Queue* q); // 獲取隊尾元素 int QueueSize(Queue* q); // 獲取元素個數(shù) int QueueEmpty(Queue* q); // 判空 void QueueDestroy(Queue* q); // 銷毀隊列5.2 Queue.c 實現(xiàn)文件#includeQueue.h // 初始化隊列 void QueueInit(Queue* q) { assert(q); q-front NULL; q-rear NULL; q-size 0; } // 隊尾入隊列 void QueuePush(Queue* q, QDataType data) { assert(q); QueueNode* Newnode (QueueNode*)malloc(sizeof(QueueNode)); if (Newnode NULL) { printf(malloc fail\n); return; } // 先初始化節(jié)點再接入鏈表 Newnode-next NULL; Newnode-data data; if (q-front NULL) { // 空隊列首次入隊頭尾同時指向新節(jié)點 q-front Newnode; q-rear Newnode; } else { // 非空隊列尾插后更新尾指針 q-rear-next Newnode; q-rear Newnode; } q-size; } // 隊頭出隊列 void QueuePop(Queue* q) { assert(q q-front); if (q-front ! q-rear) { // 多個節(jié)點頭指針后移釋放舊頭 QueueNode* node q-front; q-front q-front-next; free(node); } else { // 僅剩最后一個節(jié)點釋放后雙指針同時置空 free(q-front); q-front NULL; q-rear NULL; } q-size--; } // 獲取隊頭元素 QDataType QueueFront(Queue* q) { assert(q q-front); return q-front-data; } // 獲取隊尾元素 QDataType QueueBack(Queue* q) { assert(q q-rear); return q-rear-data; } // 獲取有效元素個數(shù) int QueueSize(Queue* q) { assert(q); return q-size; } // 判空空返回1非空返回0 int QueueEmpty(Queue* q) { assert(q); return q-size 0 ? 1 : 0; } // 銷毀隊列 void QueueDestroy(Queue* q) { assert(q); while (q-front) { QueueNode* node q-front; q-front q-front-next; free(node); } // 釋放完節(jié)點重置所有狀態(tài) q-rear NULL; q-size 0; }5.3 兩個核心邊界處理鏈式隊列的邏輯難點不在常規(guī)操作而在兩個邊界狀態(tài)首次入隊空隊列插入第一個節(jié)點時該節(jié)點既是隊頭也是隊尾必須同時給front和rear賦值。刪除最后一個節(jié)點當front rear時釋放節(jié)點后必須將雙指針同時置空否則rear會變成野指針。六、實現(xiàn)踩坑復盤以下是手寫過程中真實遇到的典型問題大多不屬于「算法不會」而是指針狀態(tài)維護不完整。序號問題描述后果修正方案1初始化重復賦值front漏寫rearrear為隨機臟值首次入隊訪問野內存雙指針必須同步初始化為 NULL2malloc后先訪問節(jié)點成員再判空申請失敗時直接對空指針解引用程序崩潰先判空確認成功后再使用節(jié)點3新節(jié)點未顯式置next NULL尾節(jié)點next為垃圾值遍歷/銷毀時越界每個新節(jié)點創(chuàng)建后必須手動置空 next4刪除最后一個節(jié)點只置空frontrear成為野指針指向已釋放內存尾節(jié)點刪除后front、rear 同時置 NULL5銷毀隊列只釋放節(jié)點不重置狀態(tài)銷毀后rear野指針、size殘留舊值銷毀后手動重置 rear 與 size恢復空隊列狀態(tài)6局部臨時指針 free 后置 NULL冗余代碼無實際作用局部變量函數(shù)結束即銷毀僅結構體成員指針 free 后需要置空七、測試驗證7.1 測試代碼 test.c覆蓋空隊列、多次入出隊、清空后重入隊等全邊界場景#include Queue.h #include stdio.h void PrintQueue(Queue* q) { if (QueueEmpty(q)) { printf(隊列[空]\n); return; } QueueNode* cur q-front; printf(隊列); while (cur ! NULL) { printf(%d , cur-data); cur cur-next; } printf( | 頭%d 尾%d size%d\n, QueueFront(q), QueueBack(q), QueueSize(q)); } int main(void) { Queue q; QueueInit(q); printf(初始化完成\n); PrintQueue(q); printf(\n入隊 10,20,30,40\n); QueuePush(q, 10); QueuePush(q, 20); QueuePush(q, 30); QueuePush(q, 40); PrintQueue(q); printf(\n出隊兩次\n); QueuePop(q); PrintQueue(q); QueuePop(q); PrintQueue(q); printf(\n入隊 50,60\n); QueuePush(q, 50); QueuePush(q, 60); PrintQueue(q); printf(\n全部出隊直到空\n); while (!QueueEmpty(q)) { QueuePop(q); PrintQueue(q); } printf(\n空隊列重新入隊 77\n); QueuePush(q, 77); PrintQueue(q); QueueDestroy(q); printf(\n隊列銷毀完畢\n); return 0; }7.2 運行結果八、復雜度分析操作時間復雜度QueuePush入隊O(1)QueuePop出隊O(1)QueueFront取隊頭O(1)QueueBack取隊尾O(1)QueueSize求長度O(1)QueueEmpty判空O(1)QueueDestroy銷毀O(N)銷毀操作必須遍歷釋放所有節(jié)點時間復雜度最低為 O(N)。九、拓展去掉 size 后的變化如果移除size成員結構體變?yōu)閠ypedef struct Queue { QueueNode* front; QueueNode* rear; } Queue;產生的影響QueueEmpty 不受影響仍可通過front NULL判空保持 O(1)QueueSize 性能下降必須從頭遍歷鏈表計數(shù)時間復雜度退化為 O(N)入隊出隊代碼簡化無需維護 size 的加減操作簡單說size最大的價值就是把「求長度」從線性遍歷變成了常數(shù)時間。寫在最后從順序棧到鏈式隊列核心都是「操作受限的線性表」但實現(xiàn)思路差異顯著順序棧靠「數(shù)組 top 下標」發(fā)揮尾插尾刪的優(yōu)勢鏈式隊列靠「單鏈表 雙指針 size」適配頭刪尾插的特性比起死記代碼更值得沉淀的是三點數(shù)據(jù)結構選型要匹配操作場景沒有絕對最優(yōu)只有最合適鏈式結構最容易出錯的永遠是邊界0個節(jié)點、1個節(jié)點寫數(shù)據(jù)結構本質是維護「不變量」每一次操作后結構的狀態(tài)規(guī)則必須始終成立Gitee 倉庫地址數(shù)據(jù)結構/8.17 隊列練習Queue · Luminous/Code_2026 - 碼云 - 開源中國