数据结构
栈就像装数据的桶或箱子它是一种具有后进先出性质的数据结构，也就是说后存放的先取，先存放的后取。
这就如同我们要取出放在箱子里面底下的东西（放入的比较早的物体），我们首先要移开压在它上面的物体（放入的比较晚的物体）。
使用数组的形式来实现栈，这种栈也称为静态栈；使用链表的形式来实现栈，这种栈也称为动态栈。
堆像一棵倒过来的树 ，堆是一种经过排序的树形数据结构，每个结点都有一个值。
通常我们所说的堆的数据结构，是指二叉堆。堆是一种特殊的完全二叉树。
堆的特点是根结点的值最小（或最大），且根结点的两个子树也是一个堆。由于堆的这个特性，常用来实现优先队列，堆的存取是随意，无序的。这就如同我们在图书馆的书架上取书，虽然书的摆放是有顺序的，但是我们想取任意一本时不必像栈一样，先取出前面所有的书，可以直接取出想要的书。
堆栈空间分配
栈：由操作系统自动分配释放 ，存放函数的参数值，局部变量的值等。其操作方式类似于数据结构中的栈先进后出。
堆： 一般由程序员分配释放， 若程序员不释放，程序结束时可能由系统回收，分配方式倒是类似于链表。
可执行程序包括BSS段、data段、text段（也称文本段）。
BSS（Block Started by Symbol）通常是指用来存放程序中未初始化的全局变量和静态变量的一块内存区域。特点是:可读写的，在程序执行之前BSS段会自动清0。所以，未初始的全局变量在程序执行之前已经成0了。
注意和data段的区别，BSS存放的是未初始化的全局变量和静态变量，data数据段存放的是初始化后的全局变量和静态变量。data段的数据会加载进入可执行文件中，bss段数据不会对可执行文件的大小有影响，但是会有一些占位符操作，需要知道运行时bss数据需要的内存大小。
文字常量区 ： 常量字符串"abcd" 就是放在这里的，一般存在rodata段，处于data段和text段中间的一个区域里。程序结束后由系统释放
程序代码区(text) : 存放程序的二进制代码。
堆&栈的区别
1：堆栈缓存方式
栈使用的是一级缓存， 通常被调用时处于运行内存，调用完毕立即释放。
堆则是存放在二级缓存中，生命周期由系统来决定（引用计数为0 就会触发回收）。所以调用这些对象的速度要相对来得低一些。
2：申请方式和回收方式
栈内存是由编译器自动完成的，如局部变量的分配（即在一个函数中声明一个 int 类型的变量i时，编译器就会自动开辟一块内存以存放变量 i）。与此同时，其生存周期也只在函数的运行过程中，在运行后就释放，并不可以再次访问。
堆内存是由程序员手动申请与释放的，程序在运行的时候由程序员使用内存分配函数（如 malloc 函数）来申请任意多少的内存，使用完再由程序员自己负责使用内存释放函数（如 free 函数）释放内存
3：申请后效率
栈：只要栈的剩余空间大于所申请空间，系统将为程序提供内存，否则将报异常提示栈溢出。栈内存分配运算内置于处理器的（指令集）中，系统自动分配速度更快。栈中的空闲内存都是连续的，因此不需要维护空闲内存块。只是一个简单的指向当前栈顶（栈的高地址）的指针sp。
堆：操作系统有一个记录空闲内存地址的链表，当系统收到程序的内存分配申请时，会遍历该链表，寻找第一个空间大于所申请空间的堆结点，然后将该结点从空闲结点链表中删除，并将该结点的空间分配给程序，大多数系统，会在这块内存空间块的首地址处记录本次分配的大小，这样，代码中的 delete语句才能正确的释放本内存空间。另外，由于找到的堆结点的大小不一定正好等于申请的大小，系统会自动的将多余的那部分重新放入空闲链表中。由于频繁分配和释放（malloc / free）不同大小的堆空间势必会造成内存空间的不连续，从而造成大量碎片，导致程序效率降低。
5：申请大小的限制
栈：栈是向低地址扩展的数据结构，其地址的增长方向是向下进行的，向内存地址减小的方向增长。是一块连续的内存的区域。这句话的意思是栈顶的地址和栈的最大容量是系统预先规定好的，是一个编译时就确定的常数。如果申请的空间超过栈的剩余空间时，将提示overflow。能从栈获得的空间有限。
堆：堆是向高地址扩展的数据结构，是不连续的内存区域。是用链表来存储空闲内存地址的，链表的遍历方向是由低地址向高地址进行的。堆的大小受限于计算机系统中有效的虚拟内存，堆获得的空间比较灵活，也比较大。
6：堆和栈中的存储内容
栈： 在函数调用时，第一个进栈的是主函数中函数调用后的下一条指令（函数调用语句的下一条可执行语句）的地址（返回地址），然后是函数的各个参数，然后是函数中的局部变量。注意静态变量是不入栈的。
当本次函数调用结束后，局部变量先出栈，然后是参数，最后栈顶指针指向最开始存的返回地址，也就是主函数中的下一条指令，程序由该点返回到主函数继续往下执行。
堆：一般是在堆的头部用一个字节存放堆的大小。
C 语言中，内存分配方式有三种形式：
从静态存储区域分配：它是由编译器自动分配和释放的，程序编译的时候就已经分配好，这块内存在程序的整个运行期间都存在，直到整个程序运行结束时才被释放，如全局变量与 static 变量。
在栈上分配：它同样也是由编译器自动分配和释放的，即在执行函数时，函数内局部变量的存储单元都可以在栈上创建，函数执行结束时这些存储单元将被自动释放。栈有两种分配方式：静态分配和动态分配。
静态分配是由编译器自动完成的，如局部变量的分配（即在一个函数中声明一个 int 类型的变量i时，编译器就会自动开辟一块内存以存放变量 i）。与此同时，其生存周期也只在函数的运行过程中，在运行后就释放，并不可以再次访问。
动态分配由 alloca 函数进行分配，由编译器进行释放，无需任何手工实现。
堆上分配：也称动态内存分配，它是由程序员手动完成申请和释放的。即程序在运行的时候由程序员使用内存分配函数（如 malloc 函数）来申请任意多少的内存，使用完之后再由程序员自己负责使用内存释放函数（如 free 函数）来释放内存。也就是说，动态内存的整个生存期是由程序员自己决定的，使用非常灵活。需要注意的是，如果在堆上分配了内存空间，就必须及时释放它，否则将会导致运行的程序出现内存泄漏等错误。
C 语言中各类型变量的存储位置和作用域。
全局变量：从静态存储区域分配，其作用域是全局作用域，也就是整个程序的生命周期内都可以使用。与此同时，如果程序是由多个源文件构成的，那么全局变量只要在一个文件中定义，就可以在其他所有的文件中使用，但必须在其他文件中通过使用extern关键字来声明该全局变量。
全局静态变量：从静态存储区域分配，其生命周期也是与整个程序同在的，从程序开始到结束一直起作用。但是与全局变量不同的是，全局静态变量作用域只在定义它的一个源文件内，其他源文件不能使用。
局部变量: 从栈上分配，其作用域只是在局部函数内，在定义该变量的函数内，只要出了该函数，该局部变量就不再起作用，该变量的生命周期也只是和该函数同在。
局部静态变量: 从静态存储区域分配，其在第一次初始化后就一直存在直到程序结束，该变量的特点是其作用域只在定义它的函数内可见，出了该函数就不可见了,只是延长了变量的生命周期，作用域不变。
相关知识延伸：
在多线程环境下每一个线程都可以有他自己完全的独立的栈，但是他们共享堆。并行存取被堆控制而不是栈。
堆的管理依赖于运行时环境，C 使用 malloc ，C++ 使用 new ，但是很多语言有垃圾回收机制。
栈是更低层次的特性与处理器架构紧密的结合到一起。当堆不够时可以扩展空间，这不难做到，因为可以有库函数可以调用。但是，扩展栈通常来说是不可能的，因为在栈溢出的时候，执行线程就被操作系统关闭了，这已经太晚了。
堆包含一个链表来维护已用和空闲的内存块。在堆上分配（用 new 或者 malloc）内存是从空闲的内存块中找到满足要求的内存块。这个操作会更新堆中的块链表。
堆碎片 ： 申请和释放许多小的内存块可能会产生：在已用块之间存在很多小的空闲块。进而申请大块内存失败，虽然空闲块的总和足够，但是空闲的小块是零散的，不能满足申请的大小。当旁边有空闲块的已用块被释放时，新的空闲块可能会与相邻的空闲块合并为一个大的空闲块，这样可以有效的减少“堆碎片”的产生。
CPU 用 push 指令来将数据压栈，用 pop 指令来弹栈。当用 push 压栈时，sp 值减少（向低地址扩展）。当用 pop 弹栈时，sp 值增大。
当函数被调用时，CPU使用特定的指令把当前的 IP （“instruction pointer”，是一个寄存器，用来记录 CPU 指令的位置）压栈。CPU 接下来将调用函数地址赋给 IP ，进行调用。当函数返回时，旧的 IP 被弹栈，CPU 继续往下执行。当进入函数时，栈中sp指针 向下扩展（向低地址扩展），扩展到确保为函数的局部变量留足够大小的空间。如果函数中有一个 32-bit 的局部变量会在栈中留够四字节的空间。当函数返回时，sp 通过返回原来的位置来释放空间。
栈是为执行线程留出的内存空间。栈受到内存块的限制，不断的函数嵌套或者为局部变量分配太多的空间，可能会导致栈溢出。当栈中的内存区域都已经被用完之后继续向下写（低地址），会触发一个 CPU 异常。栈溢出错误。可以把这个占用太多内存的局部变量用static 关键字修饰这样局部变量变成静态局部变量，存储方式从栈上改到全局变量区数据段上减少对栈内存的占用。
内存通常由操作系统分配，通过应用程序调用 API 接口去实现分配。在管理动态分配内存上会有一些额外的开销，不过这由操作系统来处理。计算机程序通常有一个栈叫做调用栈，用来存储当前函数调用相关的信息（比如：主调函数的地址，局部变量），因为函数调用之后需要返回给主调函数。
堆是在内存中动态和随机分配的，是无序的。
堆（heap）是为动态分配预留的内存空间。从堆上分配和释放内存没有固定模式；你可以在任何时候分配和释放它。这样使得跟踪哪部分堆已经被分配和被释放变的异常复杂；
1. 当线程创建的时候，操作系统（OS）为每一个系统级（system-level）的线程分配栈。通常情况下，操作系统通过调用语言的运行时（runtime）去为应用程序分配堆。
2. 栈附属于线程，因此当线程结束时栈被回收。堆通常通过运行时在应用程序启动时被分配，当应用程序（进程）退出时被回收。
3. 当线程被创建的时候，设置栈的大小。在应用程序启动的时候，设置堆的大小，但是堆可以在需要的时候扩展（分配器向操作系统申请更多的内存）。
4. 栈比堆要快，在栈上的每个字节频繁的被复用也就意味着它可能映射到处理器缓存中，所以很快（局部性原理）。
1.对栈而言，数据是有序的，先进后出，后进先出，不能越位。
2.对堆而言，数据是随机无序的。可以任何顺序插入和删除。
参考地址：
