一、双端队列
双端队列 Deque 是一种有次序的数据集，跟队列相似，其两端可以称作"首" 和 "尾"端，但 Deque 中数据项既可以从队首加入，也可以从队尾加入；数据项也可以从两端移除。某种意义上说，双端队列集成了栈和队列的能力。
但双端队列并不具有内在的 LIFO 或者 FIFO 特性，如果用双端队列来模拟栈或队列，需要由使用者自行维护操作的一致性。
用 Python 实现抽象数据类型Deque，Deque定义的操作如下：
- Deque()：创建一个空双端队列；
- add_front(item)：将 item 加入队首；
- add_tail(item)：将 item 加入队尾；
- remove_front()：从队首移除数据项，返回值为移除的数据项；
- remove_tail()：从队尾移除数据项，返回值为移除的数据项；
- is_empty()：返回 Deque 是否为空；
- get_size()：返回 Deque 中包含数据项的个数。
定义双端队列，代码实现如下：
classDeque: def__init__(self): # 创建空的双端队列self.items= [] defis_empty(self): # 判断双端队列是否为空returnself.items== [] defadd_front(self, item): # 从队首加入元素 self.items.append(item) defadd_tail(self, item): # 从队尾加入元素 self.items.insert(0, item) defremove_front(self): # 从队首删除元素 ifself.is_empty(): raiseException('Queue is empty') returnself.items.pop() defremove_tail(self): # 从队尾删除元素 ifself.is_empty(): raiseException('Queue is empty') returnself.items.pop(0) defget_size(self): # 获取双端队列元素数量returnlen(self.items)
操作复杂度：add_front / remove_front，O(1)；add_tail / remove_tail，O(n)。
二、回文检测
“回文词” 指正读和反读都一样的词，如radar、bob、toot；中文：“上海自来水来自海上”，“山东落花生花落东山”。
用双端队列很容易解决 “回文词” 问题，先将需要判定的词从队尾加入Deque，再从两端同时移除字符判定是否相同，直到 Deque 中剩下 0 个或 1 个字符。
算法实现如下：
defpalindrome_check(string): # 回文检测str_deque=Deque() foriteminstring: str_deque.add_front(item) check_flag=Truewhilestr_deque.get_size() >1andcheck_flag: left=str_deque.remove_front() # 队尾移除right=str_deque.remove_tail() # 队首移除ifleft!=right: # 只要有一次不相等 不是回文check_flag=False# 判断完一遍 check_flag为True 是回文returncheck_flagprint(palindrome_check("radar")) print(palindrome_check("abcbac")) print(palindrome_check("上海自来水来自海上"))
