双端队列

接下来学习另一个线性数据结构。与栈和队列不同的是，双端队列的限制很少。注意，不要把它的英文名 deque（与 deck 同音）和队列的移除操作 dequeue 搞混了。

何谓双端队列

双端队列是与队列类似的有序集合。它有一前、一后两端，元素在其中保持自己的位置。与队列不同的是，双端队列对在哪一端添加和移除元素没有任何限制。新元素既可以被添加到前端，也可以被添加到后端。同理，已有的元素也能从任意一端移除。某种意义上，双端队列是栈和队列的结合。图3-16 展示了由 Python 数据对象组成的双端队列。

Figure 1. 图3-16 由Python数据对象组成的双端队列

值得注意的是，尽管双端队列有栈和队列的很多特性，但是它并不要求按照这两种数据结构分别规定的 LIFO 原则和 FIFO 原则操作元素。具体的排序原则取决于其使用者。

双端队列抽象数据类型

双端队列抽象数据类型由下面的结构和操作定义。如前所述，双端队列是元素的有序集合，其任何一端都允许添加或移除元素。双端队列支持以下操作。

Deque() 创建一个空的双端队列。它不需要参数，且会返回一个空的双端队列。
addFront(item) 将一个元素添加到双端队列的前端。它接受一个元素作为参数，没有返回值。
addRear(item) 将一个元素添加到双端队列的后端。它接受一个元素作为参数，没有返回值。
removeFront() 从双端队列的前端移除一个元素。它不需要参数，且会返回一个元素，并修改双端队列的内容。
removeRear() 从双端队列的后端移除一个元素。它不需要参数，且会返回一个元素，并修改双端队列的内容。
isEmpty() 检查双端队列是否为空。它不需要参数，且会返回一个布尔值。
size() 返回双端队列中元素的数目。它不需要参数，且会返回一个整数。

假设 d 是一个新创建的空双端队列，表3-6 展示了对 d 进行一系列操作的结果。注意，前端在列表的右端。记住前端和后端的位置可以防止混淆。

Figure 2. 表3-6 双端队列操作示例

用Python实现双端队列

和前几节一样，我们通过创建一个新类来实现双端队列抽象数据类型。Python 列表再一次提供了很多简便的方法来帮助我们构建双端队列。在代码清单3-14 中，我们假设双端队列的后端是列表的位置 0 处。

代码清单3-14 用Python实现双端队列

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

removeFront 使用 pop 方法移除列表中的最后一个元素，removeRear 则使用 pop(0) 方法移除列表中的第一个元素。同理，之所以 addRear 使用 insert 方法，是因为 append 方法只能在列表的最后添加元素。

以下展示了表3-6 中的双端队列操作及其返回结果。

>>> d = Deque()
>>> d.isEmpty()
True
>>> d.addRear(4)
>>> d.addRear('dog')
>>> d.addFront('cat')
>>> d.addFront(True)
>>> d.size()
4
>>> d.isEmpty()
False
>>> d.addRear(8.4)
>>> d.removeRear()
8.4
>>> d.removeFront()
True

实现双端队列的 Python 代码与实现栈和队列的有许多相似之处。在双端队列的 Python 实现中，在前端进行的添加操作和移除操作的时间复杂度是 \$O(1)\$，在后端的则是 \$O(n)\$。考虑到实现时采用的操作，这不难理解。再次强调，记住前后端的位置非常重要。

回文检测器

运用双端队列可以解决一个非常有趣的经典问题：回文问题。回文是指从前往后读和从后往前读都一样的字符串，例如 radar、toot，以及 madam。我们将构建一个程序，它接受一个字符串并且检测其是否为回文。

该问题的解决方案是使用一个双端队列来存储字符串中的字符。按从左往右的顺序将字符串中的字符添加到双端队列的后端。此时，该双端队列类似于一个普通的队列。然而，可以利用双端队列的双重性，其前端是字符串的第一个字符，后端是字符串的最后一个字符，如图3-17 所示

Figure 3. 图3-17 双端队列示例

由于可以从前后两端移除元素，因此我们能够比较两个元素，并且只有在二者相等时才继续。如果一直匹配第一个和最后一个元素，最终会处理完所有的字符（如果字符数是偶数），或者剩下只有一个元素的双端队列（如果字符数是奇数）。任意一种结果都表明输入字符串是回文。代码清单3-15 展示了完整的回文检测程序。

代码清单3-15 用Python实现回文检测器

from pythonds.basic 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"))

调用 palchecker 函数的示例如下所示。

>>> palchecker("lsdkjfskf")
False
>>> palchecker("toot")
True