Python中的队列

2022年 11月 4日

你好，我是悦创。

我们来看一下群友的问题：

在这里插入图片描述

那我来分享一下，队列的基本知识。

1. 队列的基本知识

先进先出队列(或简称队列)是一种基于先进先出(FIFO)策略的集合类型.

队列的最简单的例子是我们平时碰到的：

比如排队等待电影；
在杂货店的收营台等待；
在自助餐厅排队等待（这样我们可以弹出托盘栈）。

行为良好的线或队列是有限制的，因为它只有一条路，只有一条出路。不能插队，也不能离开。你只有等待了一定的时间才能到前面。下图展示了一个简单的 Python 对象队列。

队列是有序数据集合，队列的特点，删除数据项是在头部，称为前端(front)，增加数据在尾部，称为后端(rear)

2. Queue

# 导入队列
from queue import Queue

# 最多接收3个数据,设置队列长度
q = Queue(3)

# put 向队列中添加数据
q.put(1)
q.put(2)
q.put(3)

# 获取当前队列长度
print(q.qsize())

# 取出最前面的一个数据 1 , 还剩两个
print(q.get())

# 再加入数据
q.put(4)

#超过三个了.如果没有 timeout 参数会处于阻塞状态,卡在那边.若设置 2秒,2秒后会 raise 一个 FULL 的报错
q.put(5, timeout=2))

# 当然,也可以直接给个 block=False,强制设置为不阻塞(默认为会阻塞的)，一旦超出队列长度，立即抛出异常
q.put(6, block=False)

# 同样的,当取值(get)的次数大于队列的长度的时候就会产生阻塞，设置超时时间意为最多等待x秒，队列中再没有数据，就抛出异常.也可以使用block参数,跟上面一样

其他常用方法：

empty: 检查队列是否为空，为空返回True，不为空返回False
full : 判断队列是否已经满了

join & task_done :
#举例
from queue import Queue
q = queue.Queue(2)
q.put('a')
q.put('b')
# 程序会一直卡在下面这一行，只要队列中还有值，程序就不会退出
q.join()
-------------------------------------------------------------
q = queue.Queue(2)
q.put('a')
q.put('b')

q.get() 
q.get()
# 插入两个元素之后再取出两个元素，执行后发现，程序还是卡在下面的那个join代码
q.join()
-------------------------------------------------------------
q = queue.Queue(2)
q.put('a')
q.put('b')

q.get()
# get取完队列中的一个值后，使用task_done方法告诉队列，我已经取出了一个值并处理完毕,下同
q.task_done() 
q.get()
#在每次get取值之后，还需要在跟队列声明一下，我已经取出了数据并处理完毕，这样执行到join代码的时候才不会被卡住
q.task_done()
q.join()

3. 双向队列

但是删除列表的第一个元素（抑或是在第一个元素之前添加一个元素）之类的操作是很耗时的，因为这些操作会牵扯
到移动列表里的所有元素。

4. deque

collections.deque 类（双向队列）是一个线程安全、可以快速从两端添加或者删除元素的数据类型。而且如果想要有一种数据类型来存放“最近用到的几个元素”，deque 也是一个很好的选择。这是因为在新建一个双向队列的时候，你可以指定这个队列的大小，如果这个队列满员了，还可以从反向端删除过期的元素，然后在尾端添加新的元素。使用示例如下:

>>> from collections import deque
>>> dq = deque(range(10), maxlen=10) ➊
>>> dq
deque([0, 1, 2, 3, 4, 5, 6, 7, 8, 9], maxlen=10)
>>> dq.rotate(3) ➋
>>> dq
deque([7, 8, 9, 0, 1, 2, 3, 4, 5, 6], maxlen=10)
>>> dq.rotate(-4)
>>> dq
deque([1, 2, 3, 4, 5, 6, 7, 8, 9, 0], maxlen=10)
>>> dq.appendleft(-1) ➌
>>> dq
deque([-1, 1, 2, 3, 4, 5, 6, 7, 8, 9], maxlen=10)
>>> dq.extend([11, 22, 33]) ➍
>>> dq
deque([3, 4, 5, 6, 7, 8, 9, 11, 22, 33], maxlen=10)
>>> dq.extendleft([10, 20, 30, 40]) ➎
>>> dq
deque([40, 30, 20, 10, 3, 4, 5, 6, 7, 8], maxlen=10)

❶ maxlen 是一个可选参数，代表这个队列可以容纳的元素的数量，而且一旦设定，这个
属性就不能修改了。

❷ 队列的旋转操作接受一个参数 n，当 n > 0 时，队列的最右边的 n 个元素会被移动到
队列的左边。当 n < 0 时，最左边的 n 个元素会被移动到右边。

❸ 当试图对一个已满（len(d) == d.maxlen）的队列做尾部添加操作的时候，它头部
的元素会被删除掉。注意在下一行里，元素 0 被删除了。

❹ 在尾部添加 3 个元素的操作会挤掉 -1、1 和 2。

❺ extendleft(iter) 方法会把迭代器里的元素逐个添加到双向队列的左边，因此迭代
器里的元素会逆序出现在队列里。

5. 其他队列

Python提供的所有队列类型 :

先进先出队列 queue.Queue
后进先出队列 queue.LifoQueue (Queue的基础上进行的封装)
优先级队列 queue.PriorityQueue (Queue的基础上进行的封装)
双向队列 queue.deque

除了上述提到的队列与双端队列,还有两个用的比较少的:后进先出队列与优先级队列

6. 自己队列实现

在实际编码中不会自己来实现一个队列.因为python本身就有自带的队列库.如果想自己实现可以利用列表的一些特性,比如.append或者.pop来实现.也可以抛开列表重新定义一个队列.这里有一个很好的例子来实现

6.1 数据结构-队列

队列是有序数据集合，队列的特点，删除数据项是在头部，称为前端(front)，增加数据在尾部，称为后端(rear)。数据项总是开始排在队伍的后端，慢慢向前走，直到排到最前面，轮到它的时候离开队列。

刚进来的数据排在后端，待在队伍里时间最长的在前端，这种排列规则叫做FIFO(first-in first-out)，意思是“先进先出”，或者叫做“先来先服务”(first-come first-served)

队列一般提供以下接口：

Queue() 定义一个空队列，无参数，返回值是空队列
enqueue(item) 在队列尾部加入一个数据项，参数是数据项，无返回值
dequeue() 删除队列头部的数据项，不需要参数，返回值是被删除的数据，队列本身有变化。
isEmpty() 检测队列是否为空。无参数，返回布尔值。
size() 返回队列数据项的数量。无参数，返回一个整数。

用 python 的 list 数据类型能比较容易的实现队列数据模型，但这里不以list来实现。我们假设队列里的元素有一个指针，最先加进元素的指针指向它下一个元素，依次类推，最后一个元素的指针是指向 None。所以队列里的元素可以抽象出一个类来，同样像链表时的 Node 类一样，Node 类里有自己的数据和一个指向 None 的指针。一个 Node 对象如下示意图：

而队列里分为两端，一端叫前端，这一端做数据的删除操作，另一端叫后端，做数据的增加操作。数据只能从后端加入，并只能从前端删除。为了抽象这个Queue类，会创建两个指针，一个head，指向队头的元素，一个tail，指向队尾的元素。如果是一个空的队列，那head和tail都指向None。

一个空队列示意图：

当队列里有一个元素时，head和tail两个指针都指向这个元素，示意图是这样的：

当队列再增加一个元素时，tail指针会移动到新增加的这个元素，前一个元素的next指针也会指向新元素，而head指针不会发生改变，如下图：

不断向队列增加元素时，各个指针移动方式如上。

当是删除元素时，直接把head指针移动到下一个元素，再把值弹出即可。

来看一个最简单队列的代码实现：

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None
 
 
class Queue:
    def __init__(self):
        self.head = None
        self.tail = None
 
    def enqueue(self, value):
        node = Node(value)
        if self.head is None:
            self.head = node
            self.tail = node
        else:
            self.tail.next = node
            self.tail = node
 
    def dequeue(self):
        if self.head is None:
            raise Exception('This is a empty queue')
        cur = self.head
        self.head = cur.next
        return cur.value
 
    def is_empty(self):
        return self.head is None
 
    def size(self):
        cur = self.head
        count = 0
        if cur is None:
            return count
        while cur.next is not None:
            count += 1
            cur = cur.next
        return count + 1
 
 
if __name__ == '__main__':
    q = Queue()
    for i in range(5):
        q.enqueue(i)
    for _ in range(5):
        print(q.dequeue())
    print(q.is_empty())
    print(q.size())

在实际编码中不会自己来实现一个队列，而是使用标准库中的queue，通过from queue import Queue来导入Queue类。