双端队列是指首尾都能进出元素的线性数据结构。尽管进出是任意的，但数据在双端队列中的排列顺序却是不能改变的，这一点与普通队列是一样的
我们同样可以用列表为基础实现双端队列。这里，我们将列表的最后一个元素作为队首，将第一个元素作为队尾。这也就意味着，尾部出入队的时间复杂度是O(n)，首部出入队的时间复杂度是O(1)。
class DeQueue():
# DeQueue() 创建一个空的新双端队列。 它不需要参数，并返回一个空队列。
def __init__(self):
self.items = []
# enqueue_end(item) 将新项添加到队尾。 它需要 item 作为参数，并不返回任何内容。
def enqueue_end(self, item):
self.items.insert(0, item)
# dequeue_end() 从队尾移除项。它不需要参数并返回 item。 队列被修改。
def dequeue_end(self):
item = self.items.pop(0)
return item
# enqueue_head(item) 将新项添加到队首。 它需要 item 作为参数，并不返回任何内容。
def enqueue_head(self, item):
self.items.append(item)
# dequeue_head() 从队首移除项。它不需要参数并返回 item。 队列被修改。
def dequeue_head(self):
item = self.items.pop()
return item
# isEmpty() 查看队列是否为空。它不需要参数，并返回布尔值。
def isEmpty(self):
return 0 == len(self.items)
# size() 返回队列中的项数。它不需要参数，并返回一个整数。
def size(self):
length = len(self.items)
return length
回文数检查
回文数检查是数据结构中的常见任务，这一任务可以应用双端队列直观有效地完成。
将待检查的字符串按顺序载入队列，首尾两侧弹出并比较，出现不一致时则判断为不是回文数。当队列为空或只剩一个元素是可以判断为回文数。
class DeQueue():
# DeQueue() 创建一个空的新双端队列。 它不需要参数，并返回一个空队列。
def __init__(self):
self.items = []
# enqueue_end(item) 将新项添加到队尾。 它需要 item 作为参数，并不返回任何内容。
def enqueue_end(self, item):
self.items.insert(0, item)
# dequeue_end() 从队尾移除项。它不需要参数并返回 item。 队列被修改。
def dequeue_end(self):
item = self.items.pop(0)
return item
# enqueue_head(item) 将新项添加到队首。 它需要 item 作为参数，并不返回任何内容。
def enqueue_head(self, item):
self.items.append(item)
# dequeue_head() 从队首移除项。它不需要参数并返回 item。 队列被修改。
def dequeue_head(self):
item = self.items.pop()
return item
# isEmpty() 查看队列是否为空。它不需要参数，并返回布尔值。
def isEmpty(self):
return 0 == len(self.items)
# size() 返回队列中的项数。它不需要参数，并返回一个整数。
def size(self):
length = len(self.items)
return length
# 检查传入的字符串是否为回文数，是则返回true，不是则返回false
def isPalindrome(checking_string):
dequeue = DeQueue() #创建一个空的双端队列
for ch in checking_string:
dequeue.enqueue_head(ch) #将字符串按照字符逐个载入双端队列
while dequeue.size()>1:
head_char = dequeue.dequeue_head() #弹出队首字符
end_char = dequeue.dequeue_end() #弹出队尾字符
if head_char != end_char : #首位元素不等返回false
return False
return True #列标为空或者只剩一个元素时，为回文序列，返回true
def main():
word_list = ['random','carrac','doooood','slefles']
for word in word_list:
print("%s ---- %s"%( isPalindrome(word), word))
print("-----------------")
if __name__ == "__main__":
main()
运行结果如下：
False ---- random
-----------------
True ---- carrac
-----------------
True ---- doooood
-----------------
False ---- slefles
-----------------
可以看出，实验结果是正确的。
