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

 

 🌈write in front🌈
🧸大家好，我是Aileen🧸.希望你看完之后，能对你有所帮助，不足请指正！共同学习交流.
🆔本文由Aileen_0v0🧸 原创 CSDN首发🐒 如需转载还请通知⚠️
📝个人主页：Aileen_0v0🧸—CSDN博客
🎁欢迎各位→点赞👍 + 收藏⭐️ + 留言📝​
📣系列专栏：Aileen_0v0🧸的PYTHON学习系列专栏——CSDN博客
🗼我的格言:"没有罗马,那就自己创造罗马~" 

 

目录

双端队列Deque🐻

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

伪代码🦌

实现代码 🦘

---

双端队列Deque🐻

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

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

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

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

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

 

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

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

#创建一个双端队列(Dequeue)
class Dequeue:#定义一个初始化函数然后创建一个空列表用于传递数据itemsdef __init__(self):self.items = []#在队首加入元素itemsdef addFront(self,item):self.items.append(item)#在队尾加入元素itemsdef 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 = namedef 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:#定义一个初始化函数然后创建一个空列表用于传递数据itemsdef __init__(self):self.items = []#判断列表是否为空def isEmpty(self):return self.items == []#在队首加入元素itemsdef addFront(self,item):self.items.append(item)#在队尾加入元素itemsdef 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 = Falsereturn still_equalprint(pal_checker ("上海自来水来自海上"))
print(pal_checker ("110110"))