快捷搜索:  as

嵌入式世界里,堆栈的作用和意义

栈这种布局在嵌入式里着实长短经常用的,比如函数调用与返回便是范例的栈利用,虽然很多时刻栈都是 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 源代码如下:

您可能还会对下面的文章感兴趣: