简述堆和栈的区别

预备知识—程序的内存分配

一个由C/C 编译的程序占用的内存分为以下几个部分：
1、栈区（stack）—> 由编译器自动分配释放 ，存放函数的参数值，局部变量的值等。其操作方式类似于数据结构中的栈。
2、堆区（heap） —> 一般由程序员分配释放， 若程序员不释放，程序结束时可能由OS回收。注意它与数据结构中的堆是两回事，分配方式倒是类似于链表。
3、全局区（静态区）（static）—> 全局变量和静态变量的存储是放在一块的，初始化的全局变量和静态变量在一块区域，未初始化的全局变量和未初始化的静态变量在相邻的另一块区域。 程序结束后由系统释放。
4、文字常量区 —> 常量字符串就是放在这里的。程序结束后由系统释放
5、程序代码区 —> 存放函数体的二进制代码。

堆栈的区别

1、内存管理范围

• 只有oc对象需要进行内存管理。
• 非oc对象类型比如基本数据类型不需要进行内存管理。

2、内存管理本质
因为Objective-C的对象在内存中是以堆的方式分配空间的,并且堆内存是由你释放的，就是release。
OC对象存放于堆里面(堆内存要程序员手动回收)
非OC对象一般放在栈里面(栈内存会被系统自动回收)
堆里面的内存是动态分配的，所以也就需要程序员手动的去添加内存、回收内存。

3、内存分配以及管理方式

按分配方式分：

• 堆是动态分配和回收内存的，没有静态分配的堆。
• 栈有两种分配方式：静态分配和动态分配。
• 静态分配是系统编译器完成的，比如局部变量的分配。
• 动态分配是有alloc函数进行分配的，但是栈的动态分配和堆是不同的，它的动态分配也由系统编译器进行释放，不需要程序员手动管理。

按管理方式分：

• 对于栈来讲，是由系统编译器自动管理，不需要程序员手动管理。
• 对于堆来讲，释放工作由程序员手动管理，不及时回收容易产生内存泄露。

4、申请大小的限制
栈：栈是向低地址扩展的数据结构，是一块连续的内存的区域。是栈顶的地址和栈的最大容量是系统预先规定好的，栈的大小是2M（也有的说是1M，总之是一个编译时就确定的常数 ) ,如果申请的空间超过栈的剩余空间时，将提示overflow。因此，能从栈获得的空间较小。

堆：堆是向高地址扩展的数据结构，是不连续的内存区域。这是由于系统是用链表来存储的空闲内存地址的，自然是不连续的，而链表的遍历方向是由低地址向高地址。堆的大小受限于计算机系统中有效的虚拟内存。由此可见，堆获得的空间比较灵活，也比较大。

5、碎片问题
栈：由系统自动分配，速度较快，不会产生内存碎片。
堆：是由alloc分配的内存，速度比较慢，而且容易产生内存碎片，不过用起来最方便。
对于堆来讲,频繁的new/delete势必会造成内存空间的不连续,从而造成大量的碎片,使程序效率降低。对于栈来讲,则不会存在这个问题,因为栈是先进后出的队列,它们是如此的一一对应,以至于永远都不可能有一个内存块从栈中间弹出。

6、分配效率
栈是机器系统提供的数据结构,计算机会在底层对栈提供支持:分配专门的寄存器存放栈的地址,压栈出栈都有专门的指令执行,这就决定了栈的效率比较高。堆则是C/C++函数库提供的,它的机制是很复杂的。

7、优缺点
栈对象：
优点：
1.高速，在栈上分配内存是非常快的。
2.简单，栈对象有自己的生命周期，你永远不可能发生内存泄露。因为他总是在超出他的作用域时被自动销毁了。
缺点：栈对象严格的定义了生命周期也是其主要的缺点,栈对象的生命周期不适于Objective-C的引用计数内存管理方法。

在objective-c中只支持一个类型对象：blocks。
关于在block中的对象的生命周期问题。出现这问题的原因是，block是新的对象，当你使用block时候，如果你想对其保持引用，你需要对其进行copy操作，（从栈上copy到堆中，并返回一个指向他的指针），而不是对其进行retain操作。

堆对象：
优点：可以自己控制对象的生命周期。
缺点：需要程序员手动释放，容易造成内存泄漏。

8、堆和栈中的存储内容
栈： 在函数调用时，第一个进栈的是主函数中后的下一条指令（函数调用语句的下一条可执行语句）的地址，然后是函数的各个参数，在大多数的C编译器中，参数是由右往左入栈的，然后是函数中的局部变量。注意静态变量是不入栈的。 当本次函数调用结束后，局部变量先出栈，然后是参数，最后栈顶指针指向最开始存的地址，也就是主函数中的下一条指令，程序由该点继续运行。
堆：一般是在堆的头部用一个字节存放堆的大小。堆中的具体内容有程序员安排。

在数据结构中

注意：
在我们学习《数据结构》时，接触到的堆和栈的概念和这个操作系统中的堆和栈不是一回事的。
操作系统的堆和栈是指对内存进行操作和管理的一些方式。
《数据结构》的堆实际上指的就是（满足堆性质的）优先Queue 的一种数据结构，第1 个元素有最高的优先权；栈实际上就是满足后进先出的性质的数据或数据结构。

《数据结构》中讲到的堆栈，通俗上的堆栈的理解，堆和栈是数据存储方式的两种数据结构。关于堆栈，其实还有一个比较容易搞混的地方那就是队列，其实这三种都是数据结构中的一种排序数据结构。

• 堆：堆的数据机构其实就是一个完全二叉树，具堆属性的数据结构才可被叫做为堆，堆常见的应用就是堆排序与实现优先队列，因为堆的存取是随意。
• 队列：是一种采用先进先出(FIFO)策略的抽象数据结构，它的想法来自于生活中排队的策略。顾客在付款结账的时候，按照到来的先后顺序排队结账，先来的顾客先结账，后来的顾客后结账。一般与栈作比较 。
  不过同栈的实现一样，队列的实现也有数组实现和链表实现两种方式。
• 栈：与队列相反，栈的顺序是后进先出，只可以在栈顶进行操作，类似与只有一个出入口的公交车，先上车的只能后来下车 。
  速度 比较：
  队列与栈速度相对来说，队列的更快些，因为设计增加删除的操作时，队列不需要改变数据结构，而栈需要，所以遍历速度略低些，这些数据结构一般跟算法有点关系。

堆

• 堆是一种基于树的满足某些特性的数据结构：整个堆中的所有父子节点的键值都满足相同的排序条件。堆分为最大堆和最小堆。在最大堆中，父节点的键值永远大于等于所有子节点的键值，根节点的键值是最大的。最小堆中，父节点的键值永远小于等于所有子节点的键值，根节点的键值是最小的。
• 时间复杂度
  • 索引：O(log(n))
  • 查找：O(log(n))
  • 插入：O(log(n))
  • 删除：O(log(n))
  • 删除最大值/最小值：O(1)

栈

• 栈的定义：
  栈是限定仅在表尾进行插入和删除操作的线性表。
  我们把插入和删除的一端称为栈顶（TOP），另一端称为栈底（BOTTOM）,不包含任何元素的栈称为空栈。栈又称为后进先出（Last in first out）的线性表，简称LIFO结构。

• 栈也是一个元素集合，支持两个基本操作：push用于将元素压入栈，pop用于删除栈顶元素。

• 后进先出的数据结构（Last In First Out, LIFO）

• 栈的存储结构
  由于栈也是线性表，因此线性表的存储结构对栈也使用，通常有顺序栈和链栈两种存储结构，这两种存储结构的不同，即使得实现栈的基本运算的算法也有所不同。
  （1）顺序存储结构
  其实栈的顺序存储还是挺方便的，因为他只准栈顶进出元素，所以不存在线性表插入和删除时需要移动元素的问题。不过它有一个很大的缺陷，就是必须事先确定数组存储空间大小，玩意不够用了，就需要编程手段来扩展数组的容量，非常麻烦，
  （2）链式存储结构
  如果栈的使用过程中元素变化不可预测，有时很小，有时非常大，那么最好是用链栈【存储空间不固定可伸缩】。

• 时间复杂度

  • 索引：O(n)
  • 查找：O(n)
  • 插入：O(1)
  • 删除：O(1)

队列

• 队列的定义：
  队列(queue)是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。
  队列是一种先进先出(First In First Out)的线性表，简称FIFO。允许插入的一端称为队尾（rear），允许删除的一端称为队头(Front)。
  队列是一种运算受限的线性表，它的运算限制与栈不同，是两头都有限制，插入只能在表的一端进行(只进不出)，而删除只能在表的另一端进行(只出不进)。

• 先进先出的数据结构（First In First Out, FIFO）

• 队列的类型：链式队列，即用链表实现的队列。静态队列：即用数组实现的队列。

• 队列的存储结构
  队列也是线性表，所以有两种存储方式，顺序存储和链式存储。
  （1）顺序存储结构（顺序队列）
  缺点，存储空间不够用的时候需要开发人员通过编程手段来扩展数组容量。
  衍生循环队列：头尾相接的顺序存储结构成为循环队列。
  （2）链式存储结构（链队）
  队列的链式存储结构，其实也就是线性表的单链表，只不过它只能尾进头出而已，我们把它简称为链队列。

总结：
栈（stack）是限定在表尾进行插入和删除操作的线性表。
队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。
它们均可使用线性表的顺序存储结构来实现，但都存在着顺序存储的一些弊端（空间不够用）。
同时它们各自有各级的技巧来解决以上这个问题：
对于栈来说，如果是两个相同数据类型的栈，则可以用数组的两端作为栈底的方法来让两个栈共享数据，这就可以最大化地利用数组的空间。
对于队列来说，为了避免数组插入和删除时需要移动数据，于是就引入了循环队列，使得队头和队尾可以在数组中循环变化。解决了移动数据的时间损耗。
他们也都可以通过链式存储结构来实现，实现原则上与线性表基本相同。