速学数据结构-栈的原理与实现（Python）原创

接下来呢，让我们来了解一个简单的数据结构啊，叫做站，站呢大家应该都听过是什么东西对吧？其实站呢，在生活中有很多地方在用这个东西啊，那么举一个生活中非常常见的一个例子，就是说我们平时在家里去吃完饭洗碗的时候，洗盘子的时候，那我们洗完了盘子，洗完了碗，是不是会把先洗好的，洗的最干净的那一个放在最下边，是不是先把盘子落在最下边，然后再洗一个再往上落，再洗一个再往上落是吧？那么不断的往上落呢，当你洗完了之后呢，这个盘子也就落好了，这是你洗盘子的过程，那么如果你想用盘子的时候，是不是我们要把哎，最后洗好那个盘子，也就是最后你落在这个盘子先拿出去啊，你不可能说是你把最底下的盘子抽出去用啊，对吧，那么上面的是不是就碎了呀，对吧？那么这个原理呢，其实就是和我们所谓的这个站啊，原理是一样的，我们最先洗好的盘子呢，最后用，最后洗的盘子呢，最先去用啊那这就是关于生活中一个站的一个小原理。

么再来看一下关于数据来讲，我们这个站是什么意思吧，那么这里呢，这有一个图啊，我们先来看一下这个图，那么这个图呢，是有一些数据的一个入站和出站的一个操作的，那么看这里的数据，A1 a21直到A，他们不断的去按照顺序去入站，那么在出站的时候呢，他出的顺序就是A1直到A2A1啊，那么这个是怎么样一个思想啊，其实它的思想呢，叫诶，Last in first out，也可以叫做是后进先出的一个原则啊，我们来看一下吧，那么首先呢，我们要把这个A1入站，那么A1入站的时候呢，它肯定是要落到站的底部啊，落到这个位置对吧，那么A2在入a an2在入的时候呢，因为最底部已经有了这个元素了，那么此时呢，我们这个A2的元素呀，要落在这个位置啊，那么以此类推，我们不断的去入战，那么最后呢，An在入站的时候，是不是应该放到了最上面的一个位置上去啊，因为下边的每一个位置都已经被占领了，对吧，那么好了。

那么入账的操作完成了之后呢，如果我们想用这些数据怎么让他们出战呢？其实出账的顺序啊，和入账的顺序是相反的，谁先进谁就后出呗，因为它被压在底下了呀，对吧？那么可以看到这个an是不是最后进来的，那么在出站的时候，因为下边没有办法动，所以说我们只能先把an让它出来，对吧？那么再往下呢，An减一出，然后一直到AN2出，一直到an一出，那么是不是就满足了这么一个后进先出，叫做last in first out这么一个原则呀，对吧？那么这个呢，就是关于我们战的一个基本思想啊，那么要记住这个过程呢，叫入战，这个过程呢叫初战，而两个东西呢，一个叫占顶，一个叫占底啊，底部的元素和顶部的元素分别叫占顶和占敌，那么这个呢，其实就是我们关于占的一个原理啊，它很简单，那么好了，既然站这么简单，那么下面呢，我们来看一下我们如何通过这个Python的代码去实现我们所谓的这个站呢？来一起来看一下啊。

哎，我先把这个东西给它清掉。好了，那么关于站呢，其实我们创作起来也是非常简单的，我们可以去专门创建一个啊class啊，叫sta，把它用作是站啊，那么第一步呢，我们肯定是要用一个东西把这个站做一个初始化的一个操作，那么初始化的时候呢，其实在我们这个Python基础的一个一些数据结构中啊，像列表啊，字典啊，集合呀，对吧？那么其实呢，我们最常用的一个东西呢，就是去用列表去做啊，那么首先呢，我们可以用列表去初始化一个站，那么当然了，列表它有自己的一些操作，我们可以从前面插入，可以从后面插入，对吧？那么但是在这个class内部呢，我们可以给当前我们做好的这个列表去附上一些功能，那么附上这些功能之后呢，把它变成是站哎，就OK了，就是一个中心思想所在啊，无论是现在讲的站也好，还是后面这个队列啊，双单队列也好，其实它都是用的一样的一个思想啊，大家把这个思想给记住了。那么来看吧，那么既然首先我们用这个引函数把这个站给它初始化好了，那么下面呢，第一个我们可以去创建一个empty，去判断这个占是否为空的一个方法，那么为什么要判断它是否为空呢？因为占如果是空的时候呀，是不是也意味着我们这里是没有元素的，我们纯这个元素就是直接放到占比了，对吧？那么这个时候呢，我们可以去判断这个东西是空的还是非空的，那么判断的时候呢，直接把它和这个空列表做一个哎，等价的一个判断就好了呗，那么如果是空的就返回处，如果是非空返回false，对吧？那么这是关于判断空，然后再往下呢，就是我们这个比较重要的一个叫做入站和出站的操作啊，因为刚才我们讲了呀，我们这个原则叫后进先出，所以说我们在入站的时候是不是应该让他后进啊，那后进怎么进啊，那么列表的顺序是不是，比如说现在我进一个数一对吧，那么关于根据我们这个列表啊，我们后进的时候是不是要让这个数在这个一的后边啊，那么在这变成二。

然后三，然后四，然后五，这是不是它一个正常的一个入站的一个顺序对吧？那么想要列表完成这样的操作，怎么完成呢？是不是列表我们有一个哎东西叫做a pad，我们可以直接在列表的末尾去追加元素啊，那我们可以用a pad去不断的去追加元素，去实现这个入站的一个操作啊，也是关于入站，那么再往下呢，就是出战，出战要怎么出呢？那么出战我刚才说了呀，我们是后进先出，就是最后进来这个五啊，要最先出去，那么列表怎么让它先出去啊，那么是不是它有一个方法呀，我们列表里有个pop函数，Pop函数可以直接把最后的一个元素给它退出，给它移出，对吧？那么这个时候呢，我们就可以用这个泡函数去实现战的一个出战的一个过程啊，那么如果用了一下泡泡是不是五就被弹出了呀，对吧，这就是出战啊。

那么入站和出站呢，就可以用这个列表的两种方式给它完成了，那么再往下我们可以去构造一些功能的一个函数啊，比如说这个返回站点的元素，哎站的话呢，我们有很多很多元素，那么我们去出站的时候呢，是不是哎出了站之后是不是相当于弹出了一个占点的一个元素啊，所以说我们可以去通过一个功能函数去判断一下占点的元素是什么，怎么判断呢？是不是直接把我们占点元素就是这个列表的最后一个元素给它print或者是return就OK了呀，对吧？那么这个呢，就是这个返回战略元素P函数的一个作用啊。

那么最后呢，是干嘛呢？我们要看一下这个占中还有多少个元素，那么这个元素啊，是不是我们也可以直接去用这个烂函数去表明出我们有多少个啊这个函数啊对吧拉，函数是列表是去使用的，那么我们在这个呃，Star在站中也是可以把它进行一个复用的一个操作啊，那么这个呢，就是关于我们这个站的一个class这样的一个类的一个创建啊，当然如果大家有其他的想法，又想要去实现其他的功能，也可以自己去创建一些这个啊函数啊都是OK的，那么好了，先把它运行一下吧，然后再往下我们看一下这个测试代码啊，那么首先呢，我要把这个class给它实例画一下，对吧？然后呢，我们去判断它是否为空，那么第一个判断一下，运行之后发现它就是空的对吧，那么再往下呢，我们去给出一个测试代码，我们把这些啊，I like Python这三个单词啊，不断的把它入站，然后再进行一个出站，然后再返回站井元素这么一个操作啊，那么可以在这给大家简单画一下这个操作是怎么样的，那是不是首先push有。

是这里是入账对吧，首先把I入占了，那么第一步是不是把I放到这个位置了，那么第二步like。在这儿对吧，第三步Python在这对吧？那么这是我们这个入账的一个操作，那么入完账之后呢，这三步执行完了呀，你会发现这个站啊形成了这么一个哎形式，那么再往下呢，我用pop泡建一个出站，那么pop出站出的是谁呀？是不是PY被出去了呀，对吧？那么PY一旦被出去了之后，是不是剩下的就是like和I了呀，那么此时如果我运行这个代码，我返回这个站点的元素是不是返回的应该是like呀，对吧？那么好了，我们来看一下这个返回的元素到底是不是like呢？来运行一下，哎，运行完了之后发现，哎，它的确就是like啊，对吧？那么如果大家还要去有疑问的话呢，我们再返回一个吧，我们再去进行一个出站，然后返回这的元素，看看它是什么呗，对吧，首先S点泡泡，然后呢，再再来个s.pick对吧？那么这面两个操作一运行，你会发现变成了I对吧？因为刚才的PY出去了，这回呢，Like也出去了，然后呢，I是不是被剩下的呀？那么这就是我们进行的一个入。

出站和出这么一个操作啊，对吧，那么好了，入完账了，出完账了，还有一个没有用啊，有一个size，我们来看一下此时这个站的size是多少呗，运行一下是一对吧，因为只有这个I一个元素对吧？那么好啦，到这呢，我们关于这个啊站的一个简单的了解就了解到这了，这个功能类大家可以自己去实现一下啊，那么如果想实现其他的这个函数呢，也可以自己去完成，那么好了，我们下个视频见。