网络编程
位置:首页>> 网络编程>> Python编程>> Python数据结构与算法的双端队列详解

Python数据结构与算法的双端队列详解

作者:姜学迁  发布时间:2021-10-08 13:24:27 

标签:Python,数据结构,算法,双端队列

什么是双端队列

双端队列是与队列类似的有序集合。它有一、一两端,元素在其中保持自己的位置。与队列不同的是,双端队列对在哪一端添加和移除元素没有任何限制。新元素既可以被添加到前端,也可以被添加到后端。同理,已有的元素也能从任意一端移除。某种意义上,双端队列可以是栈和队列的结合。

Python数据结构与算法的双端队列详解

值得注意的是,尽管双端队列有栈和队列的很多特性,但是它并不要求按照这两种数据结构分别规定的LIFO原则和FIFO原则操作元素。具体的排序原则取决于其使用者。

双端队列抽象数据类型由下面的结构和操作定义。如前所述,双端队列是元素的有序集合,其任何一端都允许添加或移除元素。双端队列支持以下操作:

  • 创建一个空的双端队列。它不需要参数,且会返回一个空的双端队列。 Deque()

  • 将一个元素添加到双端队列的前端。它接受一个元素作为参数,没有返回值。 addFront(item)

  • 将一个元素添加到双端队列的后端。它接受一个元素作为参数,没有返回值。 addRear(item)

  • 从双端队列的前端移除一个元素。它不需要参数,且会返回一个元素,并修改双端队列的内容。 removeFront()

  • 从双端队列的后端移除一个元素。它不需要参数,且会返回一个元素, 并修改双端队列的内容。 removeRear()

  • 检查双端队列是否为空。它不需要参数,且会返回一个布尔值。 isEmpty()

  • 返回双端队列中元素的数目。它不需要参数,且会返回一个整数。 size()

用Python实现双端队列

我们通过创建一个新类来实现双端队列抽象数据类型。Python列表再一次提供了 很多简便的方法来帮助我们构建双端队列。在下面的代码中,我们假设双端队列的后端是列表的位置0处(列表的最左端)。

class Deque:
   def __init__(self):
       self.items = []
   def isEmpty(self):
       return self.items == []
   # 往双端队列前端添加元素
   def addFront(self, item):
       self.items.append(item)
   # 往双端队列后端添加元素
   def addRear(self, item):
       self.items.insert(0, item)
   # 在前端移除双端队列元素
   def removeFront(self):
       return self.items.pop()
   # 在后端移除双端队列元素
   def removeRear(self):
       return self.items.pop(0)
   def size(self):
       return len(self.items)
   def look(self):
       print(self.items)

removeFront 使用 pop 方法移除列表中的最后一个元素,removeRear 则使用 pop(0) 方法移除列表中的第一个元素。同理,之所以 addRear 使用 insert 方法,是因为 append 方法只能在列表的最后(最右端)添加元素。

代码运行效果如下:

Python数据结构与算法的双端队列详解

运用双端队列构建回文检测器

我们现在运用双端队列解决一个非常有趣的经典问题:回文问题。回文是指从前往后读和从后往前读都一样的字符串,例如 sos、radar、toot、madam 等等。我们将构建一个程序,它接受一个字符串并且检测其是否为回文。

该问题的解决方案是使用一个双端队列来存储字符串中的字符。按照从左往右的顺序将字符串中的字符添加到双端队列的后端或前端。此时,该双端队列类似于一个普通的队列。

由于可以从前后两端移除元素,因此我们能够比较两个元素,并且只有在二者相等时才继续。如果一直匹配第一个和最后一个元素,最终会处理完所有的字符(如果字符数是偶数),或者剩下只有一个元素的双端队列(如果字符数是奇数)。任意一种结果都表明输入字符串是回文。

回文检测器代码如下:

class Deque:
   def __init__(self):
       self.items = []
   def isEmpty(self):
       return self.items == []
   def addFront(self, item):
       self.items.append(item)
   def addRear(self, item):
       self.items.insert(0, item)
   def removeFront(self):
       return self.items.pop()
   def removeRear(self):
       return self.items.pop(0)
   def size(self):
       return len(self.items)

def palchecker(aString):
   chardeque = Deque()
   for ch in aString:
       chardeque.addFront(ch)
   stillEqual = True
   while chardeque.size() > 1 and stillEqual:
       first = chardeque.removeFront()
       last = chardeque.removeRear()
       if first != last:
           stillEqual = False
   return stillEqual

来源:https://blog.csdn.net/jiang1126/article/details/123337898

0
投稿

猜你喜欢

  • 注:本文所说的视觉设计师专指网页视觉设计师。网页设计师与平面设计师都归类为设计师,其实这两个职业是跨行业的,虽然有很多设计师一直在跨行业工作
  • 一、游戏玩法介绍:24点游戏是儿时玩的主要益智类游戏之一,玩法为:从一副扑克中抽取4张牌,对4张牌使用加减乘除中的任何方法,使计算结果为24
  • re模块是python独有的匹配字符串的模块,该模块中提供的很多功能是基于正则表达式实现的,而正则表达式是对字符串进行模糊匹配,提取自己需要
  • 实际上前面我们就已经用到了图像的绘制,如:io.imshow(img)  这一行代码的实质是利用matplotlib包对图片进行绘
  • 目录一、简介思路高德地图API二、获取经纬度三、路线规划(四种方式)获取出行路线数据处理四、演示效果五、结尾一、简介路径规划中包括步行、公交
  • Flask是一个Python编写的Web 微框架,让我们可以使用Python语言快速实现一个网站或Web服务。本文参考自Flask官方文档,
  • 一、name_scopewith tf.name_scope(name):name_scope: 为了更好地管理变量的命名空间而提出的。比如
  • python聊天室很多人都觉得微信,QQ,ICQ(我不知道现在还能不能用了)都过于垃圾,想要自己做一个聊天室(或是聊天软件),所以我们可以自
  • 另外一类常用的模板标签是通过渲染 其他 模板显示数据的。 比如说,Django的后台管理界面,它使用了自定义的模板标签来显示新增/编辑表单页
  • pycharm中光标变粗,如下:原因:光标进入了改写状态。解决方法:按一下键盘中的Insert键就好了。
  • 最近把MySQL升级到了5.6版本,无意中在任务管理器发现MySQL内存占用达到400+M,这是怎么回事呢?以前的版本可没有遇到过这种情况啊
  • 查询速度慢的原因很多,常见如下几种:1、没有索引或者没有用到索引(这是查询慢最常见的问题,是程序设计的缺陷)2、I/O吞吐量小,形成了瓶颈效
  • 引言最近在做个表情包的小程序,涉及到表情包搜索功能。我们上传表情包的时候,只有一张图,怎么搜索?这个时候我们想到就是将表情包的文字提取出来,
  • 在深入研究这些库之前,首先,我们需要一个数据库来绘制数据。我们将在本完整教程中使用 tips database。让我们讨论一下这个数据库的简
  • 本文实例讲述了Python实现将数据写入netCDF4中的方法。分享给大家供大家参考,具体如下:nc文件为处理气象数据文件。用户可以去htt
  • 简单总结:1、与类和实例无绑定关系的function都属于函数(function);2、与类和实例有绑定关系的function都属于方法(m
  • 前言由与上不了学,教我们Mastercam的老师提前给我们布置了4道习题。对我们太好了,谢谢老师�没办法,干就完了。只是要求附上制作过程视频
  • 数据准备假设我们目前有两个数据表: ① 一个数据表是关于三个人他们的id以及其他的几列属性信息import pandas as pdimpo
  • 本文实例为大家分享了Vue实现无限加载瀑布流的具体代码,供大家参考,具体内容如下我做的这个瀑布流放在了一个嵌套页面里,就是类似管理后台的ma
  • 一、场景描述这里有以四张发票为例(辰哥网上搜的),将发票图片放到pic文件夹下。随便打开一张发票提取目标:金额、名称、纳税人识别号、开票人。
手机版 网络编程 asp之家 www.aspxhome.com