Python数据结构与算法——双端队列Dequeue

Z时代
2024-01-10
分类：综合

coding

点击上方

蓝字

关注我们

双端队列Dequeue

双端队列是一种有序的数据集，与队列相似，但双端队列的两端都可以作为队首和队尾（即数据在两端都可以删除和插入）

某种意义上来说，双端队列Dequeue集合了栈和队列的功能，Dequeue既可以实现栈也可以实现队列

双端队列的操作：

Dequeue()

创建一个双端队列

addFront()

队首加入数据

addFear()

队尾加入数据

removeFront()

队首删除数据

removeFear()

队尾删除数据

size()

双端队列元素个数

isEmpty()

是否为空

双端队列使用实例：

双端队列代码：

双端队列应用——“回文词”判定

“回文词”：正读和反读都一样的词

例：radar（雷达），madam，foot，“上海自来水来自海上”，“山东落花生花落”

算法：利用双端队列Dequeue，先将字符串加入双端队列，再从两端开始移除判断是否相同，最后剩一个字符

代码：

所有代码：

python">classDequeue():"""双端队列"""
def__init__(self):        self.items = []
defaddFront(self, item):        self.items.append(item)
defaddFear(self, item):        self.items.insert(0, item)
defremoveFront(self):"""时间复杂O(1)"""return self.items.pop()
defremoveFear(self):"""时间复杂度O(n)"""return self.items.pop(0)
defsize(self):return len(self.items)
defisEmpty(self):return self.items == []

defcheck_backwords(backwords):"""回文词判断"""    check_dequeue = Dequeue()    mark = True
for word in backwords:        check_dequeue.addFront(word)
while check_dequeue.size() > 1and mark:# 从两端取出数据进行对比        check1 = check_dequeue.removeFear()        check2 = check_dequeue.removeFront()
if check1 != check2:            mark = False
    return mark