数据结构与算法-(9)---双端队列(Deque)-阿里云开发者社区

数据结构与算法-(9)---双端队列(Deque)

2023-11-22 60

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 数据结构与算法-(9)---双端队列(Deque)

双端队列Deque🐻

Dequeue特点:数据可以从队首也可以从队尾加入,也可以从两端进行移除.

它集成了栈和队列的能力.

But 双端队列并不具有内在的LIFO或者FIFO特性

如果双端队列用来模拟栈或队列需要使用者自行维护操作的一致性.

将它的头或者尾部倒转过来我们可以将它看成是一个栈(Stack)

我们可以仿照之前的栈以及队列对象的创建,我们给双端队列也创建一个对象

忘记的小伙伴可以点击👉🔗http://t.csdnimg.cn/RfdSQ

#创建一个双端队列(Dequeue)
class Dequeue:
    #定义一个初始化函数然后创建一个空列表用于传递数据items
    def __init__(self):
        self.items = []
     #在队首加入元素items
    def addFront(self,item):
        self.items.append(item)
    #在队尾加入元素items
    def addRear(self,items):
        self.items.insert(0,item)
    #从队首移除数据,返回值为移除数据项
    def removeFront(self):
        return self.items.pop()
    #从队尾移除数据,返回移除数据项
    def removeRear(self):
        return self.items.pop(0)
    #判断列表是否为空
    def isEmpty(self):
        return self.items == []
    #返回Dequeue中包含的数据项的个数
    def size(self):
        return len(self.items)

双端队列:我们还是采用List去实现它,List下标0作为deque的尾端,List下标-1作为deque的首端

操作复杂度: addFront / removeFront 的复杂度是 O(1)

addRear / removeRear 的复杂度是 O(n)

双端队列的应用 - 判断回文数🦫

之前看过我的Python每日一练的小伙伴一定记得之前做过同样的题,只是我们用的是列表切片进行反转,不记得的小伙伴可以点击👉🔗http://t.csdnimg.cn/7J0fF

输入一个数，判断它是不是回文数。12321,radar是回文数，正着读和反着读都一样.

伪代码🦌

Python面向对象编程允许在类外的函数里面进行实例化对象。

这是因为Python中一切皆对象，实例化对象也只是调用类的构造函数来创建一个对象而已，因此可以在任何地方进行实例化操作。

在类外部实例化对象的作用是提高程序的灵活性和可维护性。有时候我们会需要在多个函数或模块中使用同一个对象，如果每个函数或模块都单独创建一个对象，就会增加对象的数量，造成不必要的开销。而在类外部实例化一个对象，然后将该对象传递给多个函数或模块使用，则可以大大减少对象的数量，提高程序的效率和可维护性。

下面是一个简单的例子，演示了在类外部实例化对象的方法及其作用：

class Person:
    def __init__(self, name):
        self.name = name
    def say_hello(self):
        print("Hello, my name is", self.name)
def greet(person):
    person.say_hello()
# 在函数外部实例化对象
p = Person("Bob")
# 将对象传递给另外一个函数使用
greet(p)  # "Hello, my name is Bob"

在上面的例子中，我们在函数外部实例化了一个Person对象，然后将该对象传递给greet()函数，该函数使用该对象的say_hello()方法来打印出问候语。这种方法可以避免在greet()函数中重复创建Person对象，提高程序的效率和可维护性。

实现代码 🦘

#创建一个双端队列(Dequeue)
class Dequeue:
    #定义一个初始化函数然后创建一个空列表用于传递数据items
    def __init__(self):
        self.items = []
    #判断列表是否为空
    def isEmpty(self):
        return self.items == []
     #在队首加入元素items
    def addFront(self,item):
        self.items.append(item)
    #在队尾加入元素items
    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 isEmpty(self):
        return self.items == []
    #返回Dequeue中包含的数据项的个数
    def size(self):
        return len(self.items)
#palindrome - 回文检查
def  pal_checker (ps):
    #实例化对象
    d = Dequeue()
    for char in  ps:
        d.addRear(char)
    #假设元素左右相等
    still_equal = True
    #依次取出首尾元素进行判断,然后再判断它是否满足 :
    # 奇数个元素的时候,双端队列里面还剩下一个元素
    #偶数个元素的时候,双端队列里面没有元素
    while d.size() > 1 and still_equal :
        #从队首取出一个元素
        first = d.removeFront()
        #从队尾取出一个元素
        last = d.removeRear()
        if first != last:
            still_equal = False
    return still_equal
print(pal_checker ("上海自来水来自海上"))
print(pal_checker ("110110"))