概念辨析

严格来说，堆（heap）和栈（stack）是两种数据结构，但：

• 有时候我们也会把栈称之为“堆栈”，比如说“堆栈溢出/堆栈调用”，这时候说的就是“栈”
  
• 有些人会把后面要学的树（tree）当成“堆”
  

ʅ(‾◡◝)ʃ，飞哥也很无奈，同学们就根据上下文理解吧，不用太较真……

PS：致敬https://stackoverflow.com/，此外，源栈的“栈”，知道啥意思了吧？

堆

堆可以有两种理解：

无序的数据集合

简单的说，就是数据散乱的分布，没有任何组织和规律，就像一堆货物堆在那里一样：

演示：堆的形成

• 一开始的时候，内存的使用还是有序的（一个接一个）
• 但随着数据不断的占用/释放/移动，最终形成了一种无序状态：这里一块那里一块的样子
  

同时，产生很多存储碎片：零星的小型的无法/很难被使用的存储空间（无论是内存还是外存都一样）。

如何对付存储碎片？

• 内存：电脑重启
• 外存：windows有磁盘碎片整理

根节点最大/最小

看起来像一颗树，但和树有区别：

1. 必须是平衡二叉树（但不排序）
2. 只需要满足一个要求：父节点比子节点都大
3. 所以不需要指针，可以用数组存储，找到找到任何一个节点的父节点或者子节点（选：参考）

栈

简单的说，是一种“先进后出”的数据结构。用栈来存放数据：

• 最先放进去的数据，要最后才能取出来；
• 最后放进去的数据，才能最先取出来。

装子弹的弹匣就是一种典型的“栈”：

子弹被击发的顺序是和被压入的顺序相颠倒的：最后压入的一颗子弹会被最先击发，而最先压入弹匣的子弹只有等所有上面的子弹打完之后才能被击发。

我们将其进行抽象，就可以得到下面这样的栈的数据结构图：

说明：左图top不移动，右图bottom不移动

运动是相对的，所以上面左右两种图形都是可以的。右图可能更直观，它和弹匣结构一一对应：

• 栈顶（top）对应手枪的击锤；
• 栈底（bottom）对应弹匣底部的弹簧；
• 栈的深度（depth）对应着弹匣容量；
• 出栈（pop）对应着击锤击发射出子弹抛出弹壳：取数据
• 入栈（push）对应着压入子弹：存数据

@想一想@：每一次数据出栈，我们都需要将数据“往上推”吗？怎么推？

提示：运动是相对的，为什么一定要移动数据呢？能不能移动top指针啊？（复习：为什么需要引用类型）

为什么需要栈？

堆可以不管它，就乱七八糟的存放数据嘛，^_^

这是因为函数的嵌套调用就是一个的栈的使用过程！

我们的源代码经过编译/解释，最终在计算机上以机器码的方式运行，这时候就没有函数的概念，所有的代码都被转换成一条一条的指令，CPU依次逐个的运行这些指令就可以了——就像手枪击锤一个一个的击发子弹一样。（复习：冯·诺依曼结构）

但是，内存资源是有限的，所以我们不能把全部代码一次性的加载进来，只能分批次的加载执行：就像装一个弹匣的子弹，打完了再装一弹匣再打一样。装这些代码容器最好就是栈。

我们来看一下这些代码：

 static void Main(string[] args)
        {
            int average = getAverage(98,85,16);
            Console.WriteLine(average);
        }

        static int getAverage(double sql, double csharp, double js)
        {
            double score = (sql + csharp + js) / 3;
            return Convert.ToInt32(score);
        }

1. 首先把Main()压进来，开始执行，但刚声明一个变量average赋值的时候就需要getAverage()，所以我们得
2. 把getAverage()压进来，继续执行，得到了score的值之后，又需要调用Convert.ToInt32()，OK，把
3. Convert.ToInt32()也压进来，继续执行，执行完毕（忽略掉ToInt32()可能调用的其他方法），将执行的结果做为函数结果返回给getAverage()——注意，这里是一个转折点，之前都是压栈，现在开始出栈了。因为Convert.ToInt32()已经执行完毕，它不需要继续留在栈中，就可以直接出栈，为栈腾出空间
4. 接着getAverage()将运行结果返回给Main()里的average变量，所以getAverage()也没有用处了，可以出栈
5. ……
6. 知道最后Main()执行完毕

是不是？Main()先进后出，Convert.ToInt32()后进先出，整个过程，和栈的完美契合。

理解：

• 作用域，为什么大括号（}）之后就取不到变量了？是不是因为这一个函数或者代码段出栈了？^_^
• 调用堆栈
• 堆栈溢出：递归
• 值&引用类型
  

最后，在方法getAverage()中设上断点，运行，查看Call Stack窗口（如果找不到的话，导航栏：Debug->Windows->Call Stack打开）

这是一个非常有用的调试技巧，让我们可以知道当前代码是如何被一个一个的方法调用的。知道它为什么被称之为Call Stack（调用堆栈），而不是Call Methods（调用方法）了吧？

队列

是一种先进先出的数据结构。

主要用于“削峰”，以避免拥堵，在所谓“高并发大流量”（比如秒杀抢购）的场景中广泛应用：

1. 服务器/系统在瞬间接受大量请求
2. 如果没有队列的话，服务器处理不过来，就可能会宕机
3. 通过队列，让请求排队，依次处理，保证服务器正常运行

PS：是不是就和生活场景里的“排队”一样？这不仅仅是文明礼貌，而是整体社会运行秩序的保障。

作业

1. 按TDD的要求实现一个模拟栈（MimicStack），内部利用整数数组，能够：
   
   1. 实例化时确定栈的深度（depth）
   2. 压入（Push）数据：一次压入一个整数，且能提示：“栈已满”
   3. 弹出（Pop）数据：一次弹出一个整数，且能提示：“栈已空”
   4. 暴露该栈已存放多少数据（Stored），还能再存放的多少条数据（Empty）
2. @想一想@：队列可以如何实现？【选】实习一个模拟队列MimicQueue

源栈学历

在当前系列 数据结构和算法 中继续学习：

多快好省！前端后端，线上线下，名师精讲

• 先学习，后付费；
• 不满意，不要钱。
• 编程培训班，我就选源栈

更多了解 加：