|
大家好，我是痞子衡,，是正經(jīng)搞技術(shù)的痞子,。今天痞子衡給大家講的是嵌入式里堆棧原理及其純C實(shí)現(xiàn),。 今天給大家分享的這篇還是2016年之前痞子衡寫的技術(shù)文檔，花了點(diǎn)時(shí)間重新編排了一下格式,。棧這種結(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）對數(shù)據(jù)項(xiàng)進(jìn)行插入和刪除，其符合后進(jìn)先出（Last-In / First-Out）原則,。棧（os）一般是由編譯器自動(dòng)分配釋放,，其使用的是一級緩存。
堆也是一種分配方式類似于鏈表的數(shù)據(jù)結(jié)構(gòu),，其可以在任意位置對數(shù)據(jù)項(xiàng)進(jìn)行操作,。堆（os）一般由程序員手動(dòng)分配釋放，其使用的是二級緩存,。
在嵌入式世界里,，堆棧一般指的僅是棧。 2.作用與意義 在MCU中,，棧這種結(jié)構(gòu)一般被cpu和os所使用。
在cpu裸機(jī)中使用情況分兩種：一,、主動(dòng)進(jìn)行函數(shù)調(diào)用時(shí),，STACK用以暫存下一條指令地址、函數(shù)參數(shù),、函數(shù)中定義的局部變量,；二、硬中斷來臨時(shí),，暫存當(dāng)前執(zhí)行的現(xiàn)場數(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.軟硬之分 硬件堆棧：是通過寄存器SP作為索引指針的地址,，是調(diào)用了BL等函數(shù)調(diào)用指令后硬件自動(dòng)填充的堆棧。
軟件堆棧：是編譯器為了處理一些參數(shù)傳遞而做的堆棧,，會(huì)由編譯器自動(dòng)產(chǎn)生和處理,，可以通過相應(yīng)的編譯選項(xiàng)對其進(jìn)行編輯。
簡單一點(diǎn)說,，硬件堆棧主要做為地址堆棧用,，而軟件堆棧主要會(huì)被分配成數(shù)據(jù)堆棧?；蚩雌錀ｍ斨羔樖欠窈虲PU具有特殊的關(guān)聯(lián),，有關(guān)聯(lián)者（如SP）“硬”，而無關(guān)聯(lián)者“軟”,。 4.棧的純C實(shí)現(xiàn) 基本的抽象數(shù)據(jù)類型（ADT）是編寫C程序必要的過程,，這類ADT有鏈表、堆棧,、隊(duì)列和樹等,，本節(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)的長度固定,，而且長度在編譯時(shí)候就得確定。其優(yōu)點(diǎn)是結(jié)構(gòu)簡單,，實(shí)現(xiàn)起來方便而不容易出錯(cuò),。而缺點(diǎn)就是不夠靈活以及固定長度不容易控制，適用于知道明確長度的場合,。
動(dòng)態(tài)數(shù)組：特點(diǎn)是長度可以在運(yùn)行時(shí)候才確定以及可以更改原來數(shù)組的長度,。優(yōu)點(diǎn)是靈活，缺點(diǎn)是由此會(huì)增加程序的復(fù)雜性,。
鏈?zhǔn)浇Y(jié)構(gòu)：特點(diǎn)是無長度上線,，需要的時(shí)候再申請分配內(nèi)存空間，可最大程度上實(shí)現(xiàn)靈活性,。缺點(diǎn)是鏈?zhǔn)浇Y(jié)構(gòu)的鏈接字段需要消耗一定的內(nèi)存,，在鏈?zhǔn)浇Y(jié)構(gòu)中訪問一個(gè)特定元素的效率不如數(shù)組。
首先先確定一個(gè)堆棧接口的頭文件，里面包含了各個(gè)方案下的函數(shù)原型,，放在一起是為了實(shí)現(xiàn)程序的模塊化以及便于修改,。然后再接著分別介紹各個(gè)方案的具體實(shí)施方法。
堆棧接口stack.h文件代碼： 1./*
2.** 堆棧模塊的接口 stack.h
3.*/
4.#include<stdlib.h>
5.
6.#define STACK_TYPE int /* 堆棧所存儲(chǔ)的值的數(shù)據(jù)類型 */
7.
8./*
9.** 函數(shù)原型：create_stack
10.** 創(chuàng)建堆棧,，參數(shù)指定堆?？梢员４娑嗌賯€(gè)元素。
11.** 注意：此函數(shù)只適用于動(dòng)態(tài)分配數(shù)組形式的堆棧,。
12.*/
13.void create_stack(size_t size);
14.
15./*
16.** 函數(shù)原型：destroy_stack
17.** 銷毀一個(gè)堆棧,，釋放堆棧所適用的內(nèi)存。
18.** 注意：此函數(shù)只適用于動(dòng)態(tài)分配數(shù)組和鏈?zhǔn)浇Y(jié)構(gòu)的堆棧,。
19.*/
20.void destroy_stack(void);
21.
22./*
23.** 函數(shù)原型：push
24.** 將一個(gè)新值壓入堆棧中,，參數(shù)是被壓入的值。
25.*/
26.void push(STACK_TYPE value);
27.
28./*
29.** 函數(shù)原型：pop
30.** 彈出堆棧中棧頂?shù)囊粋€(gè)值,，并丟棄,。
31.*/
32.void pop(void);
33.
34./*
35.** 函數(shù)原型：top
36.** 返回堆棧頂部元素的值，但不改變堆棧結(jié)構(gòu),。
37.*/
38.STACK_TYPE top(void);
39.
40./*
41.** 函數(shù)原型：is_empty
42.** 如果堆棧為空,，返回TRUE,否則返回FALSE。
43.*/
44.int is_empty(void);
45.
46./*
47.** 函數(shù)原型：is_full
48.** 如果堆棧為滿,，返回TRUE,否則返回FALSE,。
49.*/
50.int is_full(void);
4.1 靜態(tài)數(shù)組 在靜態(tài)數(shù)組堆棧中，STACK_SIZE表示堆棧所能存儲(chǔ)的元素的最大值,，用top_element作為數(shù)組下標(biāo)來表示堆棧里面的元素,，當(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 源代碼如下： 1./*
2.**
3.** 靜態(tài)數(shù)組實(shí)現(xiàn)堆棧程序 a_stack.c ,，數(shù)組長度由#define確定
4.*/
5.
6.#include'stack.h'
7.#include<assert.h>
8.#include<stdio.h>
9.
10.#define STACK_SIZE 100 /* 堆棧最大容納元素?cái)?shù)量 */
11.
12./*
13.** 存儲(chǔ)堆棧中的數(shù)組和一個(gè)指向堆棧頂部元素的指針
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 動(dòng)態(tài)數(shù)組 頭文件還是用stack.h，改動(dòng)的并不是很多,，增加了stack_size變量取代STACK_SIZE來保存堆棧的長度，數(shù)組由一個(gè)指針來代替,，在全局變量下缺省為0,。
create_stack函數(shù)首先檢查堆棧是否已經(jīng)創(chuàng)建，然后才分配所需數(shù)量的內(nèi)存并檢查分配是否成功,。destroy_stack函數(shù)首先檢查堆棧是否存在,，已經(jīng)釋放內(nèi)存之后把長度和指針變量重新設(shè)置為零。is_empty 和 is_full 函數(shù)中添加了一條斷言，防止任何堆棧函數(shù)在堆棧被創(chuàng)建之前就被調(diào)用,。
d_stack.c源代碼如下： 1./*
2.** 動(dòng)態(tài)分配數(shù)組實(shí)現(xiàn)的堆棧程序 d_stack.c
3.** 堆棧的長度在創(chuàng)建堆棧的函數(shù)被調(diào)用時(shí)候給出,，該函數(shù)必須在任何其他操作堆棧的函數(shù)被調(diào)用之前條用。
4.*/
5.#include'stack.h'
6.#include<stdio.h>
7.#include<malloc.h>
8.#include<assert.h>
9.
10./*
11.** 用于存儲(chǔ)堆棧元素的數(shù)組和指向堆棧頂部元素的指針
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 鏈?zhǔn)浇Y(jié)構(gòu) 由于只有堆棧頂部元素才可以被訪問,，因此適用單鏈表可以很好實(shí)現(xiàn)鏈?zhǔn)蕉褩?，而且無長度限制。把一個(gè)元素壓入堆棧是通過在鏈表頭部添加一個(gè)元素實(shí)現(xiàn),。彈出一個(gè)元素是通過刪除鏈表頭部第一個(gè)元素實(shí)現(xiàn),。由于沒有長度限制，故不需要create_stack函數(shù),，需要destroy_stack進(jìn)行釋放內(nèi)存以避免內(nèi)存泄漏,。
l_stack.c 源代碼如下： 1./*
2.** 單鏈表實(shí)現(xiàn)堆棧，沒有長度限制
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.** 定義一個(gè)結(jié)構(gòu)以存儲(chǔ)堆棧元素,。
13.*/
14.typedef struct STACK_NODE
15.{
16. STACK_TYPE value;
17. struct STACK_NODE *next;
18.} StackNode;
19.
20./* 指向堆棧中第一個(gè)節(jié)點(diǎn)的指針 */
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(); /* 逐個(gè)彈出元素,，逐個(gè)釋放節(jié)點(diǎn)內(nèi)存 */
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實(shí)現(xiàn)痞子衡便介紹完畢了,，掌聲在哪里~~~
|
