Python数据结构与算法中的队列详解(2)

目录
  • 传土豆
  • 总结

传土豆

队列的一个典型方法是模拟需要以 FIFO 方式管理数据的真实场景。考虑这样一个游戏：传土豆。在这个游戏中，成员们围成一圈，并依次尽可能快地传递一个土豆。在某个时刻，大家停止传递，此时手里有土豆的成员就得退出游戏。 重复上述过程，直到只剩下一个成员。

我们将针对传土豆游戏实现通用的模拟程序。该程序接受一个名字列表和一个用于计数的常量 num ，并且返回最后剩下的那个人的名字。

我们使用队列来模拟一个环。即假设握着土豆的人位于队列的头部。在模拟传土豆的过程中，程序将这个人的名字移出队列，然后立刻将其插入队列的尾部。随后，这个人会一直等待，直到再次到达队列的头部。在出列和入列 num 次之后，此时位于队列头部的人出局，新一轮游戏开始。如此反复，直到队列中只剩下一个名字（即队列的大小为 1）。

class Queue:
    def __init__(self):
        self.items = []            # 构建空队列
    def isEmpty(self):
        return self.items ==[]     # 判断是否为空
    def enqueue(self,item):
        self.items.insert(0, item) # 在队列尾部(列表左端)插入元素
    def dequeue(self):
        return self.items.pop()    # 在队列头部(列表右端)移出元素
    def size(self):
        return len(self.items)     # 队列(列表)长度
    def look(self):
        print(self.items)

def transmitPotato(nameList, num):
    simqueue = Queue()     # 创建队列
    for name in nameList:  # 遍历成员姓名列表
        simqueue.enqueue(name)   # 成员姓名入队列
    while simqueue.size() > 1:  # 当队列元素个数大于1时 循环执行
        for i in range(num):  # 循环num次(土豆传递num次)
            # 成员姓名从队头转换至队尾
            simqueue.enqueue(simqueue.dequeue())
        # 成员姓名出队(此成员淘汰出局)
        simqueue.dequeue()
    return simqueue.dequeue()  # 返回队列里最后剩下的名字

调用 transmitPotato 函数，使用 7 作为计数常量，将得到以下结果：

注意，在上例中，计数常量大于列表中的名字个数。 这不会造成问题，因为队列模拟了一个环。同时需要注意，当名字列表载入队列时，列表中的第一个名字出现在队列的头部。在上例中，小明是列表中的第一个元素，因此处在队列的最前端。

总结

本篇文章就到这里了，希望能够给你带来帮助，也希望您能够多多关注我们的更多内容!

赞 (0)

相关推荐

  • Python的数据结构与算法之队列详解

    Python的数据结构与算法之队列详解

    目录 模拟打印机任务队列过程 主要模拟步骤: ​构建队列程序 模拟打印程序 模拟打印过程(有注释) 总结 模拟打印机任务队列过程 计算机科学中也有众多的队列例子.比如计算机实验室有10台计算机,它们都与同一台打印机相连.当学生需要打印的时候,他们的打印任务会进入一个队列.该队列中的第一个任务就是即将执行的打印任务.如果一个任务排在队列的最后面,那么它必须等到所有前面的任务都执行完毕后才能执行.​ 学生向共享打印机发送打印请求,这些打印任务被存在一个队列中,并且按照先到先得的顺序执行.这样的设定可

  • Python数据结构与算法中的队列详解(1)

    Python数据结构与算法中的队列详解(1)

    目录 什么是队列? 构建一个队列 总结 什么是队列? 队列,与栈类似,是有序集合.添加操作发生在 “尾部”,移除操作只发生在 “头部”.新元素只从尾部进入队列,然后一直向前移动到头部,直到成为下一个被移除的元素.​ 最新添加的元素必须在队列的尾部等待,在队列中时间最长的元素则排在最前面.这种排序原则被称作FIFO(first-in first-out),即先进先出,也称先到先得.在日常生活中,我们经常排队,这便是最简单的队列例子.进电影院要排队,在超市结账要排队,买咖啡也要排队.好的队列只允许一

  • python队列基本操作和多线程队列

    python队列基本操作和多线程队列

    目录 一.队列基本操作 二.多线程队列 一.队列基本操作 from queue import Queue q = Queue(5)  # 创建一个容量为5的队列.如果给一个小于0的数,则队列为无限大小.(这是官方的解释,实际不是无限大小,而是跟内存有关) # 存储数据 q.put(123)  # 数值  q.put('hello world!')  # 字符串 q.put(['hello', 'world'])  # 列表 q.put(('hello', 'world'))  # 元组 q.pu

  • Python的线程使用队列Queue来改造转账场景

    Python的线程使用队列Queue来改造转账场景

    目录 一.看看转账场景的问题 二.这种问题怎么使用队列来解决呢? 三.总结 前篇我们了队列Queue和转账场景这次趁热学委展示一下使用队列解决转账场景的问题. 一.看看转账场景的问题 前面有两篇文章展示了转账反复读写amount,导致结果出错. xuewei_account = dict() xuewei_account['amount'] = 100 # amount为负数即是转出金额 def transfer(money):     for i in range(100000):      

  • Python线程之线程安全的队列Queue

    Python线程之线程安全的队列Queue

    目录 一.什么是队列? 二.队列基操入队/出队/查队列状态 三.Queue是一个线程安全的类 一.什么是队列? 像排队一样,从头到尾排成一排,还可以有人继续往后排队,这就是队列. 这里学委想说的是Queue这个类, 它是queue这个内置模块内的一个类. import queue q = queue.Queue(5) #可以传入参数指定队列大小 queue.Queue()# 不传或者给0或者<0的数字则创建一个无限长度的队列 它提供了很多函数,下面几个函数,我们使用的比较多: get: 获取并移

  • Python数据结构与算法中的队列详解(2)

    Python数据结构与算法中的队列详解(2)

    目录 传土豆 总结 传土豆 队列的一个典型方法是模拟需要以 FIFO 方式管理数据的真实场景.考虑这样一个游戏:传土豆.在这个游戏中,成员们围成一圈,并依次尽可能快地传递一个土豆.在某个时刻,大家停止传递,此时手里有土豆的成员就得退出游戏. 重复上述过程,直到只剩下一个成员. 我们将针对传土豆游戏实现通用的模拟程序.该程序接受一个名字列表和一个用于计数的常量 num ,并且返回最后剩下的那个人的名字. 我们使用队列来模拟一个环.即假设握着土豆的人位于队列的头部.在模拟传土豆的过程中,程序将这个人

  • Python数据结构与算法中的栈详解(2)

    Python数据结构与算法中的栈详解(2)

    目录 匹配括号 匹配符号 总结 匹配括号 接下来,我们使用栈解决实际的计算机科学问题.​ 比如我们都写过这样所示的算术表达式, ( 5 + 6 ) ∗ ( 7 + 8 ) / ( 4 + 3 ) (5 + 6) * (7 + 8) / (4 + 3) (5+6)∗(7+8)/(4+3),其中的括号用来改变计算顺序,或提升运算优先级.​ 匹配括号是指每一个左括号都有与之对应的一个右括号,并且括号对有正确的嵌套关系. 正确的嵌套关系: ( ( ) ( ) ( ) ( ) ) (()()()()) (

  • Python数据结构与算法中的栈详解(3)

    Python数据结构与算法中的栈详解(3)

    目录 前序.中序和后序表达式是什么? 我们为什么要学习前/后序表达式? 从中序向前序和后序转换 用Python实现从中序表达式到后序表达式的转换​ 计算后序表达式 总结 前序.中序和后序表达式是什么? 对于像B∗C 这样的算术表达式,可以根据其形式来正确地运算.在B∗C 的例子中,由于乘号出现在两个变量之间,因此我们知道应该用变量 B 乘以变量 C .​ 因为运算符出现在两个操作数的中间 ,所以这种表达式被称作中序表达式 .​ 来看另一个中序表达式的例子:A+B∗C.虽然运算符 “ + ” 和

  • Python数据结构与算法中的栈详解

    Python数据结构与算法中的栈详解

    目录 0.学习目标 1.栈的基本概念 1.1栈的基本概念 1.2栈抽象数据类型 1.3栈的应用场景 2.栈的实现 2.1顺序栈的实现 2.1.1栈的初始化 2.1.2求栈长 2.1.3判栈空 2.1.4判栈满 2.1.5入栈 2.1.6出栈 2.1.7求栈顶元素 2.2链栈的实现 2.2.1栈结点 2.2.2栈的初始化 2.2.3求栈长 2.2.4判栈空 2.2.5入栈 2.2.6出栈 2.3栈的不同实现对比 3.栈应用 3.1顺序栈的应用 3.2链栈的应用 3.3利用栈基本操作实现复杂算法 总

  • Python数据结构与算法中的栈详解(1)

    Python数据结构与算法中的栈详解(1)

    目录 什么是栈 构建一个栈 总结 什么是栈 栈有时也被称作“下推栈”.它是有序集合,添加操作和移除操作总发生在同一端,即栈的 “顶端”,栈的另一端则被称为 “底端”.所以最新添加的元素将被最先移除,而且栈中的元素离底端越近,代表其在栈中的时间越长. 这种排序原则被称作LIFO(last-in first-out),即后进先出.它提供了一种基于在集合中的时间来排序的方式. 最近添加的元素靠近顶端,旧元素则靠近底端. 栈的例子在日常生活中比比皆是.几乎所有咖啡馆都有一个由托盘或盘子构成的栈,你可以从

  • Python数据结构与算法之跳表详解

    Python数据结构与算法之跳表详解

    目录 0. 学习目标 1. 跳表的基本概念 1.1 跳表介绍 1.2 跳表的性能 1.3 跳表与普通链表的异同 2. 跳表的实现 2.1 跳表结点类 2.2 跳表的初始化 2.3 获取跳表长度 2.4 读取指定位置元素 2.5 查找指定元素 2.6 在跳表中插入新元素 2.7 删除跳表中指定元素 2.8 其它一些有用的操作 3. 跳表应用 3.1 跳表应用示例 0. 学习目标 在诸如单链表.双线链表等普通链表中,查找.插入和删除操作由于必须从头结点遍历链表才能找到相关链表,因此时间复杂度均为O(

  • 详解Python数据结构与算法中的顺序表

    详解Python数据结构与算法中的顺序表

    目录 0. 学习目标 1. 线性表的顺序存储结构 1.1 顺序表基本概念 1.2 顺序表的优缺点 1.3 动态顺序表 2. 顺序表的实现 2.1 顺序表的初始化 2.2 获取顺序表长度 2.3 读取指定位置元素 2.4 查找指定元素 2.5 在指定位置插入新元素 2.6 删除指定位置元素 2.7 其它一些有用的操作 3. 顺序表应用 3.1 顺序表应用示例 3.2 利用顺序表基本操作实现复杂操作 0. 学习目标 线性表在计算机中的表示可以采用多种方法,采用不同存储方法的线性表也有着不同的名称和特

  • Python数据结构与算法之使用队列解决小猫钓鱼问题

    Python数据结构与算法之使用队列解决小猫钓鱼问题

    本文实例讲述了Python数据结构与算法之使用队列解决小猫钓鱼问题.分享给大家供大家参考,具体如下: 按照<啊哈>里的思路实现这道题目,但是和结果不一样,我自己用一幅牌试了一下,发现是我的结果像一点,可能我理解的有偏差. # 小猫钓鱼 # 计算桌上每种牌的数量 # 使用defaultdict类,并设置默认类型为int型,即默认值为0 # cardcounts = defaultdict(int) # 不过deque有对应的方法 def henhenhaahaa(): from collecti

  • Python数据结构之图的存储结构详解

    Python数据结构之图的存储结构详解

    一.图的定义 图是一种比树更复杂的一种数据结构,在图结构中,结点之间的关系是任意的,任意两个元素之间都可能相关,因此,它的应用极广.图中的数据元素通常被称为顶点 ( V e r t e x ) (Vertex) (Vertex), V V V是顶点的有穷非空集合, V R VR VR是两个顶点之间的关系的集合(可以为空),可以表示为图 G = { V , { V R } } G=\{V,\{VR\}\} G={V,{VR}}. 二.相关术语 2.1 无向图 给定图 G = { V , { E }

随机推荐