368_尚硅谷_Go核心编程_数据结构和算法-栈.avi原创

好的同学们，我们来看一下站这个概念，那么我个人认为啊，就作为一个程序员来讲呢，其实都必须对站有一个了解。你看我们在做编程的过程中呢，我们经常用到加减乘除或者各种运算，对吧？那么我们要深度的问大家一句，就是它的这种运算在我们计算机底层，或者说编译器，它是怎么去处理的？啊，这个问题呢，其实对一个程序员来说，其实应该是有所了解，至少你要了解它的一个基本的运行原理，那么我们来看一个实际的需求，引出这个站的概念，比如说我给大家输入一个表达式。是这样一个表达式。那么我要求大家点击计算，注意啊，也就是说这个计算式是你从一个输入框输入进去的。不是像我们在程序里面直接写的，比如说如果我我这个地方是直接把这个算式放在我们程序里边去，当然同学们都知道这个很容易很容易做出来，比如说我用一个结果来接收。

那这个我相信同学们都知道，它是可以运行的，对吧，七乘以二怎么怎么怎么样，这个都都很简单，但是呢，当我们是以一个字符串的形式给他传进去的，它是怎么来进行扫描，然后把这个结果得到的呢？最底层就用到了一个站。哎，这个站大家看，我的问题是请问计算机底层是如何得到运营结构的，注意不是简单的把算式列列出来运算，因为我们看到的这个算式啊，是我们看到的，但是计算机怎么理解这个算式呢？也也就是说，对计算机而言，当你提交这个算式的时候，它接收到的就是一个字符串。那么字符串怎么去解析这个？这就计算机怎么去解析这个字符串，从而得到我们想要的结果，这是我们要去讨论的问题，它底层其实说白了就是研究，到下来就是我们的编译器，它是怎么进行加减乘除的这种预算的，OK，好，这里面呢，就引出我们的这样的概念了。

好，这是站的引出，那么有了这个站的引出过后呢，我们就来看站的一个基本使用，来我们看一看站它有哪些需要同学们了解的，有些程序员呢，也把这个站直接叫堆栈，所以说你在网上去搜的话呢，你会看到，诶有时候这个堆栈它也叫栈。也叫站，它有时候它是同一，它是它是就叫法就是有时候不是特别精准说站和堆栈有什么区别，站和堆是有区别的，站和堆是有区别的，但是呢，有时候有些程序员直接就把站叫堆栈了。但我们严格的叫呢，还叫赞比较准确一点啊，它的英文单词叫sta。然后呢，站它跟前面的队列有一个最大的区别，它是先入站，是一个先入后出的这么一种数据结构，就是谁先进去，结果反而后出来，大家可以把它想象成是一个弹夹，就小小时候小小男孩比较喜欢玩的那个博客枪，双枪老太婆玩的那个玩意儿，对吧？往下压一颗子弹，再压一颗，再压一颗，其实打出来的子弹是最最后压进去的，他是一下打出来，呃，最最后打出来是最先压进去的，因为它会往下面压嘛。

啊，站就是这么一个东西，它是先入后出，先入后出，第二个呢，站是一个限制性线性线性表，它的元素和插入和插入和删除只在线性表的同一端进行，也就是占顶，待会儿我们会看到这个结构啊，它允许插入和删除的一端为变化端，这个称之为占顶，因此占顶呢是一个关键。啊，它总是从站底取，也是从站底往里面放啊，它只有一端可以出来占底呢，是动不了的，站底是动不了的，不跟我们队列啊，队列有对对头和对尾，它这个没有，它就一个占底。

所以它的占底是动不了的啊，所以说你看我在这写了一个东西，我这写了一句话，说说另外一端为固定的一端，称之为占占底。好，那么这个呢，我们就大致的做了一个介绍，我们看一个图吧，大家看这个图。大家看这是一个关于站的，呃，出站和入站的一个示意图，我们来。比如说。这个地方呢，是一个空战。那占一般我们用什么来做呢？一般是用数组来模拟啊，一般是用数组来模拟，那么占顶和占顶在刚开始的时候呢，都为负一。啊，刚开始都为负一，都为负一，那么这个时候当它有一个一入站的时候呢，占底和站点都往上面移动一位。

啊，这个绿色的代表占底，红色的代表占顶，那么都移了一位过后呢，好，这两个都在，都在这个呃，零这个位置了，就下边为零的这么一个元素位置。然后如果我们再入一个站呢，占顶就往上走，站是占底呢，就不动了啊，占底就不动了，那也就是说将来这个占底如果为负一的话呢，大家应该可以马上感觉到，就应该推出来，他为负一就代表我们这个战士空战。啊，代表是空战好，如果再入一个呢，又往上走，以此以此类推，这个是入站。入站，那么审后什么时候这个站满了呢？就是这个地方啊，就是这个站顶到达了我们这个宿主的。最大的那个下标就是它的长度减一，那个下标就不能再往上面再再给了，那有些同学老师假设我我这个暂时用它无限的延伸，可不可以也可以，那么你可以用链表来做啊，也当然也可以用那个切片来做啊，也可以用切片来做假设一般来说我们这个站呢，都是有有一个限制的，好这个站，这个入站说完了，我们看出站，怎么出站呢？大家看假设站是这么一个情况。

出站之前，站底和站顶是这样一个情况，出站，出站是从这个站顶弹出去，弹出去一个，弹出去以后呢，我们这个站顶呢，就往下面挪动一位，也就是到这儿来了，大家看这个图。比如说我从这边弹出去一个30，那么30被取出以后，占顶是往下移动一位，占底呢不变。占比不变，好了，同学们，这个就是站的一个出站和入站的一个基本的概念啊，示意图大家应该能够看得到啊，我们再来看站的应用场景有哪些，那么站它在哪些地方能够使用得到呢？就说什么地方有可能用到我们这个站的数据结构呢？大家看有这么几个地方。

呃，第一个地方呢，就是子程序的调用。哎，比如说我们调一个函数对不对，那调一个函数它底层是怎么实现的呢？对吧，它在跳往一个子程序前，会先将下一个指定的地址先存在这个堆栈里面，它是存到，那他如果不存到这个地方，他不知道以后干完事过后应该回到哪个位置，所以说他这个地方会有一个这样的一个站。好，直到子程序执行完毕后，再将地址取出，回到原来的程序，哎，这个就是在底层里面呢，它会先保留当前的一个地址，然后执行完了再回来，他他把那个地址弹出来，然后再回到以前的那个位置，再继续做，所以说大家知道这个return是怎么做的了。这个维怎么做啊，其实它在计算的时候，它它整个函数也也有一个这样的概念，就是为什么你看那个有以前有同学说，诶为什么那个函数先执行这个函数后执行，其实个那个函数它有一个站在管理。

他比如说在跳到另外一个函数之前，他先把原来这个地址前压到这个站里面，他开又开开一个心站开始执行，执行完了过后他回到这个站底，再把这个地址取出来，哦，我我继续应该到哪去做啊，它是这样子的，那么还有像处理这个递归的调用啊，处理递归调用，你看处理递归的时候呢，他把这个参数区域的变量的数据也瞎压到堆里面去，那么再开一个新站之后，再开一个新站，把新的变量和呃这个数据压那个心脏里面去，所以他的数据也是相互独立的。还有像这个表达式的求值和转换，比如说刚才我们所说的像五乘以四对吧，减去三再加上一个五，诶这个地方也也用个赞，待会儿呢，我们就要自己来实现这个东西，就待会我们来自己写一个算法。把这个算出来。但是我要告诉大家啊，就说这个你要写一个非常完整的，其实是比较麻烦的，比如说你要考虑到小括号，还要考虑到中括号，有些地方还要考虑到大括号，这个难度还是有点大。

所以说我们在这呢，更多的是把这个站的一个基本的它的一个使用的原理告诉大家，所以说我们待会实现这个表达式呢，在功能上不是特别强大，只能做加减乘除啊，小括号大括号呢，我可以交给你们去做，我提提提些思想算法在里面啊，好，然后呢，二叉树的便利也会用到占啊，二叉树的比如说呃，前序便历是吧，和后中序或者是那个后续便历都会用到这个占，然后呢，还有像图形的深度优先的这种搜索算法也会用到站。啊，这个站呢，是几几乎就说在底层里面玩的很多，好了，那有这些东西过后呢，同学们我们就来快速的入门来完成一个站的使用，那么待会呢，我这样做啊，我们来用什么做呢？我们用数组模拟一个站，然后呢，呃，把这个站的哪些讲清楚呢，一个是出战。

一个是入站，还有一个还有就是一个便利，就是把这个站给大家打印出来，还有一个打印站或叫输出站。啊，我们把这个呢给大家说一说啊，我们把这个说一说，好，那么我们就现在准备来做这个东西啊，做这个东西注意啊，这个赞，我希望同学们好好理解一下，好好好理解一下，好，那现在呢，我们就把这个板书一下，先把前面讲的板书一下，我们再接着来用代码实现它。好，这是站，我们写到这里。赞。OK，给他来一个标题二，对，来一个标题二。好，这个是个站。好，有点卡顿，正在备份啊，稍等一下。啊，每隔20分钟备备份一下站，那刚才我讲了哪些东西呢？我们来简单的看一下，首先我说了一个站的引出，就是什么时候，呃，什么地方会需要到站呢？我看了一个实际需求。

那我举了一个计算表达式啊，一个表达式的计算对吧。好，在这里我说在计算机的底层，在计算机的底层它是怎么来实现这个计算的呢？这里面就用到了站。我在这儿引出这个站的概念。好，那么紧接着我们又说了一下，呃，占的一个几个知识点吧，第一个呢，就是概念，概念性的东西有有说到一个占顶，有说到一个占顶，那么大家知道占底呢是固定不变的，占顶呢是变化的，就是说它的它数据入站是这个占点的变化，出站呢也是从站点，所以它一端是固定的，另外一端是变化的，好这点大家要清楚啊，所以说这个站的介绍。先给大家阐述到这里。

好，这是站的一个基本介绍。好来一个标题三，那这里面呢，我把它做了这么几个说明第一点对吧。赞的英文star。好，然后呢，大家要记住站的一个基本特点是先入后出。啊，这个跟队列刚好是相反的。啊，这个特点，这个一定要记住先入后出啊，待会我们在写计算表达式的时候，如果你忘了先入后出，这个结果刚好相反，就你在做减法的时候，你刚好是反过来的，比如说本身是五减四，结果你会发现你得出结果刚好是四减五。如果你不把这个记住，你你整个这个结构是错的啊，还有一个呢，就是占顶啊，占顶呢是变化的一端，占底是固定，固定的一端啊，固定一端是占底啊，这这个基本概念要要很清楚。好的。好，那么这是它的一个基本介绍，我们紧接着呢，又说了一下他的一个示意图，就是站的一个示意图。

我们这写的站着示意图。诶，站的入站啊，入站和出站，出站的一个示意图。把这儿也给同学们板书到这里啊。就是他的入账和出账啊，是一个什么样的概念。啊，我这画了一个这么图。好，这个示意图还是很有用的啊，待会儿呢，我们看到有什么作用呢，待会儿要知道我们初始化的时候，占顶和占顶都是负一。都是负一，这样就决定什么，怎么去判断它是个空站啊，怎么判断它是个空站，然后呢，这个案例啊，这个呢，它的一个站的应用场景有这么我举了五个，但实际上可能远远不止这五个的用处啊，还有别的地方。好，这是这个应用场景，第一个子程序的调用，第二个处理递归。好，第三个表达式的转换，第四个就是二叉树的便利，第五个图形的这个深度优先搜索算法。

好，下面呢，我们再看一个案例占的。这样的案例。好，我们来开始写了。好，那么我们来走下代码啊，关于这个第一个介绍这一部分，我们先给大家说到这。