一、棧到底是個(gè)啥說白了棧就是一種操作受限的線性表。 普通的數(shù)組、鏈表想在哪插在哪刪都行但棧不行它只開放一端給你操作這一端叫棧頂另一端封死叫棧底。所有的插入、刪除都只能在棧頂做。這種限制催生出了棧最核心的特性后進(jìn)先出LIFO, Last In First Out。 舉個(gè)最生活化的例子摞書。 你往桌上放書一本本往上疊最后放的那本在最上面你要拿書只能先拿最上面那本。最后放上去的第一個(gè)被拿下來 —— 這就是標(biāo)準(zhǔn)的棧邏輯。往棧里加數(shù)據(jù)叫入棧壓棧從棧里刪數(shù)據(jù)叫出棧彈棧倆操作都只碰棧頂不碰棧底。二、棧為什么偏愛數(shù)組實(shí)現(xiàn)理論上數(shù)組和鏈表都能實(shí)現(xiàn)棧但實(shí)際寫代碼的時(shí)候幾乎所有人都會(huì)選數(shù)組。 原因非常實(shí)在棧的所有操作都在尾部而數(shù)組的尾插、尾刪天然就是 O (1)完全對(duì)上了再加上數(shù)組是連續(xù)內(nèi)存緩存命中率高比鏈表省空間還跑得快沒理由不用。棧的結(jié)構(gòu)長什么樣一個(gè)動(dòng)態(tài)數(shù)組實(shí)現(xiàn)的棧結(jié)構(gòu)體里就三樣?xùn)|西typedef int STDataType; typedef struct Stack { STDataType* a; // 存數(shù)據(jù)的動(dòng)態(tài)數(shù)組 int top; // 棧頂標(biāo)記指向下一個(gè)可插入的位置 int capacity; // 數(shù)組總共能存多少數(shù)據(jù) } ST;這里說下top的約定一般我們讓它指向 “棧頂元素的下一個(gè)空位”。比如空棧的時(shí)候top0入棧一個(gè)元素后top1這樣top的值剛好等于棧里元素的個(gè)數(shù)省得單獨(dú)維護(hù) size。初始化和銷毀初始化就是把棧置成空狀態(tài)銷毀就是把申請(qǐng)的數(shù)組釋放掉避免內(nèi)存泄漏。// 初始化棧 void STInit(ST* ps) { assert(ps); ps-a NULL; ps-top 0; ps-capacity 0; } // 銷毀棧 void STDestroy(ST* ps) { assert(ps); free(ps-a); ps-a NULL; ps-top 0; ps-capacity 0; }入棧先看容量夠不夠入棧是最常寫的操作核心就兩步先檢查容量滿了就擴(kuò)容再把數(shù)據(jù)放到棧頂top往后挪一位。擴(kuò)容這里有個(gè)細(xì)節(jié)不用直接改結(jié)構(gòu)體里的capacity先用局部變量newcap算好新容量申請(qǐng)成功了再正式賦值。萬一realloc失敗了原棧的數(shù)據(jù)和容量都不會(huì)亂這是寫動(dòng)態(tài)結(jié)構(gòu)的基本防御性寫法。// 入棧 void STPush(ST* ps, STDataType x) { assert(ps); // 容量滿了先擴(kuò)容 if (ps-top ps-capacity) { int newcap ps-capacity 0 ? 4 : 2 * ps-capacity; STDataType* tmp (STDataType*)realloc(ps-a, newcap * sizeof(STDataType)); if (tmp NULL) { perror(realloc 申請(qǐng)失敗); exit(1); } ps-a tmp; ps-capacity newcap; } // 棧頂放入數(shù)據(jù)top后移 ps-a[ps-top] x; }出棧和取棧頂出棧特別簡單只要棧不是空的把top減 1 就完事了。 不用特意把原位置的數(shù)據(jù)清掉因?yàn)橄麓稳霔?huì)直接覆蓋。數(shù)據(jù)還在那里但只要top不認(rèn)可它它就不算棧里的元素了。// 出棧 void STPop(ST* ps) { assert(ps); assert(ps-top 0); // 空棧不能彈 ps-top--; } // 取棧頂元素 STDataType STTop(ST* ps) { assert(ps); assert(ps-top 0); return ps-a[ps-top - 1]; }幾個(gè)實(shí)用的小接口判空、取元素個(gè)數(shù)都是一行代碼的事// 棧里有多少個(gè)元素 int STSize(ST* ps) { assert(ps); return ps-top; } // 棧是不是空的 bool STEmpty(ST* ps) { assert(ps); return ps-top 0; }三、棧的特點(diǎn)和適用場景棧的幾個(gè)關(guān)鍵特點(diǎn)操作單一只在棧頂增刪邏輯簡單不容易出 bug效率極高入棧、出棧、取棧頂全是 O (1)幾乎沒有額外開銷不支持隨機(jī)訪問想拿棧底的元素必須把上面的全彈出去內(nèi)存連續(xù)數(shù)組實(shí)現(xiàn)的緩存友好訪問速度快