痞子衡嵌入式：嵌入式里堆棧原理及其純C實現

来源:https://www.cnblogs.com/henjay724/archive/2020/02/05/12264729.html
-Advertisement-
Play Games

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


　　大家好，我是痞子衡，是正經搞技術的痞子。今天痞子衡給大家講的是嵌入式里堆棧原理及其純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主頁、微信公眾號 平臺上。

微信搜索"痞子衡嵌入式"或者掃描下麵二維碼，就可以在手機上第一時間看了哦。


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • Dart語言學習(十) Dart流程式控制制語句
    一、條件語句:if、if...elseif、if...elseif...else int score = 95; if (score >=90) { print('優秀'); } else if (80>=score && score<90) { print('良'); } else if (60> ...
  • abp(net core)+easyui+efcore實現倉儲管理系統——ABP WebAPI與EasyUI結合增刪改查之十(三十六)
    在上面文章abp(net core)+easyui+efcore實現倉儲管理系統——ABP WebAPI與EasyUI結合增刪改查之九(三十五) 的學習之後，我們已經實現了在控制器中實現查詢功能，今天我們來通過ABP自動幫助我們生成的WebAPI介面，來實現查詢功能。 ...
  • 【WPF學習】第二十六章 Application類——應用程式的生命周期
    在WPF中，應用程式會經歷簡單的生命周期。在應用程式啟動後，將立即創建應用程式對象，在應用程式運行時觸發各種應用程式事件，你可以選擇監視其中的某些事件。最後，當釋放應用程式對象時，應用程式將結束。 一、創建Application對象 使用Application類的最簡單方式是手動創建它。下麵的示例演 ...
  • 優秀 .NET 開源項目集錦
    .NET Core框架、庫和軟體的中文收錄大全。內容包括：庫、工具、框架、模板引擎、身份認證、資料庫、ORM框架、圖片處理、文本處理、機器學習、日誌、代碼分析、教程等。 這裡記錄的大部分可以鏈接到github上，Nuget上也有對應的包，這裡只記錄比較牛的項目。 ...
  • 《果殼中的C# C# 5.0 權威指南》 - 學習筆記
    《果殼中的C# C# 5.0 權威指南》 [作者] (美) Joseph Albahari (美) Ben Albahari[譯者] (中) 陳昇 管學理 曾少寧 楊慶川[出版] 中國水利水電出版社[版次] 2013年08月 第1版[印次] 2013年08月 第1次 印刷[定價] 118.00元 【 ...
  • Caliburn.Micro框架之Bindings
    新建一個WPF項目，將其命名為Caliburn.Micro.BindingsDemo 其次安裝Caliburn.Micro，安裝Caliburn.Micro的同時也會安裝Caliburn.Micro.Core 然後新建Views文件夾和ViewsModels文件夾，前者是放視圖的，後者是放管理視圖的 ...
  • 0x01 C語言-編寫第一個hello world
    學習每一個編程語言都是從 "Hello world!" 開始的，這好像就是編程界一條不成文的規定一樣。 在這篇文章中，我將教大家編寫一個可以輸出 "Hello world!" 的程式。 示常式序：1 #include <stdio.h>//Include a header 1 #include <s ...
  • 痞子衡嵌入式：ARM Cortex-M內核那些事（6）- 系統堆棧機制
    前面痞子衡講過嵌入式里的堆棧原理，本篇算是堆棧原理的工程實踐，更具體點說是在ARM Cortex-M上的應用。ARM Cortex-M家族發展至今已經很多代，我們且以最簡單的Cortex-M0為例來講述堆棧機制 ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發（一）：使用.NET MAUI開發第一個安卓APP
    移動開發（一）：使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說，近來想嘗試開發一款安卓APP，考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP，畢竟是使用Visual Studio開發工具，使用起來也比較的順手，結合微軟官方的教程進行了安卓 ...
  • wpf ToggleButton選中效果和一個登錄界面
    前言 QuestPDF 是一個開源 .NET 庫，用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫，它徹底改變了我們生成 PDF 文檔的方 ...
  • 彈幕樹洞項目功能新增篇
    項目地址 項目後端地址： https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址： ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址： http://tree ...
  • 第27篇 sqlserver2022詳細安裝步驟
    話不多說，直接開乾 一.下載 1.官方鏈接下載： https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe，運行開始下載SQL server； 二. ...
  • .NET 開源高性能 MQTT 類庫
    前言 隨著物聯網（IoT）技術的迅猛發展，MQTT（消息隊列遙測傳輸）協議憑藉其輕量級和高效性，已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫，為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog文檔翻譯系列（六） - 可用的接收器、增強器、格式化輸出
    Serilog支持多種接收器用於日誌存儲，增強器用於添加屬性，LogContext管理動態屬性，支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項，適用於不同需求。 ...
  • 警惕 Visual Studio 屬性求值副作用導致邏輯不符合預期
    目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據，爬取信息時需要模擬瀏覽器行為，否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下： 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • [使用目前最新版]HybridCLR6.9.0+YooAsset2.2.4實現純C# Unity熱更新方案 (一)
    1.前言 什麼是熱更新 游戲或者軟體更新時，無需重新下載客戶端進行安裝，而是在應用程式啟動的情況下，在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR，Xlua，ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles，Addressable， ...
  • 在 ASP.NET Core Web API 中使用操作篩選器統一處理通用操作
    本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺，其實像阿裡雲，騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後，它會送 ...
  • 第28篇 如何.net中實現高效可靠數據同步api
    通過以下方式可以高效，並保證數據同步的可靠性 1.API設計 使用RESTful設計，確保API端點明確，並使用適當的HTTP方法（如POST用於創建，PUT用於更新）。 設計清晰的請求和響應模型，以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類