这篇文章给大家分享的是有关Python中如何实现双端队列Dequeue的内容。小编觉得挺实用的,因此分享给大家做个参考,一起跟随小编过来看看吧。
双端队列Dequeue
双端队列是一种有序的数据集,与队列相似,但双端队列的两端都可以作为队首和队尾(即数据在两端都可以删除和插入)
某种意义上来说,双端队列Dequeue集合了栈和队列的功能,Dequeue既可以实现栈也可以实现队列
双端队列的操作:
Dequeue() | 创建一个双端队列 |
addFront() | 队首加入数据 |
addFear() | 队尾加入数据 |
removeFront() | 队首删除数据 |
removeFear() | 队尾删除数据 |
size() | 双端队列元素个数 |
isEmpty() | 是否为空 |
双端队列使用实例:
双端队列代码:
双端队列应用——“回文词”判定
“回文词”:正读和反读都一样的词
例:radar(雷达),madam,foot,“上海自来水来自海上”,“山东落花生花落”
算法:利用双端队列Dequeue,先将字符串加入双端队列,再从两端开始移除判断是否相同,最后剩一个字符
代码:
所有代码:
class Dequeue():
"""双端队列"""
def __init__(self):
self.items = []
def addFront(self, item):
self.items.append(item)
def addFear(self, item):
self.items.insert(0, item)
def removeFront(self):
"""时间复杂O(1)"""
return self.items.pop()
def removeFear(self):
"""时间复杂度O(n)"""
return self.items.pop(0)
def size(self):
return len(self.items)
def isEmpty(self):
return self.items == []
def check_backwords(backwords):
"""回文词判断"""
check_dequeue = Dequeue()
mark = True
for word in backwords:
check_dequeue.addFront(word)
while check_dequeue.size() > 1 and mark:
# 从两端取出数据进行对比
check1 = check_dequeue.removeFear()
check2 = check_dequeue.removeFront()
if check1 != check2:
mark = False
return mark
感谢各位的阅读!关于“Python中如何实现双端队列Dequeue”这篇文章就分享到这里了,希望以上内容可以对大家有一定的帮助,让大家可以学到更多知识,如果觉得文章不错,可以把它分享出去让更多的人看到吧!
原创文章,作者:carmelaweatherly,如若转载,请注明出处:https://blog.ytso.com/tech/opensource/219924.html