在 Python 中，队列（Queue）是一种常用的数据结构，用于按照特定的顺序存储和访问数据。队列的主要类型包括先进先出（FIFO）、后进先出（LIFO）、优先级队列、双端队列（Deque）和环形队列，每种队列在不同的应用场景中都有其独特的用途。

全网最适合入门的面向对象编程教程：41 Python 常用复合数据类型-队列（FIFO、LIFO、优先级队列、双端队列和环形队列）

摘要：

在 Python 中，队列（Queue）是一种常用的数据结构，用于按照特定的顺序存储和访问数据。队列的主要类型包括先进先出（FIFO）、后进先出（LIFO）、优先级队列、双端队列（Deque）和环形队列，每种队列在不同的应用场景中都有其独特的用途。

原文链接：

FreakStudio的博客

往期推荐：

学嵌入式的你，还不会面向对象？？！

全网最适合入门的面向对象编程教程：00 面向对象设计方法导论

全网最适合入门的面向对象编程教程：01 面向对象编程的基本概念

全网最适合入门的面向对象编程教程：02 类和对象的 Python 实现-使用 Python 创建类

全网最适合入门的面向对象编程教程：03 类和对象的 Python 实现-为自定义类添加属性

全网最适合入门的面向对象编程教程：04 类和对象的Python实现-为自定义类添加方法

全网最适合入门的面向对象编程教程：05 类和对象的Python实现-PyCharm代码标签

全网最适合入门的面向对象编程教程：06 类和对象的Python实现-自定义类的数据封装

全网最适合入门的面向对象编程教程：07 类和对象的Python实现-类型注解

全网最适合入门的面向对象编程教程：08 类和对象的Python实现-@property装饰器

全网最适合入门的面向对象编程教程：09 类和对象的Python实现-类之间的关系

全网最适合入门的面向对象编程教程：10 类和对象的Python实现-类的继承和里氏替换原则

全网最适合入门的面向对象编程教程：11 类和对象的Python实现-子类调用父类方法

全网最适合入门的面向对象编程教程：12 类和对象的Python实现-Python使用logging模块输出程序运行日志

全网最适合入门的面向对象编程教程：13 类和对象的Python实现-可视化阅读代码神器Sourcetrail的安装使用

全网最适合入门的面向对象编程教程：全网最适合入门的面向对象编程教程：14 类和对象的Python实现-类的静态方法和类方法

全网最适合入门的面向对象编程教程：15 类和对象的 Python 实现-__slots__魔法方法

全网最适合入门的面向对象编程教程：16 类和对象的Python实现-多态、方法重写与开闭原则

全网最适合入门的面向对象编程教程：17 类和对象的Python实现-鸭子类型与“file-like object“

全网最适合入门的面向对象编程教程：18 类和对象的Python实现-多重继承与PyQtGraph串口数据绘制曲线图

全网最适合入门的面向对象编程教程：19 类和对象的 Python 实现-使用 PyCharm 自动生成文件注释和函数注释

全网最适合入门的面向对象编程教程：20 类和对象的Python实现-组合关系的实现与CSV文件保存

全网最适合入门的面向对象编程教程：21 类和对象的Python实现-多文件的组织：模块module和包package

全网最适合入门的面向对象编程教程：22 类和对象的Python实现-异常和语法错误

全网最适合入门的面向对象编程教程：23 类和对象的Python实现-抛出异常

全网最适合入门的面向对象编程教程：24 类和对象的Python实现-异常的捕获与处理

全网最适合入门的面向对象编程教程：25 类和对象的Python实现-Python判断输入数据类型

全网最适合入门的面向对象编程教程：26 类和对象的Python实现-上下文管理器和with语句

全网最适合入门的面向对象编程教程：27 类和对象的Python实现-Python中异常层级与自定义异常类的实现

全网最适合入门的面向对象编程教程：28 类和对象的Python实现-Python编程原则、哲学和规范大汇总

全网最适合入门的面向对象编程教程：29 类和对象的Python实现-断言与防御性编程和help函数的使用

全网最适合入门的面向对象编程教程：30 Python的内置数据类型-object根类

全网最适合入门的面向对象编程教程：31 Python的内置数据类型-对象Object和类型Type

全网最适合入门的面向对象编程教程：32 Python的内置数据类型-类Class和实例Instance

全网最适合入门的面向对象编程教程：33 Python的内置数据类型-对象Object和类型Type的关系

全网最适合入门的面向对象编程教程：34 Python的内置数据类型-Python常用复合数据类型：元组和命名元组

全网最适合入门的面向对象编程教程：35 Python的内置数据类型-文档字符串和__doc__属性

全网最适合入门的面向对象编程教程：36 Python的内置数据类型-字典

全网最适合入门的面向对象编程教程：37 Python常用复合数据类型-列表和列表推导式

全网最适合入门的面向对象编程教程：38 Python常用复合数据类型-使用列表实现堆栈、队列和双端队列

全网最适合入门的面向对象编程教程：39 Python常用复合数据类型-集合

全网最适合入门的面向对象编程教程：40 Python常用复合数据类型-枚举和enum模块的使用

更多精彩内容可看：

给你的 Python 加加速：一文速通 Python 并行计算

一文搞懂 CM3 单片机调试原理

肝了半个月，嵌入式技术栈大汇总出炉

电子计算机类比赛的“武林秘籍”

一个MicroPython的开源项目集锦：awesome-micropython，包含各个方面的Micropython工具库

Avnet ZUBoard 1CG开发板—深度学习新选择

SenseCraft 部署模型到Grove Vision AI V2图像处理模块

文档和代码获取：

可访问如下链接进行对文档下载：

https://github.com/leezisheng/Doc

本文档主要介绍如何使用 Python 进行面向对象编程，需要读者对 Python 语法和单片机开发具有基本了解。相比其他讲解 Python 面向对象编程的博客或书籍而言，本文档更加详细、侧重于嵌入式上位机应用，以上位机和下位机的常见串口数据收发、数据处理、动态图绘制等为应用实例，同时使用Sourcetrail 代码软件对代码进行可视化阅读便于读者理解。

相关示例代码获取链接如下：https://github.com/leezisheng/Python-OOP-Demo

正文

队列作为一种特殊的数据结构，与集合一样，完全可以通过列表来实现其功能。队列是一种特殊的线性表，其特殊性在于仅允许在前端进行删除操作，而在后端进行插入操作，这与栈的行为模式相似，是一种受限制的线性表。插入操作的端被称作队尾，删除操作的端被称作队头，其核心概念是“先进先出”。

在 Python 中 Queue 模块提供了一个同步的线程安全的队列类，它包括常见的 FIFO（先入先出）、LIFO（后入先出）、PriorityQueue（按优先级队列）以及先入先出类型的简单队列（SimpleQueue）。

队列的基本操作方法如下：

FIFO 队列

FIFO，即 First In First Out，是我们对队列最常见的理解定义。想象一下，在银行或取款机前排成一队的情况，排在最前面的人通常会最先接受服务，而排在后面的人依次接受服务。Python 的 Queue 类正是如此。

Queue 类通常被用作某种沟通媒介，当一些对象产生数据而其他对象需要消耗这些数据时，且可能以不同的速度进行。设想一个消息应用从网络接收消息，但同一时间只能向用户展示一条消息。其他的消息会按照接收顺序缓存在队列中。

当考虑下一个对象被消耗时才需要访问数据结构中的数据时，Queue 类便成为了一个理想的选择。在这种情况下，使用列表会效率低下，因为在列表的头部插入（或移除）数据需要移动剩余的所有元素。

<code>import queue

# 如果不设置长度,默认为无限长

q = queue.Queue(5)

# 注意没有括号

print(q.maxsize)

q.put(123)

q.put(456)

q.put(789)

q.put(100)

print(q.get())

print(q.get())

print(q.get())

运行结果如下：

LIFO 队列

LIFO 代表“后进先出”（Last In First Out），LIFO 队列通常被称为栈。想我们可以将一摞纸作为形象的比喻，你每次只能拿到最上面的一张。你可以往上面放另外一张纸，使它成为最上层，或者可以拿走最上层的纸露出下面的一张。

按照惯例，对栈进行的操作被称为 push 和 pop，但是 Python 的 queue 模块使用的是与 FIFO 队列完全相同的 API：put()和 get()。只不过在 LIFO 队列中，这些方法作用于栈“顶”而不是队伍的前后端。（实际上，LIFO 和 FIFO 队列继承于同一个父类，在相同的方法中实现了不同的操作，这也是我们前面讲过的面向对象编程中多态的一个非常好的例子。）

LIFO 队列在底层的实现就是一个标准的列表，相比于列表，Lifo 队列支持多线程并发访问，同时 Lifo 队列强制使用栈接口。你无法随意地向 Lifo 队列中的错误位置插入值。

<code>from queue import LifoQueue

_# 创建对象_

lifoQueue = LifoQueue()

lifoQueue.put(1)

lifoQueue.put(2)

lifoQueue.put(3)

print(lifoQueue.queue)

_# 返回并删除队列尾部元素_

print(lifoQueue.get())

print(lifoQueue.queue)

运行结果如下：

优先级队列

优先级队列强制使用一种与之前的队列实现迥然不同的排序风格。它们仍然使用相同的 get()和 put()函数，不过不同的是，它们不是按照加入顺序来返回的，而是首先返回“最重要”的元素。按照约定，最重要或者说优先级最高的元素是通过小于操作排在最低位的元素。

通常是将一个元组存储到优先级队列中，其中元组的第一个元素代表其优先级，第二个元素是数据；另一种常用范式是实现__lt__方法（队列中多个元素拥有相同的优先级时无法保证哪个会最先返回）。

优先级队列在许多实际应用中非常有用，例如任务调度、网络流量控制和机器学习中的一些算法。以任务调度为例，可以使用优先级队列来管理一组任务。每个任务都有一个优先级值，优先级值最高的任务最先被执行。通过使用优先级队列，可以确保高优先级的任务能够及时得到处理。

如果队列是空的，get()方法将会阻塞（默认情况下）；如果队列非空，就不会阻塞，也不会等待优先级更高的元素添加进来。队列对于还未添加的元素（甚至是已经被提取出来的元素）毫不关心，仅仅基于队列当前内容做出决定。

<code>import queue

_# 创建优先级队列_

q = queue.PriorityQueue()

_# put一个元组，元组格式为（优先级，数据）_

_# 数字越小，优先级越高_

q.put((4,'aaaaa'))

q.put((3,'bbbbb'))

q.put((2,'ccccc'))

q.put((1,'ddddd'))

print(q.get())

print(q.get())

print(q.get())

print(q.get())

如下为运行结果：

优先级队列的通用实现都是基于 heap（堆）数据结构的。Python 实现利用了 heapq 模块来高效地将 heap 存储在一个寻常的列表中。关于 heap 堆的详细介绍在后文中会提到。

双端队列

双端队列 Double-ended queue，简称为 Deque，和队列的操作方式出列同名但不是一个意思。 在计算机科学中，双端队列(缩写为 deque) 是一种抽象数据类型，它概括了一个队列，其中的元素可以从前(头) 或后(尾) 添加或删除。因此也经常被称为首尾链表。

双端队列有两种：

（1）输入限制型双端队列：这种队列中输入被限制在一端，而删除则可以两端同时进行；

（2）输出限制型双端队列：这种队列只能在一端进行删除，而插入元素则可以两端同时进行。

双端队列在许多实际应用中有着广泛的用途，其中一些包括：

• **页面缓存: **浏览器的前进、后退功能可以通过双端队列实现；
• 调度算法: 在某些调度算法中，双端队列可以用于任务的优先级调度；
• **优先级队列: **双端队列可以用作优先级队列的基础数据结构。

以下是关于双端队列相关操作的示例代码，首先我们需要导入 collections 模块，这个模块实现了一些专门化的容器，提供了对 Python 的通用内建容器 dict、list、set 和 tuple 的补充：

<code>from collections import deque

_# 创建一个双端队列_

deque_obj = deque()

_# 在头部插入元素_

deque_obj.appendleft(10)

deque_obj.appendleft(15)

deque_obj.appendleft(20)

_# 在尾部插入元素_

deque_obj.append(25)

deque_obj.append(30)

print(deque_obj)

_# 循环右移2次_

deque_obj.rotate(2)

print(deque_obj)

_# 从头部删除元素_

front = deque_obj.popleft()

print(front)

_#从尾部删除元素_

rear = deque_obj.pop()

print(rear)

print(deque_obj)

以下为运行结果：

环形队列

在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。这时，我们可以利用循环队列实现利用这个队列之前用过的空间，通过循环队列我们能使用这些空间去存储新的值。循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。

循环队列在逻辑上可以将其视为一个环，当队首指针等于队列长度减去一个单位后，再前进一个位置就自动到 0，即取余运算。我们可以使用 Python 的 collections 模块中的 deque 来实现一个循环队列，在创建 deque 时，可以指定最大长度 collections.deque(maxlen=x) ，如果 maxlen 没有指定或者是 None，deques 可以增长到任意长度。否则，deque 就限定到指定最大长度，当 deque 满了，有新项加入时，同样数量的项就从另一端弹出。示例代码如下：

<code>from collections import deque

# 创建一个大小为 3 的循环队列

queue = deque(maxlen=3)

# 添加元素

queue.append('a')

queue.append('b')

queue.append('c')

# 添加第四个元素会导致第一个元素被弹出

queue.append('d')

print(queue)

如下为运行结果：