这篇文章主要介绍了Python实现的数据结构与算法之双端队列,详细讲述了双端队列的概念、功能、定义及Python实现与使用双端队列的相关技巧,非常具有实用价值,需要的朋友可以参考下
本文实例讲述了Python实现的来源gaodai#ma#com搞*!代#%^码网数据结构与算法之双端队列。分享给大家供大家参考。具体分析如下：
一、概述
双端队列（deque，全名double-ended queue）是一种具有队列和栈性质的线性数据结构。双端队列也拥有两端：队首（front）、队尾（rear），但与队列不同的是，插入操作在两端（队首和队尾）都可以进行，删除操作也一样。
二、ADT
双端队列ADT（抽象数据类型）一般提供以下接口：
① Deque() 创建双端队列
② addFront(item) 向队首插入项
③ addRear(item) 向队尾插入项
④ removeFront() 返回队首的项，并从双端队列中删除该项
⑤ removeRear() 返回队尾的项，并从双端队列中删除该项
⑥ empty() 判断双端队列是否为空
⑦ size() 返回双端队列中项的个数
双端队列操作的示意图如下：
三、Python实现
在Python中，有两种方式可以实现上述的双端队列ADT：使用内建类型list、使用标准库collections.deque（其实collections.deque就是Python中双端队列的标准实现）。
两种方式的不同主要体现在性能上（具体参考 collections.deque | TimeComplexity）：
操作|实现方式 list collections.deque ----------------------------------------- addFront O(n) O(1) ----------------------------------------- addRear O(1) O(1) ----------------------------------------- removeFront O(n) O(1) ----------------------------------------- removeRear O(1) O(1)
1、使用内建类型list
#!/usr/bin/env python # -*- coding: utf-8 -*- class Deque: def __init__(self): self.items = [] def addFront(self, item): self.items.insert(0, item) def addRear(self, item): self.items.append(item) def removeFront(self): return self.items.pop(0) def removeRear(self): return self.items.pop() def empty(self): return self.size() == 0 def size(self): return len(self.items)
2、使用标准库collections.deque
#!/usr/bin/env python # -*- coding: utf-8 -*- from collections import deque class Deque: def __init__(self): self.items = deque() def addFront(self, item): self.items.appendleft(item) def addRear(self, item): self.items.append(item) def removeFront(self): return self.items.popleft() def removeRear(self): return self.items.pop() def empty(self): return self.size() == 0 def size(self): return len(self.items)
四、应用
回文（palindrome）是正读反读都一样的单词或句子，是一种修辞方式和文字游戏。
英文例子：
madam
able was i ere i saw elba
中文例子：
花非花
人人为我、我为人人
如果要实现一个 回文验证算法（验证一个给定的字符串是否为回文），使用Deque类将非常容易：将字符串存储到双端队列，同时取出首尾字符并比较是否相等，只要有一对字符不等，则该字符串不是回文；若全部相等，则该字符串为回文。具体代码如下：
#!/usr/bin/env python # -*- coding: utf-8 -*- def palchecker(aString): chardeque = Deque() for ch in aString: chardeque.addRear(ch) while chardeque.size() > 1: first = chardeque.removeFront() last = chardeque.removeRear() if first != last: return False return True if __name__ == '__main__': str1 = 'able was i ere i saw elba' print('"%s" is%s palindrome' % (str1, '' if palchecker(str1) else ' not')) str2 = u'人人为我、我为人人' print(u'"%s"%s是回文' % (str2, u'' if palchecker(str2) else u'不')) str3 = u"What's wrong 怎么啦" print(u'"%s"%s是回文' % (str3, u'' if palchecker(str3) else u'不'))
运行结果：
$ python palchecker.py "able was i ere i saw elba" is palindrome "人人为我、我为人人"是回文 "What's wrong 怎么啦"不是回文
希望本文所述对大家的Python程序设计有所帮助。
以上就是Python实现的数据结构与算法之双端队列详解的详细内容，更多请关注gaodaima搞代码网其它相关文章！
转载请注明原文链接：Python实现的数据结构与算法之双端队列详解
