前言：什么是抽象数据类型

参考什么是抽象数据类型

从数据类型讲起

为什么会提出数据类型呢？
废话一样的回答：当然是为了方便。

我们计算一个1+1的表达式，需要开辟一定的空间。假使没有int，float等数据类型的概念，那么我们为了节省空间，就需要手动的为这个表达式指定要用多少的空间，不会多用也不会浪费。

抽象是抽取出事物具有的普遍性本质，是对事物的一个概括，是一种思考问题的方式。

但是太麻烦了，如果我们对数据进行分类，将具有同样空间的数据抽象概括一下，成为同一种数据。于是分出了不同的数据类型。那么在对不同的数据类型进行操作时，就比较方便了。

我们对已有的数据类型抽象，就有了抽象数据类型。

听着比较绕，但是比较好理解。比如，我们对不同的数据，1,2, 或0.1,0.2 进行抽象，就有了数据类型。我们再进一步对数据类型进行抽象，于是就会有抽象数据类型。

抽象数据类型的定义：抽象数据类型（ADT）是指一个数学模型及定义在该模型上的一组操作。

下面的，栈，栈的操作，都属于抽象数据类型。

一、用Python实现栈

参考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)