数据结构----双端队列Dque

双端队列的概念与数据结构

　　deque（也称为双端队列）是与队列类似的项的有序集合。它有两个端部，首部和尾部，并且项在集合中保持不变。

　　deque 特殊之处在于添加和删除项是非限制性的。可以在前面或后面添加新项。同样，可以从任一端移除现有项。在某种意义上，这种混合线性结构提供了单个数据结构中的栈和队列的所有能力。　　

Deque的抽象数据类型定义：Deque的抽象数据类型应该由以下结构和操作定义。其中元素可以从首部或尾部的任一端添加和移除。Deque操作如下：

• Dque() 创建一个空的新 deque。它不需要参数，并返回空的 deque。
• lpush(item) 将一个新项添加到 deque 的首部。它需要 item 参数 并不返回任何内容。
• rpush(item) 将一个新项添加到 deque 的尾部。它需要 item 参数并不返回任何内容。
• lpop() 从 deque 中删除首项。它不需要参数并返回 item。deque 被修改。
• rpop() 从 deque 中删除尾项。它不需要参数并返回 item。deque 被修改。
• isEmpty() 测试 deque 是否为空。它不需要参数，并返回布尔值。
• size() 返回 deque 中的项数。它不需要参数，并返回一个整数。　　

双端队列的定义　　

　　

class Deque(object):
    def __init__(self):
        self.deque = []

    def __str__(self):
        return str(self.deque)

    def rpush(self, item):
        self.deque.append(item)

    def lpush(self, item):
        self.deque.insert(0, item)

    def rpop(self):
        return self.deque.pop() if self.deque else "Dequeue is empty!"

    def lpop(self):
        return self.deque.pop(0) if self.deque else "Dequeue is empty!"

    def isEmpty(self):
        return self.deque == []

    def size(self):
        return len(self.deque)

Deque的应用案例-回文检查

回文检测：设计程序，检测一个字符串是否为回文。

- 回文：回文是一个字符串，读取首尾相同的字符，例如，radar toot madam。

- 分析：该问题的解决方案将使用 deque 来存储字符串的字符。我们从左到右处理字符串，并将每个字符添加到 deque 的尾部。在这一点上，deque 像一个普通的队列。然而，我们现在可以利用 deque 的双重功能。 deque 的首部保存字符串的第一个字符，deque 的尾部保存最后一个字符。我们可以直接删除并比较首尾字符，只有当它们匹配时才继续。如果可以持续匹配首尾字符，我们最终要么用完字符，要么留出大小为 1 的deque，取决于原始字符串的长度是偶数还是奇数。在任一情况下，字符串都是回文。

from basic.deque import Deque

def palchecker(aString):
    chardeque = Deque()

    for ch in aString:
        chardeque.addRear(ch)

    stillEqual = True

    while chardeque.size() > 1 and stillEqual:
        first = chardeque.removeFront()
        last = chardeque.removeRear()
        if first != last:
            stillEqual = False

    return stillEqual

print(palchecker("lsdkjfskf"))
print(palchecker("radar"))