你好我是久远，我们先来复习一下上周我们讲的知识。
- 什么是链表？
在计算机科学中，链表是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针。
- 链表的优点
由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比数组快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而顺序表相应的时间复杂度分别是O(logn)和O(1)。使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。
什么是栈
栈有时也被称作堆栈或者堆叠。栈是有序集合，它的添加，移除操作总是发生在同一端，设这一端为顶端，则未执行操作的一端为底端。
栈中的元素离底端越近，代表其在栈中的时间越长，最新添加的元素将被最先移除。这种排序原则被称作 LIFO（last-in first-out），即后进先出。它提供了一种基于在集合中的时间来排序的方式。最近添加的元素靠近顶端，旧元素则靠近底端。
生活中的例子：
在我们的生活中也很常见关于栈的例子，假设我们有一个放羽毛球的球桶，我们只能从桶的上面取出球，底部是不能取的，靠近开口的球，更先被取到。
既然有取出的先后，那么我们的栈也算是有顺序的，我们依旧使用列表来实现栈的一些操作。
举例来说，对于列表1, 5, 3, 7, 8, 6，只需要考虑将它的哪一边视为栈的顶端。一旦确定了顶端，所有的操作就可以利用 append 和pop 等列表方法来实现。
在这里我们视列表的尾部为栈顶，因此当进行 push 操作时，新的元素会被添加到列表的尾部。pop 操作同样会修改这一端。
栈的操作
我们前面已经介绍了栈的基本情况，既然我们要实现栈的操作，那我们肯定要新建一个栈，有了这个栈，我们肯定要做一些彰显出栈特性的事情————出栈，入栈。还有我们常见的操作，判断是否为空，判断栈的大小等等。
以下是我们要实现的方法：
- Stack()创建一个空栈。不传任何参数，返回空栈。
- push(item)将一个元素添加到栈的顶端。它需要一个参数 item，且无返回值。
- pop()将栈顶端的元素移除。它不需要参数，但会返回顶端的元素，并且修改栈的内容。
- peek()返回栈顶端的元素，但是并不移除该元素。它不需要参数，也不会修改栈的内容。
- isEmpty()检查栈是否为空。它不需要参数，且会返回一个布尔值。
- size()返回栈中元素的数目。它不需要参数，且会返回一个整数。
栈的定义
代码语言：txt复制class Stack:
def __init__(self):
self.items = []定义一个 stack 类来告诉计算机，我们现在定义了一个全新的类型叫做 stack ，每个类有一个定义方法即 init() ,我们使用 init 方法来定义栈的一些属性。我们新建一个栈，栈中最重要的就是元素，多个元素构成栈，而一开始当我们没有向栈中放入任何元素时，栈是空的，因此有 self.items = []，我们定义了一个空栈来作为栈的初始化。
栈是否为空
既然栈存在，我们就可以进行栈有无的判断，我们也像之前的数据结构类型一样，引入 isEmpty() 方法来判断栈中是否有元素，没有元素则为空栈，返回 true ；包含有元素，则说明栈不为空，返回 false。
代码语言：txt复制def isEmpty(self):
return self.items == []栈的大小
栈的大小实际上就是判断栈中有多少元素，而我们使用列表来进行栈的实现，因此我们只需要使用 len() 方法计算引入的列表的长度即可判断栈中元素的多少了，即栈的大小。
代码语言：txt复制def size(self):
return len(self.items)入栈操作
现在我们既可以判断栈中是否有元素，又可以判断栈的大小了，那么接下来就要实现栈最主要的两个操作了，入栈和出栈。
进行入栈操作我们就要想到，既然要把元素加入到栈中，那么我们就要传入一个参数去表示要加入到栈中的元素，然后将这个参数加入到栈中即可。
代码语言：txt复制def push(self, item):
self.items.append(item)我们传入一个 item 参数，为我们要加入到栈中的元素，然后将其加入到我们引入的 items 列表中即可完成栈中元素的加入了。
出栈操作
既然有元素加入到栈中，那我们就可以将元素从栈中删除，因此我们有了出栈的操作，出栈操作一般的思维是这样的：我们让栈顶的元素弹出，同时也要告诉大家，我弹出的是哪个元素。
因此要返回弹出的那个元素。
代码实现为：
代码语言：txt复制def pop(self):
return self.items.pop()使用列表中的 pop方法，返回列表末尾的那个元素，并将该元素从列表中删除，实现出栈。
查看栈顶
我们的栈操作中通常还包含一项查看栈顶元素的操作，因为我们在此将引入的列表末尾视为栈顶，因此我们只需要返回所引入的列表的最后一个元素即可。
代码语言：txt复制def peek(self):
return self.items[len(self.items)-1]整体的代码如下：
代码语言：txt复制class Stack:
def __init__(self):
self.items = []
def isEmpty(self):
return self.items == []
def size(self):
return len(self.items)
def push(self, item):
self.items.append(item)
def pop(self):
return self.items.pop()
def peek(self):
return self.items[len(self.items)-1]总结
恭喜你又学完了一个知识点，栈是一个后进先出的数据类型，它有两个非常主要的操作，进栈和出栈：
- 进栈：将资料放入栈的顶端，栈的顶端移到新放入的资料。
- 出栈：将堆栈顶端资料移除，堆栈顶端移到移除后的下一笔资料。
它可以用数组或者链表来实现，而由于 python 的特殊性，我们常使用列表来实现栈的操作。
与栈相对的有队列，队列是一种先进先出的数据类型，我们下次会进行讲解。
