键盘敲烂,月薪过万作业不做,等于没学
当前系列: 数据结构和算法 修改讲义

概念辨析

严格来说,堆(heap)和栈(stack)是两种数据结构,但:

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

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

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

堆可以有两种理解:

无序的数据集合

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


演示:堆的形成

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

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

如何对付存储碎片?

根节点最大/最小

看起来像一颗树,但和树有区别:

  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
学习笔记
源栈学历
今天学习不努力,明天努力找工作

作业

觉得很 ,不要忘记分享哟!

任何问题,都可以直接加 QQ群:273534701

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

多快好省!前端后端,线上线下,名师精讲

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

更多了解 加:

QQ群:273534701

答疑解惑,远程debug……

B站 源栈-小九 的直播间

写代码要保持微笑 (๑•̀ㅂ•́)و✧

公众号:源栈一起帮

二维码