一、队列的定义

队列和栈一样，也是元素的有序集合，其元素的顺序取决于添加顺序或移除顺序，它也有两端，称作头部和尾部，栈中元素的添加操作和移除操作与栈不一样，添加操作发生在队列的尾部，移除操作发生在队列的头部。

队列中最先添加的元素将最先被移除，队列的排序原则被称作FIFO，即先进先出，最先添加的元素在队列头部，它最先最移出队列。

这种排列方式可以比喻成日常生活中的排队，很多人排成一队，所有的人从队的一端入队，从另一端出队，其中不能插队，后到的人若想进入队列，只能从队尾进入队列。

队列的相关应用例子：

在操作系统使用一些队列来控制计算机进程。

调度机制往往基于一个队列算法，其目标是尽可能快地执行程序，同时服务尽可能多的用户。在打字时，我们有时会发现字符出现的速度比击键速度慢。这是由于计算机正在做其他的工作。击键操作被放入一个类似于队列的缓冲区，以便对应的字符按正确的顺序显示。

二、队列实现步骤分析

与栈一样，通过Python中的类与对象，在类中定义几个方法，使用列表来实现队列的相关操作，这里是将列表的末尾作为队列的头部，队列的尾部是列表下标为0处的位置，队列的操作有：

1、创建一个空队列，通过构造方法创建一个空列表；

class Queue:
    def __init__(self):
        self.items = []  # 创建一个空队列，不需要参数，且会返回一个空队列

2、向队列（尾部）中添加元素，通过列表中的insert()实现添加新元素至队列中，由于是向队列尾部添加元素，添加列表中的第一个元素，即下标为0的元素；

def add(self, item):
        self.items.insert(0, item)  # 在队列的尾部添加元素，它需要一个元素作为参数

3、删除队列头部元素，通过列表中的pop()实现删除队列头部元素，由于未指定参数，所以该方法删除列表中的末尾元素，即删除的是队列头部元素；

def delete(self):
        return self.items.pop()  # 删除队列头部的元素，不需要参数，它会返回一个元素，并修改队列的内容

4、返回队列的头部元素，通过len()取得队列（列表）的长度，由于列表的下标是从0开始，所以要减1，即可索引返回第一位元素；

def display(self):
        return self.items[len(self.items) - 1]  # 返回队列的头部元素

5、检查队列是否为空，通过比较运算符“==”比较队列是否为空，若为空，则返回布尔值False，若不为空，则返回True；

def isEmpty(self):
        return self.items == []  # 检查队列是否为空，不需要参数，且返回一个布尔值来表示

6、返回队列中元素数目，通过len()取所有元素的值，即返回队列中元素的数目。

def size(self):
        return len(self.items)  # 返回队列中元素的数目，不需要参数，却返回一个整数来表示

三、队列的Python实现代码

完整代码如下：

# 通过列表实现队列的操作
class Queue:
    def __init__(self):
        self.items = []  # 创建一个空队列，不需要参数，且会返回一个空队列
    def add(self, item):
        self.items.insert(0, item)  # 在队列的尾部添加元素，它需要一个元素作为参数
    def delete(self):
        return self.items.pop()  # 删除队列头部的元素，不需要参数，它会返回一个元素，并修改队列的内容
    def display(self):
        return self.items[len(self.items) - 1]  # 返回队列的头部元素
    def isEmpty(self):
        return self.items == []  # 检查队列是否为空，不需要参数，且返回一个布尔值来表示
    def size(self):
        return len(self.items)  # 返回队列中元素的数目，不需要参数，却返回一个整数来表示
# 测试
q = Queue()# q是一个新创建的空队列，创建一个对象，即对象名称=类名称()
print(q.isEmpty())  # 查询队列是否为空
print(q.size())  # 返回队列中元素的数目
q.add(False)  # 在队列的尾部添加一个元素
print(q.display())# 返回队列的头部元素
q.add("qwet")
q.add(0)
print(q.display())
print(q.size())
q.delete()  # 删除队列头部的元素
print(q.display())
print(q.size())
print(q.isEmpty())

运行结果如下：

四、队列的应用

六人传土豆游戏

六个人传土豆游戏可模拟为队列的循环，通过队列来模拟一个环，即队列头部的出队移至尾部，然后入队进入队列的尾部从而一直循环传下去。在出队和入队N次之后，此时位于队列头部的人出局，新一轮的游戏开始，如此反复像一个圆环一样依次循环下去，直到队列中只剩下一个名字，即最后队伍的元素数目为1。

定义一个Pass()函数，传递土豆的常量为7，首先通过一个for循环遍历参加传递土豆游戏的所有人使其都添加到队列中，通过add(name_people)方法实现程序实现，name_people参数可传入一个列表，然后通过while循环条件为队列中的元素是否大于1，若大于1则while循环一直执行其内部代码块下去，在while循环内根据所输入的传递土豆的常量通过for循环中的range()函数确定相应的循环次数，然后依次将所删除的头部元素再添加到队列的尾部，若循环次数（传递土豆的常量）达到后，此时删除队列头部的元素，该人出局；若直到队伍的元素数目等于1时，结束while循环返回队列中的只剩下的那个元素，完整代码及解析如下：

# 通过列表实现队列的操作
class Queue:
    def __init__(self):
        self.items = []  # 创建一个空队列，不需要参数，且会返回一个空队列
    def add(self, item):
        self.items.insert(0, item)  # 在队列的尾部添加元素，它需要一个元素作为参数
    def delete(self):
        return self.items.pop()  # 删除队列头部的元素，不需要参数，它会返回一个元素，并修改队列的内容
    def display(self):
        return self.items[len(self.items) - 1]  # 返回队列的头部元素
    def isEmpty(self):
        return self.items == []  # 检查队列是否为空，不需要参数，且返回一个布尔值来表示
    def size(self):
        return len(self.items)  # 返回队列中元素的数目，不需要参数，却返回一个整数来表示
# 定义一个有参函数，参数为参加游戏的人peoples和传土豆的计数常量num
def Pass(peoples, num):
    q = Queue()# q是一个新创建的队列，创建一个对象，即对象名称=类名称()
    for name_people in peoples:  # 依次遍历参加游戏的人peoples使其添加到队列中
        q.add(name_people)
    while q.size() > 1:  # 若队列中的元素数目大于1则while循环一直执行下去
        for i in range(num):  # 根据所给的计数常量依次进行相应的循环次数
            q.add(q.delete())  # 将所删除的头部元素添加到队列的尾部
        q.delete()  # 计数常量到达后，删除队列头部的元素，即该人出局
    return q.delete()  # 返回队列中只剩一个元素
# 测试
print(Pass(["first", "second", "third", "four", "five", "six", "seven"], 7))

运行结果如下：

我们可以对六人传土豆游戏进行进一步的修改，比如允许随机计数，从而使每一轮的结果都不可预测，从而使游戏更加公平，由于是随机计数，可以使用random模块来生成随机整数，选定一个范围使计算机自动生成。

改进后的六人传土豆游戏程序代码及解析如下：

import random  # 导入random模块
# 通过列表实现队列的操作
class Queue:
    def __init__(self):
        self.items = []  # 创建一个空队列，不需要参数，且会返回一个空队列
    def add(self, item):
        self.items.insert(0, item)  # 在队列的尾部添加元素，它需要一个元素作为参数
    def delete(self):
        return self.items.pop()  # 删除队列头部的元素，不需要参数，它会返回一个元素，并修改队列的内容
    def display(self):
        return self.items[len(self.items) - 1]  # 返回队列的头部元素
    def isEmpty(self):
        return self.items == []  # 检查队列是否为空，不需要参数，且返回一个布尔值来表示
    def size(self):
        return len(self.items)  # 返回队列中元素的数目，不需要参数，却返回一个整数来表示
# 定义一个有参函数，参数为参加游戏的人peoples和传土豆的计数常量num
def Pass(peoples, num):
    q = Queue()
    for name_people in peoples:  # 依次遍历参加游戏的人peoples使其添加到队列中
        q.add(name_people)
    while q.size() > 1:  # 若队列中的元素数目大于1则while循环一直执行下去
        for i in range(num):  # 根据所输入的计数常量依次进行相应的循环次数
            q.add(q.delete())  # 将所删除的头部元素添加到队列的尾部
        q.delete()  # 计数常量达到后，删除队列头部的元素，即该人出局
    return q.delete()  # 返回队列中只剩一个元素
# 测试
num = random.randint(1, 100)  # 产生1到100之间的一个整数作为计数常量值，每次产生的整数不一定相同从而无法预测到结果
print(f"本次计数常量值为：{num}")
print(Pass(["first", "second", "third", "four", "five", "six", "seven"], num))

运行结果如下，每次产生的计数常量值不同导致结果不同：

第一次运行：

第二次运行：

五、双端队列的定义

双端队列与队列类似，它有前、后两端，但无论是添加元素或删除元素都可以在两端实现，它的排序原则可以为栈的后进先出，也可以为队列的先进先出，这取决于使用者，可以说双端队列是栈和队列的结合。

六、双端队列实现步骤分析

通过Python中的类与对象，在类中定义几个方法，使用列表来实现双端队列的相关操作，这里是将列表的末尾作为双端队列的前端，双端队列的后端是列表下标索引为0的位置，双端队列的操作有：

1、创建一个空双端队列，通过构造方法创建一个空列表；

class Deque:
    def __init__(self):
        self.items = []  # 创建一个空双端队列，不需要参数，且会返回一个空双端队列

2、向双端队列两端添加元素，分为向双端队列的前端或后端添加元素，前端通过append()方法向列表末尾添加元素，即向双端队列的前端添加；后端通过insert()方法在列表下标为0处列表的第一位元素，即双端队列的后端添加；

def addFront(self, item):
        self.items.append(item)  # 在双端队列的前端添加元素，它需要一个元素作为参数
    def addRear(self, item):
        self.items.insert(0, item)  # 在双端队列的后端添加元素，它需要一个元素作为参数

3、删除双端队列两端元素，分为删除双端队列的前端元素和删除双端队列的后端元素，都通过使用pop()方法，前端不需要指定参数，使其删除列表的末尾元素，即双端队列的前端元素；后端指定参数为0，使其删除列表中下标为0的元素，即列表的第一位元素，从而删除双端的后端元素；

def deleteFront(self):
        return self.items.pop()  # 删除双端队列前端的元素，不需要参数，它会返回一个元素，并修改双端队列的内容
    def deleteRear(self):
        return self.items.pop(0)  # 删除双端队列后端的元素，不需要参数，它会返回一个元素，并修改双端队列的内容

4、返回双端队列的两端元素，通过len()先取得列表的长度，由于下标是从0开始，所以要减1，从而索引得到双端队列的前端元素；通过索引列表下标为0的元素得到双端队列的后端元素；

def displayFront(self):
        return self.items[len(self.items) - 1]  # 返回双端队列的前端元素
    def displayRear(self):
        return self.items[0]  # 返回双端队列的后端元素

5、检查双端队列是否为空，通过比较运算符“==”比较队列是否为空，若为空，则返回布尔值False，若不为空，则返回True；

def isEmpty(self):
        return self.items == []  # 检查双端队列是否为空，不需要参数，且返回一个布尔值来表示

6、返回双端队列中元素数目，通过len()取所有元素的值，即返回队列中元素的数目。

七、双端队列的Python实现代码

完整代码如下：

# 通过列表实现双端队列的操作
class Deque:
    def __init__(self):
        self.items = []  # 创建一个空双端队列，不需要参数，且会返回一个空双端队列
    def addFront(self, item):
        self.items.append(item)  # 在双端队列的前端添加元素，它需要一个元素作为参数
    def addRear(self, item):
        self.items.insert(0, item)  # 在双端队列的后端添加元素，它需要一个元素作为参数
    def deleteFront(self):
        return self.items.pop()  # 删除双端队列前端的元素，不需要参数，它会返回一个元素，并修改双端队列的内容
    def deleteRear(self):
        return self.items.pop(0)  # 删除双端队列后端的元素，不需要参数，它会返回一个元素，并修改双端队列的内容
    def displayFront(self):
        return self.items[len(self.items) - 1]  # 返回双端队列的前端元素
    def displayRear(self):
        return self.items[0]  # 返回双端队列的后端元素
    def isEmpty(self):
        return self.items == []  # 检查双端队列是否为空，不需要参数，且返回一个布尔值来表示
    def size(self):
        return len(self.items)  # 返回双端队列中元素的数目，不需要参数，却返回一个整数来表示
# 测试
d = Deque()  # d是一个新创建的空双端队列，创建一个对象，即对象名称=类名称()
print(d.isEmpty())  # 检查双端队列是否为空
print(d.size())  # 返回双端队列中元素的数目
d.addFront(123456)  # 向双端队列的前端添加元素
d.addFront("45@d")
d.addRear("2021-1-14")  # 向双端队列的后端添加元素
d.addRear("Z")
print(d.size())
print(d.displayFront())  # 返回双端队列的前端元素
print(d.displayRear())  # 返回双端队列的后端元素
d.deleteFront()  # 删除双端队列的前端元素
print(d.size())
print(d.displayFront())
d.deleteRear()  # 删除双端队列的后端元素
print(d.size())
print(d.displayRear())
print(d.isEmpty())

运行结果如下：

测试图例：

八、双端队列的应用

回文检测器

回文是指正着读和反着读都一样的字符串，即成对称的字符串，例如rar、toot、12321等等，我们可以通过一个双端队列来存储字符串中的字符，通过从左往右的顺序将字符串中的字符添加到双端队列的后端，然后通过定义一个条件，只有当双端队列的前端和后端相同时，才相互抵消删除元素。一直这样删除下去，若输入的字符串字符数为偶数，则最后将没有字符；若输入的字符串字符数为奇数，则最后只剩下一个字符，从而达到检测回文的目的。

回文检测器的完整代码及解析如下：

# 通过列表实现双端队列的操作
class Deque:
    def __init__(self):
        self.items = []  # 创建一个空双端队列，不需要参数，且会返回一个空双端队列
    def addFront(self, item):
        self.items.append(item)  # 在双端队列的前端添加元素，它需要一个元素作为参数
    def addRear(self, item):
        self.items.insert(0, item)  # 在双端队列的后端添加元素，它需要一个元素作为参数
    def deleteFront(self):
        return self.items.pop()  # 删除双端队列前端的元素，不需要参数，它会返回一个元素，并修改双端队列的内容
    def deleteRear(self):
        return self.items.pop(0)  # 删除双端队列后端的元素，不需要参数，它会返回一个元素，并修改双端队列的内容
    def displayFront(self):
        return self.items[len(self.items) - 1]  # 返回双端队列的前端元素
    def displayRear(self):
        return self.items[0]  # 返回双端队列的后端元素
    def isEmpty(self):
        return self.items == []  # 检查双端队列是否为空，不需要参数，且返回一个布尔值来表示
    def size(self):
        return len(self.items)  # 返回双端队列中元素的数目，不需要参数，却返回一个整数来表示
# 定义一个有参函数，其参数是输入的字符串
def palindromic(string):
    d = Deque()  # d是一个新创建的空双端队列，创建一个对象，即对象名称=类名称()
    for i in string:
        d.addRear(i)  # 通过addRear()方法向双端队列的后端添加元素
    stillEqual = True
    while d.size() > 1 and stillEqual:  # 若双端队列中元素的数目大于1且变量stillEqual为True时while循环一直下去
        first = d.deleteFront()  # 通过删除双端列表前端的元素，该方法返回的元素赋值给变量first
        last = d.deleteRear()  # 通过删除双端列表后端的元素，该方法返回的元素赋值给变量last
        if first != last:
            stillEqual = False  # 若左右两端的元素不相同则对变量stillEqual赋值False
        return stillEqual  # 返回变量stillEqual的值
# 测试
print(palindromic("我为人人，人人为我"))
print(palindromic("141"))
print(palindromic("qwer"))
print(palindromic("refer"))
print(palindromic("did"))

运行结果如下：

Python数据结构学习笔记——队列和双端队列

一、队列的定义

二、队列实现步骤分析

三、队列的Python实现代码

四、队列的应用

五、双端队列的定义

六、双端队列实现步骤分析

七、双端队列的Python实现代码

八、双端队列的应用

热门文章

最新文章

相关课程

相关电子书

相关实验场景

推荐镜像

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

Python数据结构学习笔记——队列和双端队列

一、队列的定义

二、队列 实现步骤分析

三、队列的Python实现代码

四、队列的应用

五、双端队列的定义

六、双端队列 实现步骤分析

七、双端队列的Python实现代码

八、双端队列的应用

热门文章

最新文章

相关课程

相关电子书

相关实验场景

推荐镜像

二、队列实现步骤分析

六、双端队列实现步骤分析