Python双端队列之回文词判定

- 日理万妓 2022-02-19 07:55 182阅读 0赞

**双端队列(Deque)**：由一系列有序的元素组织而成，元素可以从队首或队尾插入、删除。

Python自带Deque模块，使用时需引用from collections import deque。

**回文词**：指的是正读和反读都一样的词，如：radar、toot 和 madam，还有一些古诗词。如：

**《两相思》【宋】李禺  
思妻诗**  
枯眼望遥山隔水，往来曾见几心知？  
壶空怕酌一杯酒，笔下难成和韵诗。  
途路阻人离别久，讯音无雁寄回迟。  
孤灯夜守长寥寂，夫忆妻兮父忆儿。  
**【倒读】  
思夫诗**  
儿忆父兮妻忆夫，寂寥长守夜灯孤。  
迟回寄雁无音讯，久别离人阻路途。  
诗韵和成难下笔，酒杯一酌怕空壶。  
知心几见曾来往，水隔山遥望眼枯。

**完整代码：**

# 自定义双端队列类
    class Deque(object):
    	def __init__(self):							#初始化空队列
    		self.items = []
    
    	def isEmpty(self):							#是否为空
    		return self.items == []
    
    	def addFront(self, item):					#从队首入队，队首在右侧
    		self.items.append(item)
    
    	def removeFront(self):						#从队首出队，列表最后一个
    		return self.items.pop()
    
    	def addRear(self, item):					#从队尾入队，队尾在左侧，索引为0
    		self.items.insert(0, item)
    
    	def removeRear(self):						#从队尾出队，列表第一个
    		return self.items.pop(0)
    
    	def size(self):								#查看队列的大小
    		return len(self.items)
    
    # 判断是否是回文词
    def back_to_word_check(s1):
    	deque = Deque()								#实例化双端队列
    	[deque.addRear(i) for i in s1]				#将字符串从队尾入队
    	while deque.size() > 1:						#队列长度>1，则循环，否则为0或1个，则说明是回文词
    		first = deque.removeFront()				#从队首出队一个
    		last = deque.removeRear()				#从队尾出队一个
    		if first != last:						#若不相同，则
    			return False 						#非回文词
    	return True 								#回文词
    
    s1 = '枯眼望遥山隔水往来曾见几心知壶空怕酌一杯酒笔下难成和韵诗途路阻人离别久讯音无雁寄回迟孤灯夜守长寥寂夫忆妻兮父忆儿儿忆父兮妻忆夫寂寥长守夜灯孤迟回寄雁无音讯久别离人阻路途诗韵和成难下笔酒杯一酌怕空壶知心几见曾来往水隔山遥望眼枯'
    print(back_to_word_check(s1))

**结果为：**

True