学编程,来源栈;先学习,再交钱
当前系列: 数据结构和算法 修改 解锁



概念

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

  • 有时候我们也会把栈(stack)称之为“堆栈”,比如说“堆栈溢出/堆栈调用”,这时候说的就是“栈”
    PS:致敬
    https://stackoverflow.com/
  • 有时候我们会把后面要学的树(tree)称之为“堆”(个人感觉太奇怪了……)

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

另外,源栈的“栈”,知道啥意思了吧?

堆最好理解,它是无序的数据集合,简单的说,就是数据散乱的分布,没有任何组织和规律,就像一堆货物堆在那里一样:

演示:堆的形成

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

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

如何对付存储碎片?

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

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

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

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

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


说明:左图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. TDD的要求实现一个模拟栈(MimicStack),内部利用整数数组,能够:
    1. 实例化时确定栈的深度(depth)
    2. 压入(Push)数据:一次压入一个整数,且能提示:“栈已满”
    3. 弹出(Pop)数据:一次弹出一个整数,且能提示:“栈已空”
    4. 暴露该栈已存放多少数据(Stored),还能再存放的多少条数据(Empty)
  2. @想一想@:队列可以如何实现?【选】实习一个模拟队列MimicQueue
源栈培训 数据结构 算法
觉得很 ,不要忘记分享哟!

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

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

我们的 特色

  • 面向就业
  • 线上线下结合
  • 同学互助
  • 师生共赢

报班 QQ群:273534701

  • 获取视频资料
  • 要求作业点评
  • 参加阶段性测试
  • 模拟面试