京公网安备 11010802034615号
经营许可证编号:京B2-20210330
Python实现的数据结构与算法之双端队列详解
本文实例讲述了Python实现的数据结构与算法之双端队列。分享给大家供大家参考。具体分析如下:
一、概述
双端队列(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程序设计有所帮助。
数据分析咨询请扫描二维码
若不方便扫码,搜微信号:CDAshujufenxi
CDA数据分析师 出品 作者:李诗怡 多表进阶与 DDL/DML 连接 · 子查询 · 合并 · 建表与书写规范 ” 三、DQL 多表进阶:连 ...
2026-11-20 前面讲了怎么搭指标体系,但很多团队卡在最后一步:高层定了一个漂亮的目标,往下一层层写进周报,最后却落不到任何人的具体 ...
2026-11-20 很多团队做数据分析的现状是:老板要一个数就拉一个数,周报里堆满了 GMV、DAU、转化率,却没人说得清这些数之间是什么关系 ...
2026-11-20这周你大概又经历过一次:报表自己跑了,SQL 让 AI 写了,连周报初稿都不用自己动手。你一边松口气,一边心里发慌——那我还剩什 ...
2026-11-20 做产品立项、写商业计划书、规划市场进入策略时,"市场调研"和"竞品分析"几乎总是被绑在一起说,甚至被当成同一件事。但实际 ...
2026-11-19 在做数据治理、搭数据中台或者梳理数据库表结构时,"主数据"和"参考数据"是被提及频率最高、也最容易被混为一谈的两个概念。 ...
2026-11-19“纲举目张,执本末从。”若想在数据分析领域有所收获,一套合适的学习教材至关重要。一套优质且契合需求的学习教材无疑是那关键 ...
2026-11-19一、什么是本体 在知识图谱和语义建模里,本体(Ontology)是对一个领域内概念、属性、关系和实例的形式化描述。它回答三个问题 ...
2026-11-18一、K-S 曲线解决什么问题 风控评分卡、客户流失模型、欺诈识别模型建好之后,最核心的一个问题是:模型能不能把"会变坏"和"不会 ...
2026-11-18核心资源推荐 CDA教材(2025):https://edu.cda.cn/goods/show/3151CDA模拟题(2025):https://edu.cda.cn/goods/show/2845CD ...
2026-11-18核心资源推荐 CDA教材(2025):https://edu.cda.cn/goods/show/3151CDA模拟题(2025):https://edu.cda.cn/goods/show/2845CD ...
2026-11-18产品上线之后,真正回答"用户是谁、想要什么、卡在哪里"的,往往不是调研问卷,而是用户留下的一条条行为记录。点击、浏览、停留 ...
2026-11-17在日常数据库开发与报表查询中,日期格式几乎是最高频的"打交道"对象:页面上要展示 yyyy-MM-dd,接口要返回 ISO 8601 字符串, ...
2026-11-17核心资源推荐 CDA教材(2025):https://edu.cda.cn/goods/show/3151CDA模拟题(2025):https://edu.cda.cn/goods/show/2845CD ...
2026-11-17一、销售行业为什么离不开大数据分析 销售行业的本质是"把合适的产品,在合适的时间,卖给合适的人,并持续复购"。传统销售靠经 ...
2026-11-16一、什么是频数分布 拿到一批连续数据(员工年龄、商品价格、考试分数、订单金额),最想先看的往往不是平均值,而是数据集中在 ...
2026-11-16教育部办公厅关于成立全国数据职业教育教学指导委员会(2026—2030年)的通知 教职成厅函〔2026〕25号 各省、自治区、直辖市教 ...
2026-11-16CDA数据分析师 出品 作者:李诗怡 基础与单表查询 四大类语言 · 数据库基础 · DQL 单表查询 ” 一、SQL 四大类语言与数据 ...
2026-11-13核心资源推荐 CDA教材(2025):https://edu.cda.cn/goods/show/3151CDA模拟题(2025):https://edu.cda.cn/goods/show/2845CD ...
2026-11-13一、问题从哪来 财务分析里算增长率,常规公式所有人都会写: 增长率本年数上年数上年数 这个公式在"上年为正"时完全成立。但一 ...
2026-11-12