Python双端队列实现回文检测代码示例本篇文章小编给大家分享一下

本篇文章小编给大家分享一下Python双端队列实现回文检测代码示例，文章代码介绍的很详细，小编觉得挺不错的，现在分享给大家供大家参考，有需要的小伙伴们可以来看看。
一、双端队列
双端队列 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 中包含数据项的个数。
定义双端队列，代码实现如下：
class Deque:def __init__(self):# 创建空的双端队列self.items = []def is_empty(self):# 判断双端队列是否为空return self.items == []def add_front(self, item):# 从队首加入元素self.items.append(item)def add_tail(self, item):# 从队尾加入元素self.items.insert(0, item)def remove_front(self):# 从队首删除元素if self.is_empty():raise Exception('Queue is empty')return self.items.pop()def remove_tail(self):# 从队尾删除元素if self.is_empty():raise Exception('Queue is empty')return self.items.pop(0)def get_size(self):# 获取双端队列元素数量return len(self.items) 操作复杂度：add_front / remove_front ， O(1)；add_tail / remove_tail ， O(n) 。
二、回文检测
“回文词” 指正读和反读都一样的词，如radar、bob、toot；中文：“上海自来水来自海上” ， “山东落花生花落东山” 。
用双端队列很容易解决 “回文词” 问题，先将需要判定的词从队尾加入Deque ，再从两端同时移除字符判定是否相同，直到 Deque 中剩下 0 个或 1 个字符。
算法实现如下：
def palindrome_check(string):# 回文检测str_deque = Deque()for item in string:str_deque.add_front(item)check_flag = Truewhile str_deque.get_size() > 1 and check_flag:left = str_deque.remove_front()# 队尾移除right = str_deque.remove_tail()# 队首移除if left != right:# 只要有一次不相等不是回文check_flag = False# 判断完一遍check_flag为True是回文return check_flagprint(palindrome_check("radar"))print(palindrome_check("abcbac"))print(palindrome_check("上海自来水来自海上"))
文章图片

补充
Python还可以通过双游标判断字符串是否是回文串
从字符串s两端指定两个游标low ， high
如果low游标指向了非字母和数字（即空格和符号）,那么low游标往后移一位；
如果high游标指向了非字母和数字（即空格和符号）,那么high游标往前移一位；
直至low和high都指向了数字或字母，此时进行比较，是否相同。
如果比较的结果是True ，则low往后移一位， high往前移一位
如果比较的结果是False ，则直接返回False