1、用python现实双端队列
通过创建一个新类型来实现双端队列抽象数据类型。Python列表再一次提供了很多方便
的方法来帮助我们构建双端队列。我们假设双端队列的后端是列表的位置0处。
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)
removeFront使用pop方法移除列表中的最后一个元素，removeRear则使用pop（0）方法移除列表中的第
一个元素同理，之所以addRear使用insert方法，是因为append方法只能在列表的最后添加元素。
2、回文检测器
运用双端队列可以解决一个非常有趣的经典问题：回文问题。回文是指从前往后续和从后往前读都一样的
字符串，例如radar、toot、以及madam。我们将构建一个程序，它接受一个字符串并且检测其是否为回文。
由于可以从前后两端移除元素，因此我们能够比较两个元素，并且只有在二者相等时才继续。如果一直匹
配第一个和最后一个元素，最终会处理完所有的字符（如果字符数是偶数），或者剩下只有一个元素双端队列
（如果字符数是奇数）。任意一种结果都表明输入字符串是回文。
from pythonds.basic 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("abba"))
原文：https://www.cnblogs.com/mtfan01/p/14715731.html