00:00
来,同学们,下面呢,要给大家讲另外一个数据结构,叫赞,我相信同学们在学前面的这个Java也好,其他语言也好,可能都听说这个站。但是你们对这个站的理解到什么一个层面呢?可能大致的同学们也就知道哦,我调一个方法,他开辟一个站,里面有些数据是独立的,估计大部分是停留在这么一个认识的,那现在呢,我们对这个站呢,站本身呢,同学们站本身这个数据结构其实并不难。因为站的最主要的操作无非是一个出站,一个入站的操作,对不对?我相信同学们都能写出一个。占这个数据结构,但占的难点是在于你怎么去运用这个站解决一些实际的问题,你比如说我们看一个实际的需求,你们先想一想,你们能不能把它做出来。什么问题呢?同学们看,我在这一个页面,我输入了一个。
01:02
表达式。七乘以二乘以二加五减呃减五加一再减去五乘以三减三。点击。你把这个结果怎么算出来?有同学能把它做出来吗?王长城,有十多秒。这是一个字符串啊,说老师这个很简单嘛,打开我的这个计算器,往里面一扔不就出来了吗。那关键人家怎么底层实现的呀?大家有思路吗?那随便找一个同学看看你有没有思路,就根据你现在的一个结构,你能怎么做。因为你收到是一个字务串,明白吧,你收到这个字串,你不可能把一个字符串,当然也就是说我我调一个API对吧,我传一个表达是API,但是我们要自己实现。就是我们自己去用我们的一个最原生态的方式来得到它的结果啊,这个就要用到我们这个站了。
02:04
对,这个要用多少,那同学们看啊。那么这个需求很很简单。我输了一个字串点击的结果,请问计算机底层是如何得到这个结果的?注意不是简单的把算式列出来运算,因为我们这个算式。对计算机而言,它拿到是一个字符串,我们讨论,我们讨论是把一个字符串怎么进行一个处理,得到一个结构,那这里呢,我们就用到一个数据结构,叫做占。好,那既然讲到站,我们就来看站的一些基本的一个常识问题,对吧?好,先看站的基本介绍,那么站呢叫sta sta,然后呢,它的这个也,它也是一个有序的列表,有他也是有顺序的。那么他遵循的这个原则是什么呀?先入后出。这个大家在前面已经学过了,就说我先放进去的呢,哎,最后出来。
03:04
那后放进去的呢,那他先出来。那么占它是限制限性,它是限制线性列表元素的插入和删除只能在线性表的同一端进行的,也就是他总在占顶执行。允许插入和删除的一端为变化一端,称为top。及站顶,另外一端为固定的叫站顶,就说占底它是不动的。他一直在,一直在下边,他不动,他永远就站,它永远只有一个top在这不停的移动。OK,那么根据我们占的这个定义,知道最先放入占中的元素,再占底,最后放入的元素再占底,而删除元素刚好相反,或者叫取出元素。刚好相反,最后放入的元素最先删除,最先放入的元素最后删除,那么我们来看一个占的一个简单的数据结构,我们来看一看同学们。
04:04
来,各位同学。同学们看下。这里我看有没有在录视频啊。OK,没问题。那么看这这样一个,我们来注意观察它的特点,这个站呢。第一个状态是空的。我这里分别用一个红色的箭头和绿色的箭头表示占底和占底,那么占底你看我往里面把一放进去,好,当我把一放进去过呢,这个红色的箭头呢,往上移动了一下。啊,当然实际上这个移动呢,呃,就是加一嘛,说白了就加一,那但是绿色的没有变化,等到我把二放进去呢,红又红色的箭头又往上面移动了,相当于这个占顶呢,诶加了一,这个绿色人们变化,我加三也移动,所以说你你们看到这个特点是站底一直没有变化,而站顶呢在不停变,那么这个就是入站,那出站又怎么办呢?大家看这边出站的时候呢。
05:07
我们把占顶的这个值,就这个值腾的一下弹出去。取出来或者叫取出来过后,我们这个站顶呢,就会往下挪动,哎,就变成这样子了。就弹出一个占点呢,就往下面减一,依此类推,好同学们,这个就是一个最简单的站,那么站一般呢,用什么实现呢?我们一般来讲用数组或者列表都可以实现。那么我就举一个例子,我们用数组来实现啊,同学们,我们的目标是这样子的,怎么一个目标呢?我们先把这个站的基本的一个操作。代码写完,写完以后我们就来用站来把这个。问题给他解决了,如果我们讲完一个站不讲应用啊,大家可能会觉得这个讲这个也没什么实际意义,就这个算法在什么地方体现出来,同学们算法它是在一个什么地方体现的,就是在一个实际的具体的一个需求。
06:07
就需要你去设计一个小算法了,明白好,那现在呢,基本的介绍我们就先说到这儿啊,后面还有一个再说一个站的应用场景,除了刚才。对这个表达式进行转化和求值呢,我们这还有另外几个常用的场景,我们来看一下子程序的调用。啊,我们在有些同学学过编译原理就知道,那么编译原理呢,它底层在进行编译和执行两个计算的时候,它其实就是两个站,一个是符号站,一个是数站,它是来回的切换。那比如说我们在开辟一个站的时候,在跳往子程序前,先将下一个指令的地址压入到站中,直到子程序执行完毕过后再把这个地址弹出来,回到原来的程序中。其他底层是用这个站来实现的,还有处理、递归、调用。
07:02
诶,在处理递归调用和子程序调用类似,只是除了存储下一个指令的地址外呢,也将参数,区域变量等数据压入对账中,那你们知道为什么,你们你们知道为什么,就说我们递归调用这个函数,等到它返回的时候,他还可以把原先那个数据就是原先那个。为底层那个站的数据取出来,是因为他先把这些数据压到站里面去了。那取的时候它是按顺序取的,所以说待会我们看那个站的应用,你会理解的更深刻一些,还有表达式求值,待会儿呢,我们就用这个来实际的解决,我们这个是会实际编写一下实际解决。那因为这的应用场景很多,我们讲这个,还有二叉树的便利,我也会讲。二叉树呢,我们会讲一个非常经典的二叉排序数,那个听完过后对大家对二叉树的理解应该会非常的棒啊,二叉树的便利也会用到我们的赞。
08:01
还有有些同学将来如果是处理这个图形,也要对站有一个深刻的理解,它会有个叫深度优先的搜索法。也会用到站,说站的应用场景其实还是蛮多的。OK,好,那么有了这些基本的这个介绍过后呢,那现在呢,我们就先把这个基本介绍给大家整理一下,然后我们就开始做基本介绍,好,OK,那。站的一个。基本的概念我们就先整理一下。来一个赞。好,那刚才我们讲了什么内容呢?首先我谈了一个实际的需求。就引起大家对这个站的。站的一个这个兴趣是吧,诶这个站他确实有用的,比如说。我们如果要去计算一个表达式的结果,我们就会用得上。啊,继续推出我们这个站了。好,这是。
09:01
有一个需求引出了这个战。然后呢,我们对这个站呢,呃,它的一个基本介绍有这么四点,大家看一下,站的一个最重要的特点就是它是先入后出。这点大家必须理解,第二个呢,它只能在一端进行这个。变化,它允许它它只能在线性表的同一端进行这个进行这个操作,就他只在占点上进行操作,这点大家要理解好,还有一点就是呃,先先放进去的怎么操作,后放进去的怎么操作,好吧,好,这是站的基本介绍给大家放置进来。OK,诶,这个地方有问题啊,这个地方为什么呢。啊,因为我这加了一个粗体,所以他这个样式就被继承下来了,我稍微的整理一下。好,站的一个基本介绍,我把它标成这个不。不同的这个标号。OK,四点。
10:00
好,站的基本介绍,但基本介绍完了过后呢,这有一个示意图,这是我们画了一个示意图,站的一个示意图也给大家放到这来。好站的示意图。我这里呢,有一个截图,我就把它放过来了,好吧。这个说完了过后呢,我们说了一下站的几个经典的应用场景。好赞的几个经典的。啊,经典的应用应用场景,OK。那这个应用场景呢,我们也把它整理到这边来,我大概总结了有这么五点。五点。好,这五点呢,我也给大家排一个号就可以了。好,这是基本介绍阶段。
我来说两句