双端队列

摘自:https://www.jianshu.com/p/1f1520db325d

双端队列是与队列类似的项的有序集合。

双端队列有两个端部,首部和尾部,并且项在集合中保持不变。
双端队不同的地方是添加和删除项是非限制性的。可以在前面或后面添加新项;同样,可以从任一端移除现有项。

  双端队列

双端队列抽象数据类型

如上所述,deque 被构造为项的有序集合,其中项从首部或尾部的任一端添加和移除。
下面给出了 deque 操作。

操作 描述 返回值
Deque() 创建一个空的新 deque,不需要参数 返回空的 deque
addFront(item) 将一个新项添加到 deque 的首部,需要 item 参数 不返回任何内容
addRear(item) 将一个新项添加到 deque 的尾部,需要 item 参数 不返回任何内容
removeFront() 从 deque 中删除首项,deque 被修改 返回删除项 item
removeRear() 从 deque 中删除尾项,deque 被修改 返回删除项 item
isEmpty() 测试 deque 是否为空,不需要参数 返回布尔值
size() 返回 deque 中的项数,它不需要参数 返回一个整数

python实现双端队列

class Deque(object):
    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)

if __name__ == '__main__':
    deq = Deque()

 

双端队列的应用

使用 deque 数据结构可以容易地解决经典回文问题。回文是一个字符串,读取首尾相同的字符,例如,radar toot madam。 我们想构造一个算法输入一个字符串,并检查它是否是一个回文。
解决方案:

  1. 将字符串添加到双端队列中
  2. 直接删除并比较收尾字符串,如果可以持续匹配首尾字符,我们最终要么用完字符,要么留出大小为 1 的deque,取决于原始字符串的长度是偶数还是奇数。


      双端队列 回文检查:
    #回文检查
    def palchecker(aString):
        #创建一个双端队列,将字符串中的字符依次添加到双端队列中
        charqueue = Deque()
    
        for char in aString:
            charqueue.addRear(char)
    
        stillEqual = True
    
        #当至少有一个字符并且满足收尾相等则循环
        while charqueue.size() > 1 and stillEqual:
            first = charqueue.removeFront()
            last = charqueue.removeRear()
            if first != last:
                stillEqual = False
        return stillEqual
    
    
    print(palchecker("lsdkjfskf"))
    print(palchecker("radar"))

     

上一篇:python3 deque作用


下一篇:Java双端队列Deque