一棧Stack1概念棧是一種特殊的線性表只允許在固定的一端進行插入和刪除操作。這一端叫棧頂另一端叫棧底。入棧Push在棧頂放入數(shù)據(jù)出棧Pop從棧頂取出數(shù)據(jù)核心規(guī)則后進先出LIFOLast In First Out為什么棧用數(shù)組實現(xiàn)而不是鏈表數(shù)組順序棧鏈表鏈棧尾插直接賦值a[top] x,O(1)需要malloc新節(jié)點內(nèi)存連續(xù)性連續(xù)緩存友好分散緩存不友好額外空間無每個節(jié)點都多要一個next指針結論棧永遠只在尾部操作數(shù)組完美避開了自己的弱點頭部/中間插入慢所以數(shù)組是棧的最優(yōu)解2棧的實現(xiàn)結構體定義typedef int STDataType; typedef struct Stack { STDataType* a; // 指向動態(tài)數(shù)組的指針真正的數(shù)據(jù)存儲區(qū)在堆上 int top; // 棧頂位置也是當前元素個數(shù)指向下一個要存放的位置 int capacity; // 當前已分配的空間大小能容納多少個元素 } ST;注意top和capacity的類型是int不是STDataType。它們存的是“管理信息”下標/個數(shù)不是“業(yè)務數(shù)據(jù)”。初始化void STInit(ST* ps) { assert(ps ! NULL); ps-a NULL; // 一開始不分配內(nèi)存等第一次Push時再分配 ps-top 0; ps-capacity 0; }銷毀void STDestroy(ST* ps) { assert(ps ! NULL); free(ps-a); // 釋放堆區(qū)的數(shù)據(jù)內(nèi)存 ps-a NULL; // 置空防止野指針 ps-top 0; ps-capacity 0; }擴容void CheckIfExpand(ST* ps) { // 容量夠用直接返回 if (ps-top ps-capacity) { return; } // 新容量首次分配4個后續(xù)翻倍 int new_capacity (ps-capacity 0) ? 4 : ps-capacity * 2; // ?? 關鍵用臨時指針接收 realloc 的返回值 STDataType* tmp (STDataType*)realloc(ps-a, new_capacity * sizeof(STDataType)); if (tmp NULL) { perror(擴容失敗); exit(1); } ps-a tmp; ps-capacity new_capacity; }為什么用臨時指針如果realloc失敗返回NULL直接用ps-a realloc(...)會導致原來的數(shù)據(jù)丟失ps-a被置為NULL舊內(nèi)存無法釋放也無法訪問。用tmp接住失敗時原數(shù)據(jù)還在。realloc傳入NULL等價于malloc當ps-a NULL且ps-capacity 0時realloc(NULL, 4 * sizeof(...))等同于malloc。所以擴容函數(shù)同時處理了“首次分配”和“后續(xù)擴容”。入棧void STPush(ST* ps, STDataType x) { assert(ps ! NULL); CheckIfExpand(ps); // 先確?？臻g夠 ps-a[ps-top] x; // 在棧頂位置放入數(shù)據(jù) ps-top; // top 后移 }出棧void STPop(ST* ps) { assert(ps ! NULL); assert(ps-top 0); // 棧不能為空 ps-top--; // 只移動指針不刪除數(shù)據(jù) }注意我們只是把top減了 1舊數(shù)據(jù)還在數(shù)組里。下次Push時會被覆蓋。不需要把舊數(shù)據(jù)清零那是浪費時間。取棧頂元素STDataType STTop(ST* ps) { assert(ps ! NULL); assert(ps-top 0); return ps-a[ps-top - 1]; // 棧頂元素在 top-1 位置 }判空和元素個數(shù)bool STEmpty(ST* ps) { assert(ps ! NULL); return ps-top 0; // 簡潔寫法 本身返回 bool } int STSize(ST* ps) { assert(ps ! NULL); return ps-top; // top 的值就是元素個數(shù) }二隊列Queue1概念隊列只允許在一端插入隊尾在另一端刪除隊頭。入隊Push在隊尾插入出隊Pop從隊頭刪除核心規(guī)則先進先出FIFOFirst In First Out為什么隊列用鏈表實現(xiàn)而不是數(shù)組普通隊列用數(shù)組出隊時要把所有元素往前搬O(n)太慢。循環(huán)隊列用數(shù)組雖然解決了搬移問題但需要處理“空/滿”判定后面細說邏輯復雜一些。鏈式隊列出隊只需要改指針O(1)邏輯自然。代價是每次入隊都要malloc。結論鏈式隊列是隊列最自然的實現(xiàn)方式適合通用場景。循環(huán)隊列適合“已知最大容量、追求極致性能”的場景比如嵌入式、音視頻緩沖。2隊列的實現(xiàn)結構體定義typedef int QDataType; // 隊列節(jié)點 typedef struct QueueNode { QDataType val; struct QueueNode* next; } QNode; // 隊列結構兩個指針 一個計數(shù)器 typedef struct Queue { QNode* phead; // 隊頭指針 QNode* ptail; // 隊尾指針 int size; // 當前元素個數(shù) } Queue;為什么要有ptail因為入隊在隊尾如果沒有ptail每次入隊都要遍歷到鏈表末尾O(n)。有了ptail入隊 O(1)。初始化void QueueInit(Queue* pq) { assert(pq ! NULL); pq-phead NULL; pq-ptail NULL; pq-size 0; }創(chuàng)建節(jié)點內(nèi)部函數(shù)QNode* CreateNode(QDataType x) { QNode* newnode (QNode*)malloc(sizeof(QNode)); if (newnode NULL) { perror(malloc fail); exit(1); } newnode-val x; newnode-next NULL; return newnode; }入隊隊尾插入void QueuePush(Queue* pq, QDataType x) { assert(pq ! NULL); QNode* newnode CreateNode(x); if (pq-phead NULL) { // 隊列為空頭和尾都指向新節(jié)點 pq-phead newnode; pq-ptail newnode; } else { // 隊列非空掛在尾巴后面 pq-ptail-next newnode; pq-ptail newnode; } pq-size; }出隊隊頭刪除void QueuePop(Queue* pq) { assert(pq ! NULL); assert(pq-phead ! NULL); // 隊列不能為空 QNode* tmp pq-phead-next; // 記住第二個節(jié)點 free(pq-phead); // 釋放隊頭 pq-phead tmp; // 頭指針后移 // ?? 關鍵如果刪完隊列變空了ptail 也要置 NULL if (pq-phead NULL) { pq-ptail NULL; } pq-size--; }經(jīng)典錯誤如果隊列只有一個節(jié)點出隊后phead變成NULL但ptail還指向那個已經(jīng)被釋放的節(jié)點。下次Push時訪問ptail-next就崩潰了正確做法刪完后判斷phead是否為空如果為空說明隊列空了ptail也要同步置NULL。取隊頭/隊尾QDataType QueueFront(Queue* pq) { assert(pq ! NULL); assert(pq-phead ! NULL); return pq-phead-val; } QDataType QueueBack(Queue* pq) { assert(pq ! NULL); assert(pq-ptail ! NULL); return pq-ptail-val; }判空和元素個數(shù)bool QueueEmpty(Queue* pq) { assert(pq ! NULL); return pq-size 0; // 或者 return pq-phead NULL; } int QueueSize(Queue* pq) { assert(pq ! NULL); return pq-size; }銷毀隊列void QueueDestroy(Queue* pq) { assert(pq ! NULL); QNode* cur pq-phead; while (cur ! NULL) { QNode* next cur-next; // 先記住下一個 free(cur); // 釋放當前 cur next; // 移到下一個 } // 所有節(jié)點釋放完后指針置空 pq-phead NULL; pq-ptail NULL; pq-size 0; }三、經(jīng)典算法題1 有效的括號LeetCode 20題目給定一個只包含()[]{}的字符串判斷括號是否匹配。思路遇到左括號([{就入棧遇到右括號)]}就檢查棧頂是否是對應的左括號不匹配直接返回false遍歷完后棧必須為空bool isValid(char* s) { ST st; STInit(st); for (int i 0; s[i] ! \0; i) { if (s[i] ( || s[i] [ || s[i] {) { STPush(st, s[i]); } else { if (STEmpty(st)) return false; char top STTop(st); STPop(st); if (!checkthefit(top, s[i])) return false; } } bool result STEmpty(st); STDestroy(st); // ?? 別忘了銷毀 return result; }關鍵函數(shù)返回前一定要調(diào)用STDestroy釋放棧內(nèi)部動態(tài)分配的數(shù)組內(nèi)存。否則每次調(diào)用都會泄漏內(nèi)存。2 用隊列實現(xiàn)棧LeetCode 225核心思想兩個隊列q1主隊列和q2輔助隊列。Push 操作新元素放入空的那個隊列把另一個非空隊列的所有元素全部搬過來這樣非空隊列的隊頭永遠是最新入棧的元素typedef struct { Queue q1; Queue q2; } MyStack; void myStackPush(MyStack* obj, int x) { // 找到空隊列 Queue* empty QueueEmpty(obj-q1) ? obj-q2 : obj-q1; Queue* nonEmpty QueueEmpty(obj-q1) ? obj-q1 : obj-q2; QueuePush(empty, x); while (!QueueEmpty(nonEmpty)) { QueuePush(empty, QueueFront(nonEmpty)); QueuePop(nonEmpty); } }3用棧實現(xiàn)隊列LeetCode 232核心思想in棧只管入隊out棧只管出隊。Push直接壓入in棧Pop/Peek如果out棧為空把in棧的所有元素搬到out棧然后從out棧彈出/查看typedef struct { ST in; ST out; } MyQueue; int myQueuePop(MyQueue* obj) { // 只有在 out ?？盏臅r候才搬運 if (obj-out.top 0) { while (obj-in.top ! 0) { STPush(obj-out, STTop(obj-in)); STPop(obj-in); } } int x STTop(obj-out); STPop(obj-out); return x; }4 設計循環(huán)隊列LeetCode 622核心難點用數(shù)組實現(xiàn)隊列時如何區(qū)分“隊空”和“隊滿”標準做法浪費一個空間判空front rear判滿(rear 1) % capacity front缺點永遠浪費一個位置最多存capacity - 1個元素我的做法引入size變量判空size 0判滿size capacity優(yōu)點空間全部利用邏輯更直觀typedef struct { int* a; int front; int rear; int size; int capacity; } MyCircularQueue; bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { if (obj-size obj-capacity) return false; obj-a[obj-rear] value; obj-rear (obj-rear 1) % obj-capacity; obj-size; return true; } bool myCircularQueueDeQueue(MyCircularQueue* obj) { if (obj-size 0) return false; obj-front (obj-front 1) % obj-capacity; obj-size--; return true; }