定义
双端队列（deque，全名double-ended queue），是一种具有队列和栈的性质的数据结构。
双端队列中的元素可以从两端弹出，其限定插入和删除操作在表的两端进行。双端队列可以在队列任意一端入队和出队。
python 实现双端队列
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_end(self, item):
"""
从队尾添加元素
"""
self.items.append(item)
def pop_front(self):
"""
从队头移除元素
"""
return self.items.pop(0)
def pop_end(self):
"""
从队尾移除元素
"""
return self.items.pop()
def size(self):
"""
返回大小
"""
return len(self.items)
if __name__ == '__main__':
q = Deque()
print("当前队列是否为空", q.is_empty())
print("当前队列大小：", q.size())
q.add_front(1)
q.add_front(96)
q.add_end(55)
print("出队元素为：", q.pop_front())
print("出队元素为：", q.pop_end())
print("当前队列是否为空", q.is_empty())
print("当前队列大小：", q.size())
结果
当前队列是否为空 True
当前队列大小： 0
出队元素为： 96
出队元素为： 55
当前队列是否为空 False
当前队列大小： 1
经典算法题
双端队列实现判定一个字符串是不是回文，回文从左到右和从右到左读都一样，比如：toot，madam
解题思路：
- 将字符串插入双端队列中
- 删除首尾字符串并比较，如果能持续匹配到，最终会消耗完字符串，那么双端队列里要么为空，要么大小为1，这取决于输入的字符串是奇数还是偶数。
代码实现
def is_palindrome(value):
"""
检测是否为回文数
"""
q = Deque()
for char in value:
q.add_front(char)
while q.size() > 1:
# 取出首尾字符
first = q.pop_front()
end = q.pop_end()
if first != end:
return False
return True
print(is_palindrome('madam'))
print(is_palindrome('abccb'))
结果
True
False
