双端队列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"))
