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