Deque抽象数据类型

deque 抽象数据类型由以下结构和操作定义。如上所述，deque 被构造为项的有序集合，其中项从首部或尾部的任一端添加和移除。下面给出了 deque 操作。

  1. Deque() 创建一个空的新 deque。它不需要参数，并返回空的 deque。
  2. addFront(item) 将一个新项添加到 deque 的首部。它需要 item 参数 并不返回任何内容。
  3. addRear(item) 将一个新项添加到 deque 的尾部。它需要 item 参数并不返回任何内容。
  4. removeFront() 从 deque 中删除首项。它不需要参数并返回 item。deque 被修改。
  5. removeRear() 从 deque 中删除尾项。它不需要参数并返回 item。deque 被修改。
  6. isEmpty() 测试 deque 是否为空。它不需要参数，并返回布尔值。
  7. size() 返回 deque 中的项数。它不需要参数，并返回一个整数。

Python实现Deque

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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方法（第12行），因为 append 方法在列表的末尾添加一个新元素。
你可以看到许多与栈和队列中描述的 Python 代码相似之处。你也可能观察到，在这个实现中，从前面添加和删除项是 O(1)，而从后面添加和删除是 O(n)。 考虑到添加和删除项是出现的常见操作，这是可预期的。 同样，重要的是要确定我们知道在实现中前后都分配在哪里。

回文检查

使用 deque 数据结构可以容易地解决经典回文问题。回文是一个字符串，读取首尾相同的字符，例如，radar toot madam。 我们想构造一个算法输入一个字符串，并检查它是否是一个回文。
该问题的解决方案将使用 deque 来存储字符串的字符。我们从左到右处理字符串，并将每个字符添加到 deque 的尾部。在这一点上，deque 像一个普通的队列。然而，我们现在可以利用 deque 的双重功能。 deque 的首部保存字符串的第一个字符，deque 的尾部保存最后一个字符

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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"))
1
2
False
True