完善资料让更多小伙伴认识你，还能领取20积分哦， 立即完善>
3天内不再提示
电子发烧友william hill官网
|
|
|
相关推荐
4个回答
|
|
|
何为堆栈？
堆HEAP与栈STACK是两个不同概念，其本质上都是一种数据结构。 栈是一种按数据项排列的数据结构，只能在一端（栈顶top）对数据项进行插入和删除，其符合后进先出（Last-In / First-Out）原则。栈（os）一般是由编译器自动分配释放，其使用的是一级缓存。 堆也是一种分配方式类似于链表的数据结构，其可以在任意位置对数据项进行操作。堆（os）一般由程序员手动分配释放，其使用的是二级缓存。 在嵌入式世界里，堆栈一般指的仅是栈。 |
|
|
|
|
|
作用与意义
在MCU中，栈这种结构一般被cpu和os所使用。 在cpu裸机中使用情况分两种：一、主动进行函数调用时，STACK用以暂存下一条指令地址、函数参数、函数中定义的局部变量；二、硬中断来临时，暂存当前执行的现场数据（下一条指令地址、各种缓存数据），中断结束后，用以恢复。 在os中使用时，硬栈的使用同cpu裸机；但os一般会为每个任务额外分配一个软栈，在任务调度时，可用软中断打断当前正在执行的任务，栈则用以保存各自任务以恢复。 |
|
|
|
|
|
软硬之分
硬件堆栈：是通过寄存器SP作为索引指针的地址，是调用了BL等函数调用指令后硬件自动填充的堆栈。 软件堆栈：是编译器为了处理一些参数传递而做的堆栈，会由编译器自动产生和处理，可以通过相应的编译选项对其进行编辑。 简单一点说，硬件堆栈主要做为地址堆栈用，而软件堆栈主要会被分配成数据堆栈。或看其栈顶指针是否和CPU具有特殊的关联，有关联者（如SP）“硬”，而无关联者“软”。 |
|
|
|
|
|
栈的纯C实现
基本的抽象数据类型（ADT）是编写C程序必要的过程，这类ADT有链表、堆栈、队列和树等，本节主要讲解下堆栈的几种实现方法以及他们的优缺点。 堆栈（stack）的显著特点是后进先出（Last-In First-Out, LIFO），其实现的方法有三种可选方案：静态数组、动态分配的数组、动态分配的链式结构。 静态数组：特点是要求结构的长度固定，而且长度在编译时候就得确定。其优点是结构简单，实现起来方便而不容易出错。而缺点就是不够灵活以及固定长度不容易控制，适用于知道明确长度的场合。 动态数组：特点是长度可以在运行时候才确定以及可以更改原来数组的长度。优点是灵活，缺点是由此会增加程序的复杂性。 链式结构：特点是无长度上线，需要的时候再申请分配内存空间，可最大程度上实现灵活性。缺点是链式结构的链接字段需要消耗一定的内存，在链式结构中访问一个特定元素的效率不如数组。 首先先确定一个堆栈接口的头文件，里面包含了各个方案下的函数原型，放在一起是为了实现程序的模块化以及便于修改。然后再接着分别介绍各个方案的具体实施方法。 堆栈接口stack.h文件代码： 1./* 2.** 堆栈模块的接口 stack.h 3.*/ 4.#include 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.*/ http://44.int is_empty(void); 45. 46./* 47.** 函数原型：is_full 48.** 如果堆栈为满，返回TRUE,否则返回FALSE。 49.*/ http://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 8.#include 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 */ http://41.int is_empty(void) 42.{ 43. return top_element == -1; 44.} 45. 46./* is_full */ http://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 7.#include 8.#include 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 */ http://59.int is_empty(void) 60.{ 61. assert(stack_size > 0); 62. return top_element == -1; 63.} 64. 65./* is_full */ http://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 6.#include 7.#include 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 */ http://65.int is_empty(void) 66.{ 67. return stack == NULL; 68.} 69. 70./* is_full */ http://71.int is_full(void) 72.{ 73. return FALSE; 74.} |
|
|
|
|
只有小组成员才能发言，加入小组>>
810 浏览 0 评论
1161 浏览 1 评论
2535 浏览 5 评论
2871 浏览 9 评论
移植了freeRTOS到STMf103之后显示没有定义的原因？
2719 浏览 6 评论
keil5中manage run-time environment怎么是灰色，不可以操作吗？
1109浏览 3评论
198浏览 2评论
465浏览 2评论
379浏览 2评论
M0518 PWM的电压输出只有2V左右，没有3.3V是怎么回事？
460浏览 1评论
/7 
关注我们的微信
下载发烧友APP
电子发烧友观察
版权所有 © 湖南华秋数字科技有限公司
电子发烧友 （威廉希尔官方网站 图） 湘公网安备 43011202000918 号 电信与信息服务业务经营许可证：合字B2-20210191
工商网监
湘ICP备2023018690号
902
评论
淘帖
1760
