嵌入式里堆棧的原理介紹和如何實(shí)現(xiàn)純C實(shí)現(xiàn)

棧這種結(jié)構(gòu)在嵌入式里其實(shí)是非常常用的，比如函數(shù)調(diào)用與返回就是典型的棧應(yīng)用，雖然很多時(shí)候棧都是CPU系統(tǒng)在自動(dòng)管理，我們只需要在鏈接文件里分配棧大小以及棧存放位置，但稍微了解一下棧的原理會(huì)更加利于我們?nèi)ダ斫馇度胧酱a執(zhí)行機(jī)制，以及幫助我們進(jìn)一步去調(diào)試。

1. 何為堆棧？

堆 HEAP與棧 STACK 是兩個(gè)不同概念，其本質(zhì)上都是一種數(shù)據(jù)結(jié)構(gòu)。

棧是一種按數(shù)據(jù)項(xiàng)排列的數(shù)據(jù)結(jié)構(gòu)，只能在一端（棧頂 top）對(duì)數(shù)據(jù)項(xiàng)進(jìn)行插入和刪除，其符合后進(jìn)先出（Last-In / First-Out）原則。棧（os）一般是由編譯器自動(dòng)分配釋放，其使用的是一級(jí)緩存。

堆也是一種分配方式類似于鏈表的數(shù)據(jù)結(jié)構(gòu)，其可以在任意位置對(duì)數(shù)據(jù)項(xiàng)進(jìn)行操作。堆（os）一般由程序員手動(dòng)分配釋放，其使用的是二級(jí)緩存。

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

2. 作用與意義

在 MCU 中，棧這種結(jié)構(gòu)一般被 cpu 和 os 所使用。

在 cpu 裸機(jī)中使用情況分兩種：一、主動(dòng)進(jìn)行函數(shù)調(diào)用時(shí)，STACK 用以暫存下一條指令地址、函數(shù)參數(shù)、函數(shù)中定義的局部變量；二、硬中斷來(lái)臨時(shí)，暫存當(dāng)前執(zhí)行的現(xiàn)場(chǎng)數(shù)據(jù)（下一條指令地址、各種緩存數(shù)據(jù)），中斷結(jié)束后，用以恢復(fù)。

在 os 中使用時(shí)，硬棧的使用同 cpu 裸機(jī)；但 os 一般會(huì)為每個(gè)任務(wù)額外分配一個(gè)軟棧，在任務(wù)調(diào)度時(shí)，可用軟中斷打斷當(dāng)前正在執(zhí)行的任務(wù)，棧則用以保存各自任務(wù)以恢復(fù)。

3. 軟硬之分

硬件堆棧：是通過(guò)寄存器 SP 作為索引指針的地址，是調(diào)用了 BL 等函數(shù)調(diào)用指令后硬件自動(dòng)填充的堆棧。

軟件堆棧：是編譯器為了處理一些參數(shù)傳遞而做的堆棧，會(huì)由編譯器自動(dòng)產(chǎn)生和處理，可以通過(guò)相應(yīng)的編譯選項(xiàng)對(duì)其進(jìn)行編輯。

簡(jiǎn)單一點(diǎn)說(shuō)，硬件堆棧主要做為地址堆棧用，而軟件堆棧主要會(huì)被分配成數(shù)據(jù)堆棧?；蚩雌錀ｍ斨羔樖欠窈?CPU 具有特殊的關(guān)聯(lián)，有關(guān)聯(lián)者（如 SP）“硬”，而無(wú)關(guān)聯(lián)者“軟”。

4. 棧的純 C 實(shí)現(xiàn)

基本的抽象數(shù)據(jù)類型（ADT）是編寫(xiě) C 程序必要的過(guò)程，這類 ADT 有鏈表、堆棧、隊(duì)列和樹(shù)等，本節(jié)主要講解下堆棧的幾種實(shí)現(xiàn)方法以及他們的優(yōu)缺點(diǎn)。

堆棧（stack）的顯著特點(diǎn)是后進(jìn)先出（Last-In First-Out， LIFO），其實(shí)現(xiàn)的方法有三種可選方案：靜態(tài)數(shù)組、動(dòng)態(tài)分配的數(shù)組、動(dòng)態(tài)分配的鏈?zhǔn)浇Y(jié)構(gòu)。

靜態(tài)數(shù)組：特點(diǎn)是要求結(jié)構(gòu)的長(zhǎng)度固定，而且長(zhǎng)度在編譯時(shí)候就得確定。其優(yōu)點(diǎn)是結(jié)構(gòu)簡(jiǎn)單，實(shí)現(xiàn)起來(lái)方便而不容易出錯(cuò)。而缺點(diǎn)就是不夠靈活以及固定長(zhǎng)度不容易控制，適用于知道明確長(zhǎng)度的場(chǎng)合。

動(dòng)態(tài)數(shù)組：特點(diǎn)是長(zhǎng)度可以在運(yùn)行時(shí)候才確定以及可以更改原來(lái)數(shù)組的長(zhǎng)度。優(yōu)點(diǎn)是靈活，缺點(diǎn)是由此會(huì)增加程序的復(fù)雜性。

鏈?zhǔn)浇Y(jié)構(gòu)：特點(diǎn)是無(wú)長(zhǎng)度上線，需要的時(shí)候再申請(qǐng)分配內(nèi)存空間，可最大程度上實(shí)現(xiàn)靈活性。缺點(diǎn)是鏈?zhǔn)浇Y(jié)構(gòu)的鏈接字段需要消耗一定的內(nèi)存，在鏈?zhǔn)浇Y(jié)構(gòu)中訪問(wèn)一個(gè)特定元素的效率不如數(shù)組。

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

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

4.1 靜態(tài)數(shù)組

在靜態(tài)數(shù)組堆棧中，STACK_SIZE 表示堆棧所能存儲(chǔ)的元素的最大值，用 top_element 作為數(shù)組下標(biāo)來(lái)表示堆棧里面的元素，當(dāng) top_element == -1 的時(shí)候表示堆棧為空；當(dāng) top_element == STACK_SIZE - 1 的時(shí)候表示堆棧為滿。push 的時(shí)候 top_element 加 1，top_element == 0 時(shí)表示第一個(gè)堆棧元素；pop 的時(shí)候 top_element 減 1。

a_stack.c 源代碼如下：

4.2 動(dòng)態(tài)數(shù)組

頭文件還是用 stack.h，改動(dòng)的并不是很多，增加了 stack_size 變量取代 STACK_SIZE 來(lái)保存堆棧的長(zhǎng)度，數(shù)組由一個(gè)指針來(lái)代替，在全局變量下缺省為 0。

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

d_stack.c 源代碼如下：

4.3 鏈?zhǔn)浇Y(jié)構(gòu)

由于只有堆棧頂部元素才可以被訪問(wèn)，因此適用單鏈表可以很好實(shí)現(xiàn)鏈?zhǔn)蕉褩?，而且無(wú)長(zhǎng)度限制。把一個(gè)元素壓入堆棧是通過(guò)在鏈表頭部添加一個(gè)元素實(shí)現(xiàn)。彈出一個(gè)元素是通過(guò)刪除鏈表頭部第一個(gè)元素實(shí)現(xiàn)。由于沒(méi)有長(zhǎng)度限制，故不需要 create_stack 函數(shù)，需要 destroy_stack 進(jìn)行釋放內(nèi)存以避免內(nèi)存泄漏。

l_stack.c 源代碼如下：