双端队列
双端队列(deque,全名double-ended queue),是一种具有队列和栈的性质的数据结构。
双端队列中的元素可以从两端弹出,其限定插入和删除操作在表的两端进行。双端队列可以在队列任意一端入队和出队。
操作
- Deque() 创建一个空的双端队列
- add_front(item) 从队头加入一个item元素
- add_rear(item) 从队尾加入一个item元素
- remove_front() 从队头删除一个item元素
- remove_rear() 从队尾删除一个item元素
- is_empty() 判断双端队列是否为空
- size() 返回队列的大小
实现
class Deque(object):
"""双端队列"""
def __init__(self):
self.items = []
def is_empty(self):
"""判断队列是否为空"""
return self.items == []
def add_front(self, item):
"""在队头添加元素"""
self.items.insert(0,item)
def add_rear(self, item):
"""在队尾添加元素"""
self.items.append(item)
def remove_front(self):
"""从队头删除元素"""
return self.items.pop(0)
def remove_rear(self):
"""从队尾删除元素"""
return self.items.pop()
def size(self):
"""返回队列大小"""
return len(self.items)
if __name__ == "__main__":
deque = Deque()
deque.add_front(1)
deque.add_front(2)
deque.add_rear(3)
deque.add_rear(4)
print(deque.size())
print(deque.remove_front())
print(deque.remove_front())
print(deque.remove_rear())
print(deque.remove_rear())
"""
一个能用双端队列数据结构轻松解决的问题是经典的“回文词”问题。
回文词指的是正读和反 读都一样的词,如:radar、toot 和 madam。
我们想要编写一个算法来检查放入的字符串是否为回文词。
这个问题的解决方案是用一个双端队列来存储这个字符串。我们遍历这个字符串并把它的每个字母添加到双端队列的尾端。
现在这个双端队列看起来非常像一个普通队列,但我们可以利用双端 队列两端的对称性。双端队列的首端用来存储第一个字符,尾端用来存储最后一个字符。
因为我们能够同时取出两端的字符,所以我们可以比较它们是否相同,如果相同就继续比较剩 下的双端队列的首尾字符。
如果我们持续比较首尾字符并发现它们相同,最后字符串要么被比较 完,要么只剩下一个字符,这取决于字符串的原始长度是奇数还是偶数。
不管哪种情况,这个字符串都是一个回文词。回文词判断函数的实现如下。
"""
from 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('yhgughy'))