双端队列
双端队列（ deque 或 double-ended queue）与队列类似，也是一系列元素的有序组合。其两端称为队首（ front）和队尾（ rear），元素在到达两端之前始终位于双端队列中。与队列不同的是，双端队列对元素添加和删除的限制不那么严格，元素可以从两端插入，也可以从两端删除。 可以说，双端队列这种混合的线性数据结构拥有栈和队列各自拥有的所有功能。下图是一个由 Python 数据对象构成的双端队列。 应当指出，双端队列虽然具备栈和队列的许多特征，但其中的数据项不满足严格的“后进先出”或“先进先出”顺序，这使得插入和删除操作的规律性需要由用户自己维持。——problem solving with algorithms and data structures using python
定义双端队列的操作
Deque 抽象数据类型双端队列(Deque)由以下一些结构和操作来定义。如前文所述，双端队列由一系列有序的元素组织而成，元素可以从队首或队尾插入、 删除。下面是双端队列的一些操作。
- Deque() 创建一个空双端队列，无参数，返回值为 Deque 对象。
- addFront(item) 在队首插入一个元素，参数为待插入元素，无返回值。
- addRear(item) 在队尾插入一个元素，参数为待插入元素，无返回值
- removeFront() 在队首移除一个元素，无参数，返回值为该元素。双端队列会被改变。
- removeRear() 在队尾移除一个元素，无参数，返回值为该元素。双端队列会被改变。
- isEmpty() 判断双端队列是否为空，无参数，返回布尔值。
- size() 返回双端队列中数据项的个数，无参数，返回值为整型数值。
使用python3实现双端队列
建立一个新的类来实现抽象数据类型 Deque。我们还是使用 Python 中List-列表提供的一套非常好的方法来实现 Deque 的细节。我们实现的Deque假设队尾在列表的 0 位置。
class TestDeque:
def __init__(self):
self.items = []
def isEmpty(self):
return self.items == []
def addFront(self, item):
self.items.append(item)
def addRear(self, item):
self.items.insert(0, item)
def removeFront(self):
return self.items.pop()
//pop()表示删除列表的最后一个元素
def removeRear(self):
return self.items.pop(0)
////pop()表示删除列表的第一个元素
def size(self):
return len(self.items)往期精彩：