前言：什么是抽象数据类型
从数据类型讲起
为什么会提出数据类型呢？
废话一样的回答：当然是为了方便。
我们计算一个1+1的表达式，需要开辟一定的空间。假使没有int，float等数据类型的概念，那么我们为了节省空间，就需要手动的为这个表达式指定要用多少的空间，不会多用也不会浪费。
抽象是抽取出事物具有的普遍性本质，是对事物的一个概括，是一种思考问题的方式。
但是太麻烦了，如果我们对数据进行分类，将具有同样空间的数据抽象概括一下，成为同一种数据。于是分出了不同的数据类型。那么在对不同的数据类型进行操作时，就比较方便了。
我们对已有的数据类型抽象，就有了抽象数据类型。
听着比较绕，但是比较好理解。比如，我们对不同的数据，1,2, 或0.1,0.2 进行抽象，就有了数据类型。我们再进一步对数据类型进行抽象，于是就会有抽象数据类型。
抽象数据类型的定义：抽象数据类型（ADT）是指一个数学模型及定义在该模型上的一组操作。
下面的，栈，栈的操作，都属于抽象数据类型。
一、用Python实现栈
1.1 栈的基本操作
一般，栈的抽象数据类型（栈的定义，对栈的操作）有以下几种：
Stack() 创建一个空的新栈。 它不需要参数，并返回一个空栈。
push(item)将一个新项添加到栈的顶部。它需要 item 做参数并不返回任何内容。
pop() 从栈中删除顶部项。它不需要参数并返回 item 。栈被修改。
peek() 从栈返回顶部项，但不会删除它。不需要参数。 不修改栈。
isEmpty() 测试栈是否为空。不需要参数，并返回布尔值。
size() 返回栈中的 item 数量。不需要参数，并返回一个整数。
1.2 用Python实现栈
当我们给抽象数据类型一个物理实现时，我们将 实现 称为数据结构。
在 Python 中，与任何面向对象编程语言一样，抽象数据类型（如栈）的选择的实现是创建一个新类。栈操作实现为类的方法。
此外，为了实现作为元素集合的栈，使用由 Python 提供的原语集合的能力是有意义的。 我们将使用列表作为底层实现。
以下栈实现代码假定列表的结尾将保存栈的顶部元素。随着栈增长（push 操作），新项将被添加到列表的末尾。 pop 也操作列表末尾的元素。
class Stack:
def __init__(self):
#初始化，把空列表作为实例的一个属性
self.items = []
def isEmpty(self):
return self.items == []
def push(self,data):
self.items.append(data)
def pop(self):
self.items.pop()
def peek(self):
return self.items[len(self.items)-1]
def size(self):
return len(self.items)
以上就是栈的实现代码。我们日常使用栈时，可以从pythonds包导入栈类。栈类的代码实现就是上述代码
from pythonds.basic.stack import Stack
s=Stack()
二、用Python实现队列
队列，先进先出。我们同样会用list数据类型来实现队列
我们需要决定列表的哪一端做队尾，哪一端用来做队首。（这个应该不是唯一的，只不过在实现添加或者移除数据项方法时，会有些麻烦罢了。）
下面的一段代码设定队列的队尾在 list的0位置，这使得我们能够用list的insert来向队列的队尾添加新的元素。
self.item.insert(0,item)
而pop操作则可以用来移除队首的元素（也就是列表的最后一个元素）
self.items.pop()
完整代码：
class Queue:
def __init__(self):
self.items = []
def isEmpty(self):
return self.items == []
def enqueue(self, item):
self.items.insert(0, item)
def dequeue(self):
return self.items.pop()
def size(self):
return len(self.items)
