4.1 队列的3种实现方式

Python中有多种方法可以实现队列，可使用Python库中的数据结构和模块实现队列：①列表；②collections.deque；③queue.Queue。

1.使用列表实现队列

列表是Python的内置数据结构，可以用作实现队列，可使用append()和pop()函数代替队列的入队函数enqueue()和出队函数dequeue()对队列进行操作。利用列表实现队列非常慢，因为在开头插入或删除一个元素需要将所有其他元素移位，时间复杂度为 O （ n ）。

运行结果：

2.使用collections.deque实现队列

可以使用collections模块中的deque类实现队列。在需要从队列的两端更快地执行添加和删除操作的情况下，与列表相比，使用deque更可取，因为与列表相比，deque的添加和删除操作的时间复杂度为 O （1）。可使用append()和popleft()函数分别代替enqueue()和dequeue()。

运行结果：

3.使用queue.Queue实现队列

queue.Queue()是Python的内置模块，可用于实现队列。使用queue.Queue（maxsize）构造队列，其中maxsize表示队列中允许的最大元素数，maxsize为0表示无限队列。队列遵循FIFO规则。此模块提供了以下各种功能：

❑maxsize：队列中允许的最大元素数。

❑empty()：如果队列为空，则返回True，否则返回False。

❑full()：如果队列满了，则返回True；如果队列使用maxsize=0（默认值）初始化，则full()永远不会返回True。

❑get()：从队列中删除并返回一个元素，如果队列为空，请等待，直到有一个元素可用。

❑get_nowait()：如果元素立即可用，则返回此元素，否则引发QueueEmpty。

❑put（item）：将元素item放入队列，如果队列已满，请等到有空闲位置后再添加。

❑put_nowait（item）：将元素item放入队列而不会阻塞。

❑qsize()：返回队列中的元素数，如果没有可用的空闲位置，请增加QueueFull。

运行结果： W6Sa9MvlNSKvTuSlbKtybHBaoemkNrjTnEunb2drAa1QOwTxfpupECNtIT+UFIzi