00:00
同学们,我们来看数据结构的另外一种线性结构叫站。站呢,也是我们用的比较多的一种数据结构,包括后面我们学二叉树啊,都会用到这个站,那首先呢,我们还是看一个实际的需求,大家先看。假如我给大家这么一个案例,说这里有一个界面。这个界面呢,请你输入一个表达式,比如说我这里说的是七乘以二,再乘以二减去一个五加一,再减五,再加三,再减三,那么我要求你点击这个按钮以后,就能得到这个表达式的结果。请问你怎么完成?当然有些同学可能会想说,老师这个挺简单的嘛,对不对,我把这一个计算器打开,然后把把这个把这个例子把这个东西复制一下。哦,我连贴一把。对吧,然后一运行结果不就出来了吗?啊,你这个很无聊的对不对,你要这么去想就很无聊了,因为人家就是让你去完成,让你自己去完成,不是让你借助计算器去完成。
01:14
对不对,就相当于你要自己去写,对这个表达式的一个。一个解析,并且把结果算出来。那么同学们一定要注意啊,这个地方人家并没有让你把一个一个的数输进去,而是直接把这个表达式整体输入。并计算结果,所以说同学们,同学们这个地方其实问的是计算机底层是如何用什么样一种方式来计算这个结果的,并不是像我们想象的那样说啊老师,那我这定义几个变样,Number number1 number1等于一个什么值,NUMBER2等于一个什么值,然后呢,我再把它算出来,不是这样子的。
02:00
因为人家不会让你单独的输NUMBER1NUMBER2,而是直接怎么样呢?相当于说这个意思给你传了一个字符串。OK,比如说我给你传,给你传了一个字符串,长得是这个样子的。也就是说,你从程序里面你只能得到一个字符串,然后直接告诉我这个结果是什么。因此,你就必须要去想一个办法,把它的数字拆出来,然后还得解析它的运算符是什么,还得考虑哪一个运算符先计算,哪个运算符后计算,是不是还是挺麻烦的呀?同学们告诉大家,要解决这样一个问题,要解决这样一个问题,就需要用到一个叫赞的东西。占这样一种数据结构就可以解决对G对一个表达式的一个求解。好,这个就是一个实际问题,那下面呢,我们就对站来做一个呃,相对系统的一个介绍,首先站的对应的英文单词是。
03:05
它是一个先入后出的一个有序列表,也就是说什么意思呢?大家看是先进去的数据后面,呃,先进去的数据。然后呢是后取出后进区的数据先取出。所以说同桌你看这是一种限限制线性电表,呃,它是限制线性表中元素的插入和删除,只能在线性表的同一端进行的一种特殊线性表。允许什么呢?OK,允许插入和删除的一端为,变化的一端称为,称为站顶。另外一端是固定的,不能动。内端不动,其实它它始终是在站顶往里面放和从站停取数据,那么不动的这一端呢?我们称之为占顶,叫bottom。明白啊,待会我们画一个图,大家就明白了。那么根据站的定义呢,最先放入占中的元素,再占底,就好像同学们小时候玩的那个博客枪,玩过那个小男孩都玩,玩过那个博客枪不是压子弹吗?
04:16
压一颗子弹进去,比如说压了个一个子弹进去,在下面再压一颗,再又在上面再压一颗,再压一颗,假如你压了五颗子弹,其实最先打出去的子弹是最上面这颗子弹,而最上面这颗子弹其实是你最后压入的是吧?就有点类似于这样一个结构,所以说最先放入占中的元素,再占停,最后放入的元素再占停。而删除元素或者叫取出元素刚好相反,最后放入的元素,最后最后放入的,因为你放到占停了嘛,它先被取出,最先放入的元素呢,最后被取出或者叫删除。好,这是占的四个方面的说明,那么下面我们看一张图,加深一个认识,同学们看,这张图非常的简单啊,非常简单,同学们看。
05:05
这个地方是一个空站,这个站呢。这个数据可能是放在数组里面的,也可以是链表来实现。那么在最初的时候占顶和占顶呢?大家看是没有指向,没有指向的,比如说它是一个负一对吧,那么当我们一入站的时候呢,站底往上移动了,占顶呢也上移动了,假如我们又加。压了一个,入站了一个二,或者说加入了一个二到站里面,那么你看黄绿色的这个就没有动了,绿色的是占底,占底它不动,那么红色的呢,往上移动,代表有一个新的数据加入,再加一个三,红色的再移动看,绿色的仍然没有动,所以说我们刚才讲过占底呢,它是固定的不动。只要有一个数据,他就只向这里,以后在就不不再动了,而站顶呢,加的时候它就一直往上找,那么我们再来看一个出站的一个情况,假如现在是用宿主来模拟一个站。
06:10
当前呢,大家看这里这个站呢,一共有三个数据占顶指向了十,站顶指向30,现在呢,我们取出一个数据,有一个专业的术语叫出战,就是在站里面我们取一个数据出来,叫什么呢?叫出战。也叫泡泡。也叫泡泡,后面我们还会讲的,那么一旦这地方出了一个站以后呢,同学们看。出,一旦出站了,站站顶没有变化,站顶会往下移动一下,就代表我把30取出去,然后站顶呢往往下移动,如果我再取的时候呢,取出的就是20了。以此类推,好,这个就是一个出站和入站的基本概念,那么出战呢,我们有一个刚才讲过一个专业的术语叫pop。啊,英文叫pop入站呢,也对应一个专业的英文单词叫push。
07:05
这点大家理解一下哈,最后我们再来看一下站的应用场景,除了刚才的求表达式还有哪些作用呢?同学们看,还有一个子程序的调用。子程序调用是在跳往子程序前呢,会先将下一个指令的地址存在这个站中,直到子程序执行完毕,再将地址取出回到原来的程序中,这个有点像同学们学的那个return语句。Return那个语句。Return。或者是我们调用一个方法结束以后,或者是在方法里中调用方法也是这样一种机制,它是有个站来记录这个地址的,我们再看递归调用,递归调用呢,它在调用之前除了存储下一个指令之外,还会把参数变量等数据压入这个堆栈中。啊,就这说的对战就是战,那么还有像刚才我们讲的表达式的求值或转换,转换里面用的最多的是什么呢?就是我们所说的这个后续后缀。
08:09
啊,就是我们所说的宗罪。中缀表达式转。转什么呢?转后缀表达式后缀。表达式。后缀表达式,这个呢,后面我们还会讲到,后面专门讲中缀和后缀表达式的转换,这个是在面试和这个笔试的时候经常会问到的一个问题,就是站的一个经典应用。二叉树的便利呢,也会用到这个站。啊,也会用到这个站图形后面我们讲图结构的时候,有一个叫深度优先。深度优先。深度优先的这个搜索算法呢,也会用到站,所以说同学们可可可以看到站的应用场景还是比较多的。对吧?好,那关于站的应用场景和基本介绍呢,我们就说到这,我把刚才讲的内容给大家板述一下,待会儿呢,我们做快速入门案例,好,同学们,那刚才我们讲的这个数据结构叫站,我们捋一捋刚才讲的这个思路。
09:11
往下走。好,我在这儿写,写上这个名称啊,叫赞。OK。OK,好。那么这样呢,我们刚才给同学们讲的第一个就是一个实际的需求。啊,求表达式的一个需求,引起大家对这个问题的思考,对吧,我说说一个表达式,然后呢,这个是怎么怎么来的。对吧,这边就引出了我们一个赞。这边就引出这个站的概念了。就是站是在哪里会用到呢?比如说我们求一个表达式,这个时候就有可能会用到,对吧?好,我把这个往上边挪一挪。啊,注意这个问题,就说人家给你传,传出一个表达式,你就把这个结果给我算出来,这就会用到赞,那么说完这个需求以后呢,我们就对站做了一个相对呃完整的一个介绍,完整的一个介绍,我们说到站的一些基本的概念有哪些呢?我们捋一捋,首先站的英文单词要知道sta,它的特点是什么,我们捋一捋。
10:18
好,我把这个地方给大家标一个号啊。首先呢,它是一个先入后出,这个我就不再讲了,因为刚才已经说过好几遍,还有一点要注意啊,它这个变化的一端是暂停,也就是说他在取数据,还有这个。呃,取数据和入数据的时候呢,会会叫入站,其实变化的主要是top占底不变,就说另外一点是固定的一端,称之为占底。明白好,那下面第四句话其实是对第三一句话的一个再再次的解释,后面呢,我们这有一个图,以图的方式啊,图解的方式啊,说明了一下赞,说明了一个出战。
11:04
出站和入站的一个概念。概念,那么出战刚才我们讲过有个英文单词叫pop,这个一定要记住,叫pop。啊,出战时pop入战是push,就压压一个输进去叫push。那么这边呢,我们有一张图,把这个图呢,给各位同学板书过来就可以了啊,非常的简单,把这个图放过来。好,这个图讲完了以后呢,大家对入站和出站应该有个基本的认识了,我说一遍啊,我是把它当当零基础来讲的啊,所以说有些同学可能知道这个概念呢,你就再巩固一下,后面呢,我们又说了站的应用场景呢,有1234,后面呢我们会讲这个还会讲。一个逆波兰表达式的,怎么编写二叉树的便利呢,也会讲,比如说这个前序后续中序的遍历图形的优度,深度优先呢,也会用到占,我们还也也还会讲好,这是站的应用场景的一个小结。
12:02
OK,那么我们这里一共总结了有这么五种,对不对,一共有这么五种,好捋捋。屡屡思路。好,同学们,那关于站的应用场景和基本介绍呢,先给同学们聊到这里。
我来说两句