双端队列的实现与应用

抽象数据类型dequeue

一、实现

• 方法1

from collections import dequeue

• 方法2
  基于list

class Dequeue():
	def __init__(self):
		self.items = []

	def addFront(self, item):
		"""右侧为front"""
		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 isEmpty(self):
		return self.items == []

	def size(self):
		return len(self.items)

二、应用：判断是否为回文字符串

from dequeue import Dequeue

def pal_checker(mystr):
	"""检查字符串是否为回文字符串，即正序等于逆序字符串"""
	dq = Dequeue()
	mylist = [i  for i in mystr]
	indicator = True
	for item in mylist:
		dq.addRear(item)
	for i in range(dq.size()//2):
		fornt = dq.removeFront()
		rear = dq.removeRear()
		if fornt != rear:
			indicator = False
			break
	return indicator

if __name__ == '__main__':
	print(pal_checker("lsdkjfskf"))
	print(pal_checker("radar"))

类似balance问题，用stack也可求解