5. 队列

队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。

队列是一种先进先出的（First In First Out）的线性表，简称 FIFO。允许插入的一端为队尾，允许删除的一端为队头。队列不允许在中间部位进行操作！假设队列是q=（a1，a2，……，an），那么a1就是队头元素，而an是队尾元素。这样我们就可以删除时，总是从a1开始，而插入时，总是在队列最后。这也比较符合我们通常生活中的习惯，排在第一个的优先出列，最后来的当然排在队伍最后。

与栈一样，队列可以通过顺序表或链表来实现。

5.1 单向队列

单向队列就像排队一样，先进先出，其结构如下：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-iwv6VZyb-1676469300275)(https://hubery624.oss-cn-shenzhen.aliyuncs.com/排队.jpeg)]

单向队列操作

• enqueue(item) ：往队列中添加一个item元素
• dequeue()： 从队列头部删除一个元素
• is_empty()： 判断一个队列是否为空
• size()： 返回队列的大小

同样地，这里也以 list 实现单向队列，当然你也可以使用链表实现。

class Queue(object):"""创建一个空的队列"""def __init__(self):"""用顺序表实现队列，Python 中 list 是顺序表队列：先进先出以列表尾部为队头（append：O(1)，就要从列表头就是队列尾部（pop(0)：O(n)）以列表头部为队头（insert(0, item)：O(n)，就要从列表就尾是队列尾部（pop()：O(1)）所有哪种方法都可以"""# 定义一个列表，用来存储元素self.__list = []def enqueue(self, item):"""往队列中添加一个item元素"""self.__list.append(item)def dequeue(self):"""从队列头部删除一个元素"""return self.__list.pop(0)def is_empty(self):"""判断栈是否为空若 self.__list 为空，则为 False，[] 也是 False，两者为真，返回 True"""return self.__list == []def size(self):"""返回栈的元素个数"""return len(self.__list)if __name__ == '__main__':q = Queue()print(q.is_empty())q.enqueue(1)q.enqueue(2)q.enqueue(3)print(q.size())print(q.is_empty())print(q.dequeue())print(q.dequeue())print(q.dequeue())print(q.is_empty())

如果用 list 实现单向队列，不管是以 list 头部作为队头还是队尾，最终的结果都是有一个 O(n) 还有个 O(1）。

运行结果如下：

# 先进先出
True
3
False
1
2
3
True

5.2 双端队列

双端队列（deque，全名double-ended queue），是一种具有队列和栈的性质的数据结构。

双端队列中的元素可以从两端弹出，其限定插入和删除操作在表的两端进行。双端队列可以在队列任意一端入队和出队。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-9PGhQNjW-1676469300275)(https://hubery624.oss-cn-shenzhen.aliyuncs.com/20200613105121.png)]

操作

• add_front(item)： 从队头加入一个item元素
• add_rear(item) ：从队尾加入一个item元素
• remove_front() ：从队头删除一个item元素
• remove_rear()： 从队尾删除一个item元素
• is_empty() ：判断双端队列是否为空
• size() ：返回队列的大小

class Deque(object):"""创建一个空的双端队列"""def __init__(self):"""用顺序表实现栈，Python 中 list 是顺序表栈：先进先出以列表尾部为队头（append：O(1)，就要从列表头就是队列尾部（pop(0)：O(n)）以列表头部为队头（insert(0, item)：O(n)，就要从列表就尾是队列尾部（pop()：O(1)）所有哪种方法都可以"""# 定义一个列表，用来存储元素self.__list = []def add_front(self, item):"""从队头加入一个item元素"""self.__list.insert(0, item)     # O(n)# self.__list.append(item)      # O(1)def add_rear(self, item):"""从队尾加入一个item元素"""self.__list.append(item)        # O(1)# self.__list.insert(0, item)   # O(n)def remove_front(self):"""从队头删除一个item元素"""return self.__list.pop(0)       # O(n)# return self.__list.pop()      # O(1)def remove_rear(self):"""从队尾删除一个item元素"""return self.__list.pop()        # O(1)# return self.__list.pop(0)     # O(n)def is_empty(self):"""判断栈是否为空若 self.__list 为空，则为 False，[] 也是 False，两者为真，返回 True"""return self.__list == []def size(self):"""返回栈的元素个数"""return len(self.__list)if __name__ == '__main__':q = Deque()print(q.is_empty())q.add_front(1)      # 1q.add_front(2)      # 2 1q.add_rear(3)       # 2 1 3print(q.size())     # 3print(q.is_empty())     # Falseprint(q.remove_front())     # 2print(q.remove_front())     # 1print(q.remove_rear())      # 3print(q.is_empty())         # True

运行结果如下：

True
3
False
2
1
3
True