堆栈的概念————————ARM微控制器与嵌入式系统（清华大学慕课记录）
堆栈、堆、栈的概念
- 堆：堆可以被看成是一棵树。堆是在程序运行时，申请某个大小的存储空间。即动态分配内存，对其访问和对一般内存的访问没有区别。
- 堆：栈是一种运算受限的线性表。仅允许在栈的一端进行插入和删除操。这一端称为栈顶，相对的，另一端称为栈底。遵循先入后出的原则。
- 堆栈：堆栈本身就是栈，只是由于现代汉语言喜欢用两个字表示一个事物，因此用了“堆栈”的说法来代替栈。
CPU中为什么要引入堆栈的机制
程序在执行程序时，相对应是PC指针的变化，PC指针永远指向下一条待执行的指令。但是PC指针不是永远都是一条一条逐一递增的，再遇到函数嵌套调用时，函数跳转时（比如遇到 if…else这样的语句时），PC指针会发生跳转。
在发生函数调用的时候，函数调用结束需要使CPU回到原来的位置，也就是使PC指针发生一个跳转，PC指针的跳转也就要给PC指针赋值，给PC指针赋的这个值也就是函数的返回地址。那CPU应该从何处获得这个返回地址呢？早期的CPU设计是设计了一个返回地址寄存器。
返回地址寄存器的作用就是为了存储函数调用时的返回地址，从而使得函数调用结束时，将此寄存器的值赋值给PC指针寄存器，完成函数的返回。但是函数调用可能会嵌套好几层，第一次调用的返回地址要进行存储，第二次调用的返回地址仍然需要进行存储，在使用C语言时，会使用到库函数，在使用库函数的过程当中，就可能发生多层的函数调用，因此会造成返回地址寄存器不够用的情况，因此也就引入了一种更加智能的机制，也就是堆栈（stack）
堆栈的特点及作用
特性
- 堆栈是一段连续的存储空间
- 堆栈按照先入后出的方式进行工作
- 只能向/从堆栈的顶部加入或取出数据
- 堆栈能够保存数据的顺序
补充： 堆栈的存储器是自下向上使用，所谓的“顶部”是数据最后放入的位置
且对于大部分的CPU而言，“顶部”指低位的存储空间
基本操作方式
压栈（PUSH）:将内容加入到堆栈顶端
出栈（POP）: 将堆栈顶端的内容取出
堆栈的三种作用
- C语言编译器使用堆栈来完成参数传递和返回值传递——C语言的函数调用
- 汇编程序可以使用堆栈来保存局部变量，寄存器的值
- CPU硬件使用堆栈来保存返回地址和寄存器上下文
解决函数调用返回地址存储的方法
有了堆栈这样的机制，就能很好地处理函数跳转及函数嵌套调用的问题。
在发生函数嵌套调用的时候，当发生一级函数调用的时候，就把当前的PC指针寄存器的值压入堆栈，当函数调用还没有返回时，又再次发生函数调用时，需要把第二次发生函数调用的当前的PC指针寄存器的值压入堆栈，当第二层函数调用需要返回时，只需要从栈顶取出数据即可，这个值也就是第二次函数调用时的返回地址，将其赋值给PC指针寄存器，就可以完成第二层函数的返回。而发生第一层函数返回时，只需要再次从栈中取出一个值赋值给PC指针寄存器即可，这样就能完成第一层函数的返回。
综上，就是函数调用时的全部过程，完美的运用了堆栈先入后出的机制。
局部变量与堆栈的关系
C语言中函数的参数、返回值的传递是使用栈的，C语言中的局部变量也会根据编译器在栈中占据一定量的存储空间，因此堆栈会依据C语言的使用而逐渐地消耗，局部变量存储在栈中这一点也很好地印证了局部变量有生命周期，因为当函数调用结束，函数返回。局部变量的存储空间将逐一释放，逐一弹出，不再继续使用，局部变量的值也就被释放了。
堆栈溢出
堆栈的位置
上述描述了堆栈的作用，那堆栈又在哪里呢？对于CPU来讲，CPU采用一段连续的片外存储空间来充当堆栈，而CPU又如何找到这段存储空间呢？这里引入了堆栈指针寄存器的概念，堆栈指针寄存器指定栈顶位置，也就是片外存储器用于堆栈这一段存储空间的栈顶。
堆栈溢出的原理
在介绍堆栈溢出原理之前先指出一点，堆，全局变量的存储位置就是在堆上。
而堆栈存储空间和变量空间（堆）是使用同一端存储器空间，针对于堆栈存储空间和变量空间分别具有以下特性：
- 变量空间从低地址向高地址划分（C语言编程时使用的全局变量）
-
堆栈空间从高地址向低地址增长
下图是变量空间和堆栈空间在存储器上的示意图
因此在程序运行的时候，伴随着各种函数的调用，因此堆栈空间是处于一个上下涨落的状态，堆也在上面使用内存，考虑极限情况，当全局变量定义的过多，函数嵌套的过深，可能出现的情况就是堆空间和堆栈空间产生了交集，从而导致PC指针从堆栈中取了一个值作为返回地址，但取到的值却不是返回地址，而是一个全局变量，从而造成程序跑飞。这也就是堆栈溢出的原理。