Python数据结构之队列详解

Mason

发布时间：2026-10-12| 2人浏览过

原创

本文深入解析Python中队列数据结构的实现原理，涵盖顺序队列（含循环队列与动态扩容）和链式队列两种核心存储方式。详细阐述入队、出队、判空及求长等操作的时间复杂度，并通过Python代码演示具体实现。最后，利用队列特性解决经典的约瑟夫斯环算法问题，展示队列在复杂场景下的实际应用价值。

0. 学习目标

栈和队列作为程序设计中常见的数据类型，从数据结构视角看，二者均属于操作受限的线性表，其基本操作是线性表操作的子集；但从数据类型的抽象角度看，它们与通用线性表存在显著差异。本节将系统介绍队列的定义、多种实现方案及其实际应用场景。通过本节学习，需掌握以下核心内容：

队列的基本概念及不同实现方法
队列基本操作的实现及时间复杂度
利用队列的基本操作实现复杂算法

1. 队列的基本概念

1.1 队列的基本概念

队列（Queue）是一种特殊的线性表，其插入和删除操作分别被限制在序列的两端。新元素从一端（队尾）插入，而已有元素只能从另一端（队头）删除。对于队列而言，允许插入元素的一端称为队尾（rear），允许取出元素的一端称为队头（front）。

在队列中，数据的到达顺序至关重要。最新添加的元素必须位于队尾，而在队列中停留时间最长的元素则位于最前端。这种排序原则被称为先进先出（First In First Out，FIFO），有时也称为后进后出（Last In Last Out, LILO）。

队列在现实生活中无处不在，例如就餐排队就是一个典型的队列实例：最早进入队列的人优先就餐，后来者则需排在队尾等待。假设队列为 Q=(a0,a1,...,an)，其中 a0 为队头元素，an 为队尾元素。元素按 a0,a1,...,an 的顺序入队（enqueue），出队（dequeue）也必须遵循此顺序。队头元素 a0 是第一个出队的元素，只有当 a0,a1,...,an-1 全部出队后，an 才能退出队列。下图展示了一个简单的队列示例：

通过观察元素的添加和移除顺序，可以直观理解队列的核心思想。下图展示了队列元素的入队和出队过程，可见队列中元素的插入顺序与移除顺序完全一致。

1.2 队列抽象数据类型

除了入队（enqueue）和出队（dequeue）这两个主要操作外，队列还包含初始化、判断队空和求队长度等辅助操作。具体而言，队列的抽象数据类型定义如下：

1.3 队列的应用场景

队列具有广泛的应用场景，例如：

在作业优先级相同的情况下，操作系统依据作业的到达顺序来调度执行；
击键操作被存入类似队列的缓冲区，确保字符按正确顺序显示；
模拟现实世界中的排队场景；
支持多道程序设计；
处理异步数据传输；

除上述应用外，在后续学习中还将看到队列作为许多算法的辅助数据结构。

2. 队列的实现

与线性表类似，队列同样支持顺序存储和链式存储两种表示方式。

2.1 顺序队列的实现

类似于顺序栈，队列的顺序存储结构利用一组地址连续的存储单元依次存放从队头到队尾的元素。同时，需要使用两个指针 front 和 rear 分别指示队头元素和队尾元素的位置。初始化空队列时，设置 front=rear=0；当元素入队时，rear 加 1；当元素出队时，front 加 1，具体过程如下所示：

从上述示例可以看出，位于队头之前的存储空间被浪费。为解决这一问题，可将顺序队列视为环状空间，即将最后一个元素与第一个元素视为连续，如下图所示：

由上图可知，当队列满与队列空时，均满足 front=rear，因此无法仅通过 front==rear 判断队列是否已满。针对此问题，有两种解决方案：1) 设置标志位指示队列中是否还有空闲空间；2) 放弃一个元素空间，即当 front 指针位于 rear 指针的下一位时（(rear+1)%max_size=front），判定队列为满。以下实现采用第二种方案。

顺序队列可分为固定长度和动态长度两种。当队列满时，定长顺序队列会抛出栈满异常，而动态顺序队列则会动态申请空闲空间。

2.1.1 队列的初始化

顺序队列的初始化需要包含 4 部分信息：queue 列表用于存储数据元素，max_size 用于记录 queue 列表的最大长度，front 和 rear 分别用于记录队头元素和队尾元素的索引：

class Queue:
    def __init__(self, max_size=5):
        self.max_size = max_size
        self.queue = [None] * self.max_size
        self.front = 0
        self.rear = 0

2.1.2 求队列长度

由于 front 和 rear 分别记录队头和队尾元素的索引，我们可以方便地计算队列长度。同时需考虑循环队列的情况，front 可能大于 rear，不能直接通过 rear-front 计算，需利用公式解决此问题：

Python 实现如下：

    def size(self):
        return (self.rear-self.front+self.max_size) % self.max_size

2.1.3 判队列空

根据 front 和 rear 的值，可以方便地判断队列是否为空：

    def isempty(self):
        return self.rear==self.front

2.1.4 判队列满

根据 front 和 rear 的值，可以方便地判断队列是否还有空余空间：

    def isfull(self):
        return ((self.rear+1) % self.max_size == self.front)

2.1.5 入队

入队时，需首先判断队列中是否还有空闲空间。根据队列为定长顺序队列或动态顺序队列，入队操作略有不同：

[定长顺序队列的入队操作] 如果队满，则引发异常：

    def enqueue(self, data):
        if not self.isfull():
            self.queue[self.rear] = data
            self.rear = (self.rear+1) % self.max_size
        else:
            raise IndexError("Full Queue Exception")

[动态顺序队列的入队操作] 如果队列满，则首先申请新空间，然后再执行入队操作：

    def resize(self):
        new_size = 2 * self.max_size
        new_queue = [None] * new_size
        for i in range(self.max_size):
            new_queue[i] = self.queue[i]
        self.queue = new_queue
        self.max_size = new_size

    def enqueue(self, data):
        if self.isfull():
            self.resize()
        self.queue[self.rear] = data
        self.rear = (self.rear+1) % self.max_size

入队的时间复杂度为 O(1)。需要注意的是，虽然动态顺序队列满时，原队列中的元素需先复制到新队列中再添加新元素，但参考《顺序表及其操作实现》中关于顺序表追加操作的说明，由于 n 次入队操作的总时间 T(n) 与 O(n) 成正比，因此队列的摊销时间复杂度可视为 O(1)。

2.1.6 出队

若队列不空，则删除并返回队头元素：

    def dequeue(self):
        if not self.isempty():
            result = self.queue[self.front]
            self.front = (self.front+1) % self.max_size
            return result
        else:
            raise IndexError("Empty Queue Exception")

2.1.7 求队头元素

若队列不空，则返回队头元素：

    def head(self):
        if not self.isempty():
            result = self.queue[self.front]
            return result
        else:
            raise IndexError("Empty Queue Exception")

2.2 链队列的实现

队列的另一种存储表示方式是使用链式存储结构，因此常称为链队列。其中，enqueue 操作通过链表尾部插入元素实现，dequeue 操作通过从头部删除节点实现。

2.2.1 队列结点

队列的结点实现与链表无异：

class Node:
    def __init__(self, data=None):
        self.data = data
        self.next = None
    def __str__(self):
        return str(self.data)

2.2.2 队列的初始化

队列的初始化函数中，使队头指针 front 和 rear 均指向 None，并初始化队列长度：

class Queue:
    def __init__(self):
        self.front = None
        self.rear = None
        self.num = 0

2.2.3 求队列长度

返回 size 的值用于获取队列长度。若没有 size 属性，则需遍历整个链表才能得到队列长度：

    def size(self):
        return self.num

2.2.4 判队列空

根据队列的长度可以很容易地判断队列是否为空：

    def isempty(self):
        return self.num <= 0

2.2.5 入队

入队时，在队尾插入新元素，并将队尾指针 rear 指向新元素。若队列为空，还需将队头指针 front 也指向此元素：

    def enqueue(self, data):
        node = Node(data)
        if self.front is None:
            self.rear = node
            self.front = self.rear
        else:
            self.rear.next = node
            self.rear = node
        self.num += 1

2.2.6 出队

若队列不空，则删除并返回队头元素，同时需更新队头指针 front 指向原队头结点的后继结点。若出队元素为队列中最后一个结点，则需更新队尾指针 rear：

    def dequeue(self):
        if self.isempty():
            raise IndexError("Empty Queue Exception")
        result = self.front.data
        self.front = self.front.next
        self.num -= 1
        if self.isempty():
            self.rear = self.front
        return result

2.2.7 求队头元素

若队列不空，则返回队头元素：

    def head(self):
        if self.isempty():
            raise IndexError("Empty Queue Exception")
        result = self.front.data
        return result

2.3 队列的不同实现对比

队列的不同实现对比与栈的不同实现类似，可参考《栈及其操作实现》。

3. 队列应用

接下来，我们将首先测试上述实现的队列，以验证操作的有效性，随后利用实现的基本操作来解决实际算法问题。

3.1 顺序队列的应用

首先初始化一个顺序队列 queue，然后测试相关操作：

# 初始化一个最大长度为5的队列
q = Queue(5)
print('队列空?', q.isempty())
for i in range(4):
    print('入队元素：', i)
    q.enqueue(i)
print('队列满?', q.isfull())
print('队头元素：', q.head())
print('队列长度为：', q.size())
while not q.isempty():
    print('出队元素：', q.dequeue())

测试程序输出结果如下：

队列空? True 入队元素： 0 入队元素： 1 入队元素： 2 入队元素： 3 # 队列中弃用一个空间，因此队列中有4个元素即满队列满? True 队头元素： 0 队列长度为： 4 出队元素： 0 出队元素： 1 出队元素： 2 出队元素： 3

3.2 链队列的应用

首先初始化一个链队列 queue，然后测试相关操作：

# 初始化新队列
q = Queue()
print('队列空?', q.isempty())
for i in range(4):
    print('入队元素：', i)
    q.enqueue(i)
print('队头元素：', q.head())
print('队列长度为：', q.size())
while not q.isempty():
    print('出队元素：', q.dequeue())

测试程序输出结果如下：

队列空? True 入队元素： 0 入队元素： 1 入队元素： 2 入队元素： 3 队头元素： 0 队列长度为： 4 出队元素： 0 出队元素： 1 出队元素： 2 出队元素： 3

3.3 利用队列基本操作实现复杂算法

考虑经典的约瑟夫斯环问题：n 个人围成一圈，从第 1 个人开始报数，第 m 个将被淘汰，重复上述过程，直到只剩下一个人，其余人都将被淘汰。

我们使用队列来模拟一个环，如下图所示。从队列的头部开始，将位于队首的人移出队列并立刻将其插入队列的尾部，之后此人会一直等待，直到其再次到达队列的头部。在出列和入列 m-1 次之后，位于队列头部的人出局（即第 m 个人），然后新一轮游戏开始；如此反复，直到队列中只剩下一个人（队列的大小为 1）。

def Josephus(name_list, m):
    queue = Queue()
    for name in name_list:
        queue.enqueue(name)
    while queue.size() > 1:
        for i in range(m-1):
            queue.enqueue(queue.dequeue())
        queue.dequeue()
    return queue.head()
# n=6, m=5
result = Josephus(["A", "B", "C", "D", "E", "F"], 5)
print('幸存的人为', result)

程序输出结果如下：