广告位联系
返回顶部
分享到

Python数据结构与算法的双端队列介绍

python 来源:互联网 作者:秩名 发布时间:2022-03-09 20:17:55 人浏览
摘要

什么是双端队列? 双端队列是与队列类似的有序集合。它有一前、一后两端,元素在其中保持自己的位置。与队列不同的是,双端队列对在哪一端添加和移除元素没有任何限制。新元素

什么是双端队列?

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

在这里插入图片描述

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

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

  • 创建一个空的双端队列。它不需要参数,且会返回一个空的双端队列。 Deque()
  • 将一个元素添加到双端队列的前端。它接受一个元素作为参数,没有返回值。 addFront(item)
  • 将一个元素添加到双端队列的后端。它接受一个元素作为参数,没有返回值。 addRear(item)
  • 从双端队列的前端移除一个元素。它不需要参数,且会返回一个元素,并修改双端队列的内容。 removeFront()
  • 从双端队列的后端移除一个元素。它不需要参数,且会返回一个元素, 并修改双端队列的内容。 removeRear()
  • 检查双端队列是否为空。它不需要参数,且会返回一个布尔值。 isEmpty()
  • 返回双端队列中元素的数目。它不需要参数,且会返回一个整数。 size()

?用Python实现双端队列

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

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

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 方法只能在列表的最后(最右端)添加元素。?

代码运行效果如下:

在这里插入图片描述

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

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

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

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

回文检测器代码如下:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

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


版权声明 : 本文内容来源于互联网或用户自行发布贡献,该文观点仅代表原作者本人。本站仅提供信息存储空间服务和不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权, 违法违规的内容, 请发送邮件至2530232025#qq.cn(#换@)举报,一经查实,本站将立刻删除。
原文链接 : https://blog.csdn.net/jiang1126/article/details/123337898
相关文章
  • Python Django教程之实现新闻应用程序

    Python Django教程之实现新闻应用程序
    Django是一个用Python编写的高级框架,它允许我们创建服务器端Web应用程序。在本文中,我们将了解如何使用Django创建新闻应用程序。 我们将
  • 书写Python代码的一种更优雅方式(推荐!)

    书写Python代码的一种更优雅方式(推荐!)
    一些比较熟悉pandas的读者朋友应该经常会使用query()、eval()、pipe()、assign()等pandas的常用方法,书写可读性很高的「链式」数据分析处理代码
  • Python灰度变换中伽马变换分析实现

    Python灰度变换中伽马变换分析实现
    1. 介绍 伽马变换主要目的是对比度拉伸,将图像灰度较低的部分进行修正 伽马变换针对的是对单个像素点的变换,也就是点对点的映射 形
  • 使用OpenCV实现迷宫解密的全过程

    使用OpenCV实现迷宫解密的全过程
    一、你能自己走出迷宫吗? 如下图所示,可以看到是一张较为复杂的迷宫图,相信也有人尝试过自己一点一点的找出口,但我们肉眼来解谜
  • Python中的数据精度问题的介绍

    Python中的数据精度问题的介绍
    一、python运算时精度问题 1.运行时精度问题 在Python中(其他语言中也存在这个问题,这是计算机采用二进制导致的),有时候由于二进制和
  • Python随机值生成的常用方法

    Python随机值生成的常用方法
    一、随机整数 1.包含上下限:[a, b] 1 2 3 4 import random #1、随机整数:包含上下限:[a, b] for i in range(10): print(random.randint(0,5),end= | ) 查看运行结
  • Python字典高级用法深入分析讲解
    一、 collections 中 defaultdict 的使用 1.字典的键映射多个值 将下面的列表转成字典 l = [(a,2),(b,3),(a,1),(b,4),(a,3),(a,1),(b,3)] 一个字典就是一个键对
  • Python浅析多态与鸭子类型使用实例
    什么多态:同一事物有多种形态 为何要有多态=》多态会带来什么样的特性,多态性 多态性指的是可以在不考虑对象具体类型的情况下而直
  • Python字典高级用法深入分析介绍
    一、 collections 中 defaultdict 的使用 1.字典的键映射多个值 将下面的列表转成字典 l = [(a,2),(b,3),(a,1),(b,4),(a,3),(a,1),(b,3)] 一个字典就是一个键对
  • Python淘宝或京东等秒杀抢购脚本实现(秒杀脚本

    Python淘宝或京东等秒杀抢购脚本实现(秒杀脚本
    我们的目标是秒杀淘宝或京东等的订单,这里面有几个关键点,首先需要登录淘宝或京东,其次你需要准备好订单,最后要在指定时间快速
  • 本站所有内容来源于互联网或用户自行发布,本站仅提供信息存储空间服务,不拥有版权,不承担法律责任。如有侵犯您的权益,请您联系站长处理!
  • Copyright © 2017-2022 F11.CN All Rights Reserved. F11站长开发者网 版权所有 | 苏ICP备2022031554号-1 | 51LA统计