Python中如何实现双端队列Dequeue

这篇文章给大家分享的是有关Python中如何实现双端队列Dequeue的内容。小编觉得挺实用的,因此分享给大家做个参考,一起跟随小编过来看看吧。

 

双端队列Dequeue

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

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

Python中如何实现双端队列Dequeue

双端队列的操作:

Dequeue() 创建一个双端队列
addFront() 队首加入数据
addFear() 队尾加入数据
removeFront() 队首删除数据
removeFear() 队尾删除数据
size() 双端队列元素个数
isEmpty() 是否为空

双端队列使用实例:

Python中如何实现双端队列Dequeue

双端队列代码:

Python中如何实现双端队列Dequeue

Python中如何实现双端队列Dequeue
 

 

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

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

例:radar(雷达),madam,foot,“上海自来水来自海上”,“山东落花生花落”

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

代码:

Python中如何实现双端队列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

(0)
上一篇 2022年1月2日 14:27
下一篇 2022年1月2日 14:27

相关推荐

发表回复

登录后才能评论