双端队列
2019-01-03 本文已影响0人
疯了个魔
双端队列
双端队列是与队列类似的项的有序集合。
双端队列有两个端部，首部和尾部，并且项在集合中保持不变。
双端队不同的地方是添加和删除项是非限制性的。可以在前面或后面添加新项；同样，可以从任一端移除现有项。
双端队列
双端队列抽象数据类型
如上所述，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:
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)
双端队列的应用
使用 deque 数据结构可以容易地解决经典回文问题。回文是一个字符串，读取首尾相同的字符，例如，radar toot madam。 我们想构造一个算法输入一个字符串，并检查它是否是一个回文。
解决方案：
- 将字符串添加到双端队列中
-
直接删除并比较收尾字符串，如果可以持续匹配首尾字符，我们最终要么用完字符，要么留出大小为 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"))
