Deque是与队列类似的项的有序集合。它有两个端部，首部和尾部，并且项在集合中保持不变。deque 不同的地方是添加和删除项是非限制性的。可以在前面或后面添加新项。同样，可以从任一端移除现有项。在某种意义上，这种混合线性结构提供了单个数据结构中的栈和队列的所有能力。 Figure 1 展示了一个 Python 数据对象的 deque 。
Deque抽象数据类型
下面给出了 deque 操作。
Deque() 创建一个空的新 deque。它不需要参数，并返回空的 deque。addFront(item) 将一个新项添加到 deque 的首部。它需要 item 参数 并不返回任何内容。addRear(item) 将一个新项添加到 deque 的尾部。它需要 item 参数并不返回任何内容。removeFront() 从 deque 中删除首项。它不需要参数并返回 item。deque 被修改。removeRear() 从 deque 中删除尾项。它不需要参数并返回 item。deque 被修改。isEmpty() 测试 deque 是否为空。它不需要参数，并返回布尔值。size() 返回 deque 中的项数。它不需要参数，并返回一个整数。我们假设 d 是已经创建并且当前为空的 deque，则 Table 1 展示了一系列 deque 操作的结果。
Python实现Deque
class Deque: 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() def removeRear(self): return self.items.pop(0) def size(self): return len(self.items)在这个实现中，从前面添加和删除项是 O(1)，而从后面添加和删除是 O(n)。
回文检查
回文是一个字符串，读取首尾相同的字符，例如， radar toot madam 。
我们可以直接删除并比较首尾字符，只有当它们匹配时才继续。如果可以持续匹配首尾字符，我们最终要么用完字符，要么留出大小为 1 的deque，取决于原始字符串的长度是偶数还是奇数。在任一情况下，字符串都是回文。
from pythonds.basic.deque import Deque def palchecker(aString): chardeque = Deque() for ch in aString: chardeque.addRear(ch) stillEqual = True while chardeque.size() > 1 and stillEqual: first = chardeque.removeFront() last = chardeque.removeRear() if first != last: stillEqual = False return stillEqual print(palchecker("lsdkjfskf")) print(palchecker("radar"))
