寫在前面上一篇我們從內存布局、操作效率、CPU緩存三個維度完整對比了順序表與鏈表的底層差異并在最后引出了一種操作受限的線性表——棧。棧的邏輯規則非常簡單所有插入、刪除操作只能在棧頂完成遵循后進先出LIFO的原則。但真正動手用C語言實現時很多初學者都會卡在一個經典問題上top到底應該指向哪里常見的實現約定有兩種top指向棧頂元素的下一個位置初始化為 0top直接指向當前棧頂元素初始化為 -1兩種寫法都能正確實現棧沒有絕對的對錯核心原則只有一個一旦確定了 top 的語義初始化、入棧、出棧、判空、取棧頂等所有操作必須嚴格遵循同一套規則絕對不能混用。本文先完整實現我們日常使用的top0版本對齊后續C學習的思維習慣再補充常見的top-1經典寫法最后聊一個很值得思考的問題明明可以直接訪問結構體成員為什么還要專門封裝StackPush、StackSize這些函數本篇代碼倉庫位置數據結構/8.15 棧的練習Stack · Luminous/Code_2026 - 碼云 - 開源中國一、順序棧的底層結構設計順序棧的本質就是動態數組 棧頂標記底層復用了動態順序表的擴容邏輯只是限制了所有操作只能在尾部進行。1.1 頭文件結構體與接口定義我們先定義棧的結構體和對外接口命名和功能都對齊后續C的學習習慣同時明確判空規則棧為空返回非零值不為空返回0。// Stack.h #pragma once #includeassert.h #include stdlib.h typedef int STDataType; typedef struct Stack { STDataType* a; int top; // 棧頂標記 int capacity; // 棧的總容量 }Stack; // 初始化棧 void StackInit(Stack* ps); // 入棧 void StackPush(Stack* ps, STDataType data); // 出棧 void StackPop(Stack* ps); // 獲取棧頂元素 STDataType StackTop(Stack* ps); // 獲取棧中有效元素個數 int StackSize(Stack* ps); // 檢測棧是否為空為空返回非零結果不為空返回0 int StackEmpty(Stack* ps); // 銷毀棧 void StackDestroy(Stack* ps);1.2 三個核心成員的作用結構體里的三個變量各司其職共同維護一個動態棧a指向動態數組的指針真正存儲棧中元素的內存空間top棧頂位置標記具體含義由我們約定是整個棧最核心的變量capacity記錄當前已申請的內存總容量空間不足時觸發擴容二、主流實現top 指向棧頂元素的下一個位置這是我們日常開發、后續學習C STL最常用的約定也是本文的主力實現版本。2.1 核心規則約定我們可以把棧的有效元素理解為左閉右開區間[0, top)初始化top 0表示沒有有效元素空棧判定top 0有效元素個數直接等于top入棧先在top位置賦值再top取棧頂訪問a[top - 1]出棧直接top--滿棧判定top capacity舉個例子棧里有4個元素時內存布局是這樣的下標 0 1 2 3 4 數據 | 10 | 20 | 30 | 40 | | ↑ toptop4既代表下一個待插入的位置也等于當前有效元素的總數。2.2 完整實現代碼以下是完整的Stack.c實現嚴格遵循上面的約定// Stack.c #includeStack.h // 初始化棧 void StackInit(Stack* ps) { assert(ps); ps-a NULL; ps-top 0; ps-capacity 0; } // 入棧 void StackPush(Stack* ps, STDataType data) { assert(ps); // 空間不足時觸發擴容 if (ps-capacity ps-top) { int num ps-capacity 0 ? 4 : ps-capacity * 2; STDataType* tmp (STDataType*)realloc(ps-a, sizeof(STDataType) * num); if(tmp NULL) { perror(realloc fail); exit(-1); } ps-a tmp; ps-capacity num; } ps-a[ps-top] data; ps-top; } // 出棧 void StackPop(Stack* ps) { assert(ps); assert(ps-top 0); // 空棧禁止出棧 ps-top--; } // 獲取棧頂元素 STDataType StackTop(Stack* ps) { assert(ps); assert(ps-top 0); // 空棧無棧頂元素 return ps-a[ps-top - 1]; } // 獲取棧中有效元素個數 int StackSize(Stack* ps) { assert(ps); return ps-top; } // 檢測棧是否為空為空返回非零不為空返回0 int StackEmpty(Stack* ps) { assert(ps); return ps-top 0; } // 銷毀棧 void StackDestroy(Stack* ps) { assert(ps); free(ps-a); ps-a NULL; ps-top 0; ps-capacity 0; }2.3 關鍵細節拆解1入棧為什么先賦值再top因為top本身就指向第一個空閑的可插入位置直接寫入數據即可寫入后top向后移動一位繼續指向新的空閑位置。順序不能顛倒否則會跳過下標0的位置造成空間浪費。2取棧頂為什么是 top-1top指向的是棧頂元素的下一個位置不是有效元素本身。真正的棧頂元素是top前面的那一個也就是下標為top-1的元素。3出棧為什么只需要top--不用清零數據出棧本質上是「縮小有效區間」。top--之后原來的棧頂位置就不在[0, top)這個有效區間里了邏輯上已經被刪除。 內存里的舊數據雖然還在但后續入棧時會直接被新數據覆蓋完全不需要手動清零。多一步清零反而會增加不必要的開銷。三、教材經典實現top 直接指向棧頂元素這是數據結構教材里非常常見的入門寫法top不再代表尾后位置而是直接記錄當前棧頂元素的數組下標。3.1 核心規則約定初始化top -1用負數標記空棧狀態空棧判定top -1有效元素個數top 1入棧先top再在top位置賦值取棧頂直接訪問a[top]出棧直接top--滿棧判定top capacity - 1同樣是4個元素此時的內存布局是這樣的下標 0 1 2 3 數據 | 10 | 20 | 30 | 40 | ↑ toptop3就是棧頂元素的下標有效元素總數是 314。3.2 完整實現代碼頭文件完全不需要修改只需要替換Stack.c的內部實現對外接口保持完全一致// Stack_top_minus_one.c #includeStack.h // 初始化棧 void StackInit(Stack* ps) { assert(ps); ps-a NULL; ps-top -1; ps-capacity 0; } // 入棧 void StackPush(Stack* ps, STDataType data) { assert(ps); // 棧滿時擴容top到達最后一個有效下標 if (ps-top ps-capacity - 1) { int num ps-capacity 0 ? 4 : ps-capacity * 2; STDataType* tmp (STDataType*)realloc(ps-a, sizeof(STDataType) * num); if(tmp NULL) { perror(realloc fail); exit(-1); } ps-a tmp; ps-capacity num; } ps-top; ps-a[ps-top] data; } // 出棧 void StackPop(Stack* ps) { assert(ps); assert(ps-top 0); // 空棧禁止出棧 ps-top--; } // 獲取棧頂元素 STDataType StackTop(Stack* ps) { assert(ps); assert(ps-top 0); return ps-a[ps-top]; } // 獲取棧中有效元素個數 int StackSize(Stack* ps) { assert(ps); return ps-top 1; } // 檢測棧是否為空為空返回非零不為空返回0 int StackEmpty(Stack* ps) { assert(ps); return ps-top -1; } // 銷毀棧 void StackDestroy(Stack* ps) { assert(ps); free(ps-a); ps-a NULL; ps-top -1; ps-capacity 0; }注意兩個版本的函數名完全一致不要同時加入同一個工程編譯否則會出現重復定義錯誤可以分別測試。3.3 高頻易錯點初始值不能錯必須是-1如果寫成0第一個元素會存在下標1的位置永久浪費下標0的空間。入棧順序不能反必須先移動top再賦值否則會覆蓋原有的棧頂數據。擴容條件要對應滿棧判斷是top capacity - 1不是top capacity。四、兩種 top 約定核心對比兩套寫法的所有差異都來自「top的語義」這一個核心定義。我們整理成對照表方便復習和做題操作項top 指向棧頂下一位推薦版本top 指向棧頂元素教材版本初始化top 0top -1空棧條件top 0top -1有效元素個數等于top等于top 1入棧順序先賦值a[top]data再top先top再賦值a[top]data取棧頂a[top - 1]a[top]出棧操作top--top--滿棧條件top capacitytop capacity - 1再次強調兩套寫法沒有優劣之分但絕對不能混用。比如初始化用top0取棧頂卻寫a[top]。五、為什么更推薦 top 指向下一位置的寫法兩種實現都能正確運行但更推薦top0的版本主要有三個原因契合「左閉右開」的通用思維有效區間[0, top)是編程里非常經典的區間約定和數組遍歷、字符串、后續C迭代器的設計思路完全統一學習成本更低。計算更直觀減少出錯概率有效元素個數直接等于top不需要額外做 1 計算待插入位置天然就是a[top]邏輯更順。對齊后續C學習雖然C的std::stack是容器適配器沒有強制規定底層下標實現但這種「尾后位置」的設計思路和STL容器的底層邏輯高度一致。現在習慣這套寫法后面學C容器時會非常順暢。六、思考為什么要封裝成函數直接訪問 st.top 不行嗎很多初學者剛寫的時候都會有疑問元素個數不就是top嗎直接寫st.top不行嗎干嘛還要多寫一層StackSize(st)這其實是一個非常重要的工程化思維轉變從「寫出能跑的代碼」到「設計可維護的結構」。封裝的價值主要體現在三點1. 隱藏實現細節接口保持穩定如果外部都通過StackSize()獲取元素個數那么無論我們底層換成top0還是top-1的實現外部調用代碼一行都不用改。 我們只需要修改函數內部的實現就能完成底層邏輯的切換這就是「接口不變實現可替換」。2. 保護數據結構避免非法修改如果結構體成員直接暴露外部代碼可以隨意修改top的值比如誤寫st.top 100會直接導致整個棧的結構錯亂排查起來非常麻煩。 通過函數封裝外部只能執行入棧、出棧這些合法操作從根源上避免了非法修改保證了數據結構的安全性。3. 語義更清晰代碼可讀性更高看到StackSize(st)任何人都能立刻明白是「獲取棧的元素個數」但看到st.top還要先回憶這個項目里的top是哪一種約定。 函數封裝把「怎么算」的細節藏在了內部調用者只需要關心「做什么」代碼的可讀性和可維護性都會大幅提升。C語言沒有C類的private訪問權限但通過「頭文件聲明接口 源文件實現細節」的方式已經可以模擬出封裝的效果。這種思維習慣也是從C語言過渡到C面向對象的重要鋪墊。七、測試驗證下面是完整的測試代碼可以驗證所有接口的正確性。有意思的是無論底層用哪一種top約定這套測試代碼都完全不用改——這正是接口封裝的意義。// test.c #include Stack.h #include stdio.h int main() { Stack st; StackInit(st); StackPush(st, 1); StackPush(st, 2); StackPush(st, 3); StackPush(st, 4); StackPush(st, 5); // 第5個元素觸發擴容 printf(size%d\n, StackSize(st)); printf(top%d\n, StackTop(st)); StackPop(st); printf(pop之后top%d\n, StackTop(st)); if (StackEmpty(st)) { printf(棧為空\n); } else { printf(棧不為空\n); } while (!StackEmpty(st)) { StackPop(st); } StackDestroy(st); printf(銷毀棧成功\n); return 0; }本篇全部示例代碼已上傳代碼倉庫包含兩套 top 實現源碼、測試用例以及使用提示文檔。 讀者可以直接下載本地編譯運行對照博文加深對順序棧接口封裝與 top 兩種語義的理解。代碼倉庫數據結構/8.15 棧的練習Stack · Luminous/Code_2026 - 碼云 - 開源中國八、復雜度分析順序棧的所有核心操作時間復雜度都非常優秀操作時間復雜度說明入棧 Push均攤 O(1)絕大多數情況直接寫入僅擴容時需要搬遷數據倍增擴容下均攤為O(1)出棧 PopO(1)僅修改top的值無額外開銷獲取棧頂 TopO(1)直接按下標訪問判空 EmptyO(1)僅一次比較獲取大小 SizeO(1)直接返回top的值這里的「均攤O(1)」和動態順序表的擴容邏輯完全一致雖然單次擴容開銷很大但擴容的次數非常少把開銷平攤到所有入棧操作上平均每次操作的成本依然是常數級。九、本篇總結手寫順序棧的代碼本身并不復雜但里面藏著兩個非常重要的認知點變量語義是邊界問題的根源很多人寫棧容易出邊界錯誤本質不是代碼寫錯了而是沒有先定義清楚top到底代表什么。先定語義再寫代碼所有邊界問題都會迎刃而解。封裝不是冗余是工程化的基礎多寫一層函數調用不是多此一舉而是在隔離實現細節、保護數據安全、提升代碼可維護性。這也是我們從寫玩具代碼到寫工程代碼的第一步。理解了順序棧的實現思路再學隊列就會非常輕松——隊列同樣是操作受限的線性表只是換成了兩端操作、先進先出的規則。