棧這種結構在嵌入式里其實是非常常用的，比如函數調用與返回就是典型的棧應用，雖然很多時候棧都是CPU系統在自動管理，我們只需要在鏈接文件里分配棧大小以及棧存放位置，但稍微了解一下棧的原理會更加利于我們去理解嵌入式代碼執行機制，以及幫助我們進一步去調試。

1. 何為堆棧？

堆 HEAP與棧 STACK 是兩個不同概念，其本質上都是一種數據結構。

棧是一種按數據項排列的數據結構，只能在一端（棧頂 top）對數據項進行插入和刪除，其符合后進先出（Last-In / First-Out）原則。棧（os）一般是由編譯器自動分配釋放，其使用的是一級緩存。

堆也是一種分配方式類似于鏈表的數據結構，其可以在任意位置對數據項進行操作。堆（os）一般由程序員手動分配釋放，其使用的是二級緩存。

在嵌入式世界里，堆棧一般指的僅是棧。

2. 作用與意義

在 MCU 中，棧這種結構一般被 cpu 和 os 所使用。

在 cpu 裸機中使用情況分兩種：一、主動進行函數調用時，STACK 用以暫存下一條指令地址、函數參數、函數中定義的局部變量；二、硬中斷來臨時，暫存當前執行的現場數據（下一條指令地址、各種緩存數據），中斷結束后，用以恢復。

在 os 中使用時，硬棧的使用同 cpu 裸機；但 os 一般會為每個任務額外分配一個軟棧，在任務調度時，可用軟中斷打斷當前正在執行的任務，棧則用以保存各自任務以恢復。

3. 軟硬之分

硬件堆棧：是通過寄存器 SP 作為索引指針的地址，是調用了 BL 等函數調用指令后硬件自動填充的堆棧。

軟件堆棧：是編譯器為了處理一些參數傳遞而做的堆棧，會由編譯器自動產生和處理，可以通過相應的編譯選項對其進行編輯。

簡單一點說，硬件堆棧主要做為地址堆棧用，而軟件堆棧主要會被分配成數據堆棧。或看其棧頂指針是否和 CPU 具有特殊的關聯，有關聯者（如 SP）“硬”，而無關聯者“軟”。

4. 棧的純 C 實現

基本的抽象數據類型（ADT）是編寫 C 程序必要的過程，這類 ADT 有鏈表、堆棧、隊列和樹等，本節主要講解下堆棧的幾種實現方法以及他們的優缺點。

堆棧（stack）的顯著特點是后進先出（Last-In First-Out, LIFO），其實現的方法有三種可選方案：靜態數組、動態分配的數組、動態分配的鏈式結構。

靜態數組：特點是要求結構的長度固定，而且長度在編譯時候就得確定。其優點是結構簡單，實現起來方便而不容易出錯。而缺點就是不夠靈活以及固定長度不容易控制，適用于知道明確長度的場合。

動態數組：特點是長度可以在運行時候才確定以及可以更改原來數組的長度。優點是靈活，缺點是由此會增加程序的復雜性。

鏈式結構：特點是無長度上線，需要的時候再申請分配內存空間，可最大程度上實現靈活性。缺點是鏈式結構的鏈接字段需要消耗一定的內存，在鏈式結構中訪問一個特定元素的效率不如數組。

首先先確定一個堆棧接口的頭文件，里面包含了各個方案下的函數原型，放在一起是為了實現程序的模塊化以及便于修改。然后再接著分別介紹各個方案的具體實施方法。

堆棧接口 stack.h 文件代碼：

4.1 靜態數組

在靜態數組堆棧中，STACK_SIZE 表示堆棧所能存儲的元素的最大值，用 top_element 作為數組下標來表示堆棧里面的元素，當 top_element == -1 的時候表示堆棧為空；當 top_element == STACK_SIZE - 1 的時候表示堆棧為滿。push 的時候 top_element 加 1，top_element == 0 時表示第一個堆棧元素；pop 的時候 top_element 減 1。

a_stack.c 源代碼如下：

4.2 動態數組

頭文件還是用 stack.h，改動的并不是很多，增加了 stack_size 變量取代 STACK_SIZE 來保存堆棧的長度，數組由一個指針來代替，在全局變量下缺省為 0。

create_stack 函數首先檢查堆棧是否已經創建，然后才分配所需數量的內存并檢查分配是否成功。destroy_stack 函數首先檢查堆棧是否存在，已經釋放內存之后把長度和指針變量重新設置為零。is_empty 和 is_full 函數中添加了一條斷言，防止任何堆棧函數在堆棧被創建之前就被調用。

d_stack.c 源代碼如下：

4.3 鏈式結構

由于只有堆棧頂部元素才可以被訪問，因此適用單鏈表可以很好實現鏈式堆棧，而且無長度限制。把一個元素壓入堆棧是通過在鏈表頭部添加一個元素實現。彈出一個元素是通過刪除鏈表頭部第一個元素實現。由于沒有長度限制，故不需要 create_stack 函數，需要 destroy_stack 進行釋放內存以避免內存泄漏。

l_stack.c 源代碼如下：