用Python实现的数据结构与算法:双端队列
2024-08-31 10:22:35
一、概述
双端队列(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 怎么啦"不是回文
最新文章
- iOS 创建模型时自动生成属性
- Android QQ群:343816731 欢迎大家加入探讨
- 100735G
- EBS R12重启后无法进入登录页面
- 移动设备页面高度不足时min-height 的尴尬处理
- android 项目学习随笔十一(ListView下拉刷新提示)
- 3.5 The Lexical-Analyzer Generator Lex
- 深入浅出ES6(十五):子类 Subclassing
- BITMAP CONVERSION FROM ROWIDS
- ilog
- 重新开始学习javase_一切都是对象
- "V租房"搭建微信租房平台,让租房人发起求租需求并接收合适房源回复,提高租房效率 | 36氪
- puppet 4.4 System Requirements
- PageHeap,调试Heap问题的工具
- centos命令自动补全增强
- 小强的HTML5移动开发之路(11)——链接,图片,表格,框架
- 项目中使用sass,如何实现自动编译
- js window.location用法
- docker swarm:执行 service update 过程中服务短暂不能访问的问题
- 第二十九章 springboot + zipkin + mysql