【数据结构与算法python】双端队列的python实现

1、双端队列的介绍 双端队列Deque是一种有次序的数据集，跟队列相似，其两端可以称作“首”“尾”端，但deque中数据项既可以从队首加入，也可以从队尾加入；数据项也可以从两端移除。

2、双端队列的性质 双端队列并不具有内在的LIFO或者FIFO特性，某种意义上说，双端队列集成了栈和队列的能力

3、双端队列的基本操作

class Deque:
	# 创建一个空双端队列
    def __init__(self):
        self.items = []
	# 判断deque是否为空
    def isEmpty(self):
        return self.items == []
	# 将item加入队首
    def addFront(self, item):
        self.items.append(item)
	# 将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)
	# 返回deque中包含数据项的个数
    def size(self):
        return len(self.items)

4、例子（回文词问题）

def palchecker(aString):
    chardeque = Deque()

    for ch in aString:
        chardeque.addRear(ch)

    stillEqual = True

    while chardeque.size() > 1 and stillEqual:
        first = chardeque.removeFront()
        last = chardeque.removeRear()
        if first != last:
            stillEqual = False

    return stillEqual

print(palchecker("lsdkjfskf"))
print(palchecker("radar"))