双端队列Deque是一种有次序的数据集，跟队列相似，其两端可以称作“首”“尾”端。但deque中数据项既可以从队首加入，也可以从队尾加入；数据项也可以从两端移除。
从某种意义上说，双端队列集成了栈和队列的能力。 但是双端队列并不具有LIFO和FIFO的特性。
双端队列
双端队列Deque定义的操作如下：
Deque()：创建一个空的双端队列，无参数，返回值是空队列。
addFront(item)：在队首添加入一个元素，参数是数据项，无返回值。
addRear(item)：在队尾添加入一个元素，参数是数据项，无返回值。
removeFront()：删除队首的元素，不需要参数，返回值是被删除的元素，队列本身有变化。
removeRear()：删除队尾的元素，不需要参数，返回值是被删除的元素，队列本身有变化。
isEmpty()：检测队列是否为空。无参数，返回布尔值。
size()：返回队列元素的个数。无参数，返回一个整数。
用List实现Deque，List下标0作为deque的尾端，List下标-1作为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)
其中addFront和removeFront的操作复杂度为O(1)，而addRear和removeRear的操作复杂度为O(n)。
“回文词”判定
“回文词”指正读和反渎都一样的词，如radar、madam、toot，而用双端队列很容易能解决“回文词”问题。
首先将需要判定的词从队尾加入deque，再从两端同时移除字符判定是否相同，知道deque中剩下0个或1个字符。
回文词判断
回文词判定的算法如下：
代码
但是其实python还有更简单的方法判定回文词，如下：
s = input()
a = reversed(list(s))
if list(a) == list(s):
print('是回文')
else:
print('不是回文')
网友评论