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