大家好，我是痞子衡，是正經搞技術的痞子，今天痞子衡給大家講的是嵌入式里堆疊原理及其純C實作，
今天給大家分享的這篇還是2016年之前痞子衡寫的技術檔案，花了點時間重新編排了一下格式，堆疊這種結構在嵌入式里其實是非常常用的，比如函式呼叫與回傳就是典型的堆疊應用，雖然很多時候堆疊都是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檔案代碼：
1./*
2.** 堆疊模塊的介面 stack.h
3.*/
4.#include<stdlib.h>
5.
6.#define STACK_TYPE int /* 堆疊所存盤的值的資料型別 */
7.
8./*
9.** 函式原型：create_stack
10.** 創建堆疊，引數指定堆疊可以保存多少個元素，
11.** 注意：此函式只適用于動態分配陣列形式的堆疊，
12.*/
13.void create_stack(size_t size);
14.
15./*
16.** 函式原型：destroy_stack
17.** 銷毀一個堆疊，釋放堆疊所適用的記憶體，
18.** 注意：此函式只適用于動態分配陣列和鏈式結構的堆疊，
19.*/
20.void destroy_stack(void);
21.
22./*
23.** 函式原型：push
24.** 將一個新值壓入堆疊中，引數是被壓入的值，
25.*/
26.void push(STACK_TYPE value);
27.
28./*
29.** 函式原型：pop
30.** 彈出堆疊中堆疊頂的一個值，并丟棄，
31.*/
32.void pop(void);
33.
34./*
35.** 函式原型：top
36.** 回傳堆疊頂部元素的值，但不改變堆疊結構，
37.*/
38.STACK_TYPE top(void);
39.
40./*
41.** 函式原型：is_empty
42.** 如果堆疊為空，回傳TRUE,否則回傳FALSE，
43.*/
44.int is_empty(void);
45.
46./*
47.** 函式原型：is_full
48.** 如果堆疊為滿，回傳TRUE,否則回傳FALSE，
49.*/
50.int is_full(void);
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 源代碼如下：
1./*
2.**
3.** 靜態陣列實作堆疊程式 a_stack.c ，陣列長度由#define確定
4.*/
5.
6.#include"stack.h"
7.#include<assert.h>
8.#include<stdio.h>
9.
10.#define STACK_SIZE 100 /* 堆疊最大容納元素數量 */
11.
12./*
13.** 存盤堆疊中的陣列和一個指向堆疊頂部元素的指標
14.*/
15.static STACK_TYPE stack[STACK_SIZE];
16.static int top_element = -1;
17.
18./* push */
19.void push(STACK_TYPE value)
20.{
21. assert(!is_full()); /* 壓入堆疊之前先判斷是否堆疊已滿*/
22. top_element += 1;
23. stack[top_element] = value;
24.}
25.
26./* pop */
27.void pop(void)
28.{
29. assert(!is_empty()); /* 彈出堆疊之前先判斷是否堆疊已空 */
30. top_element -= 1;
31.}
32.
33./* top */
34.STACK_TYPE top(void)
35.{
36. assert(!is_empty());
37. return stack[top_element];
38.}
39.
40./* is_empty */
41.int is_empty(void)
42.{
43. return top_element == -1;
44.}
45.
46./* is_full */
47.int is_full(void)
48.{
49. return top_element == STACK_SIZE - 1;
50.}
4.2 動態陣列
頭檔案還是用stack.h，改動的并不是很多，增加了stack_size變數取代STACK_SIZE來保存堆疊的長度，陣列由一個指標來代替，在全域變數下預設為0，
create_stack函式首先檢查堆疊是否已經創建，然后才分配所需數量的記憶體并檢查分配是否成功，destroy_stack函式首先檢查堆疊是否存在，已經釋放記憶體之后把長度和指標變數重新設定為零，is_empty 和 is_full 函式中添加了一條斷言，防止任何堆疊函式在堆疊被創建之前就被呼叫，
d_stack.c源代碼如下：
1./*
2.** 動態分配陣列實作的堆疊程式 d_stack.c
3.** 堆疊的長度在創建堆疊的函式被呼叫時候給出，該函式必須在任何其他操作堆疊的函式被呼叫之前條用，
4.*/
5.#include"stack.h"
6.#include<stdio.h>
7.#include<malloc.h>
8.#include<assert.h>
9.
10./*
11.** 用于存盤堆疊元素的陣列和指向堆疊頂部元素的指標
12.*/
13.static STACK_TYPE *stack;
14.static int stack_size;
15.static int top_element = -1;
16.
17./* create_stack */
18.void create_stack(size_t size)
19.{
20. assert(stack_size == 0);
21. stack_size = size;
22. stack = (STACK_TYPE *)malloc(stack_size * sizeof(STACK_TYPE));
23. if(stack == NULL)
24. perror("malloc分配失敗");
25.}
26.
27./* destroy */
28.void destroy_stack(void)
29.{
30. assert(stack_size > 0);
31. stack_size = 0;
32. free(stack);
33. stack = NULL;
34.}
35.
36./* push */
37.void push(STACK_TYPE value)
38.{
39. assert(!is_full());
40. top_element += 1;
41. stack[top_element] = value;
42.}
43.
44./* pop */
45.void pop(void)
46.{
47. assert(!is_empty());
48. top_element -= 1;
49.}
50.
51./* top */
52.STACK_TYPE top(void)
53.{
54. assert(!is_empty());
55. return stack[top_element];
56.}
57.
58./* is_empty */
59.int is_empty(void)
60.{
61. assert(stack_size > 0);
62. return top_element == -1;
63.}
64.
65./* is_full */
66.int is_full(void)
67.{
68. assert(stack_size > 0);
69. return top_element == stack_size - 1;
70.}
4.3 鏈式結構
由于只有堆疊頂部元素才可以被訪問，因此適用單鏈表可以很好實作鏈式堆疊，而且無長度限制，把一個元素壓入堆疊是通過在鏈表頭部添加一個元素實作，彈出一個元素是通過洗掉鏈表頭部第一個元素實作，由于沒有長度限制，故不需要create_stack函式，需要destroy_stack進行釋放記憶體以避免記憶體泄漏，
l_stack.c 源代碼如下：
1./*
2.** 單鏈表實作堆疊，沒有長度限制
3.*/
4.#include"stack.h"
5.#include<stdio.h>
6.#include<malloc.h>
7.#include<assert.h>
8.
9.#define FALSE 0
10.
11./*
12.** 定義一個結構以存盤堆疊元素，
13.*/
14.typedef struct STACK_NODE
15.{
16. STACK_TYPE value;
17. struct STACK_NODE *next;
18.} StackNode;
19.
20./* 指向堆疊中第一個節點的指標 */
21.static StackNode *stack;
22.
23./* create_stack */
24.void create_stack(size_t size)
25.{}
26.
27./* destroy_stack */
28.void destroy_stack(void)
29.{
30. while(!is_empty())
31. pop(); /* 逐個彈出元素，逐個釋放節點記憶體 */
32.}
33.
34./* push */
35.void push(STACK_TYPE value)
36.{
37. StackNode *new_node;
38. new_node = (StackNode *)malloc(sizeof(StackNode));
39. if(new_node == NULL)
40. perror("malloc fail");
41. new_node->value = value;
42. new_node->next = stack; /* 新元素插入鏈表頭部 */
43. stack = new_node; /* stack 重新指向鏈表頭部 */
44.}
45.
46./* pop */
47.void pop(void)
48.{
49. StackNode *first_node;
50.
51. assert(!is_empty());
52. first_node = stack;
53. stack = first_node->next;
54. free(first_node);
55.}
56.
57./* top */
58.STACK_TYPE top(void)
59.{
60. assert(!is_empty());
61. return stack->value;
62.}
63.
64./* is_empty */
65.int is_empty(void)
66.{
67. return stack == NULL;
68.}
69.
70./* is_full */
71.int is_full(void)
72.{
73. return FALSE;
74.}
至此，嵌入式里堆疊原理及其純C實作痞子衡便介紹完畢了，掌聲在哪里~~~
歡迎訂閱
文章會同時發布到我的 博客園主頁、CSDN主頁、微信公眾號 平臺上，
微信搜索"痞子衡嵌入式"或者掃描下面二維碼，就可以在手機上第一時間看了哦，
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/17250.html
標籤：嵌入式