数据结构与算法之双向队列Deque

线性数据结构（linear data structure）第三讲双向队列（deque）

双向队列添加和移除的原则：可以在队列的两头添加和移除。

双向队列的操作：

• Deque() 创建一个新双向队列，返回空的双向队列。
• add_front(item) 在双向队列头部添加一个元素，返回None。
• add_rear(item) 在双向队列的尾部添加一个元素，返回None。
• remove_front() 从头部移除一个元素，返回移除的元素。
• remove_rear() 从尾部移除一个元素，返回移除的元素。
• is_empty() 返回双向队列是否为空，True或者False。
• size() 返回双向队列中元素的个数。

双向队列的实现：

class Deque:
    def __init__(self):
        self.items = []
    def add_front(self, item):
        self.items.append(item)
    def add_rear(self, item):
        self.items.insert(0, item)
    def remove_front(self):
        return self.items.pop()
    def remove_rear(self):
        return self.items.pop(0)
    def is_empty(self):
        return self.items == []
    def size(self):
        return len(self.items)

双向队列的用处：

• 回文检查[1]: 字符全部添加后，依次从头部和尾部取出元素对比。最后双向队列为空，或者包含一个元素。

参考资料：

• Problem Solving with Algorithms and Data Structures - Chapter 3

注[1] 回文是指从前往后和从后往前读都是一样的字符串，如radar