数据结构与算法-(8)---队列(Queue)

简介: 数据结构与算法-(8)---队列(Queue)

队列的概念及特点🍁

队列(Queue):是一种有次序的数据集合,其特征是新数据项的添加总发生在一端 (通常称为“尾rear”端)

特点:First in first out-先进先出,就像排队一样先到先得.

而现存数据项的移除总发生在另一端 (通常称为“首front”端)

A queue is an ordered collection of items队列是有序的集合 where the addition of new itemshappens at one end, called the “rear,” and the removal of existing itemsoccurs at the other end, commonly called the “front.(只能在对头出,队尾入)

新加入的数据项必须在数据集末尾等待而等待时间最长的数据项则是队首

这种次序安排排的原则称为(FIFO:First-infirst-out)先进先出

或“先到先服务first-come first-served”

队列的例子出现在我们日常生活的方方面面:排队

队列仅有一个入口和一个出口不允许数据项直接插入队中,也不允许从中间移除数据项

对比栈和队列 🍁

仿照栈写队列的第一种写法🍁

class Queue:#初始化函数
    def __init__(self):
        self.items = []
    def isEmpty(self):
        return self.items == []
    def enqueue(self,item):#入队--#队列的对头对应列表的尾部-1
        self.items.insert(0,item)
    def dequeue(self):
        return self.items.pop()
    def size(self):
        return len(self.items)

仿照栈写队列的第二种写法🍁

class Queue:
    def __init__(self):
        self.items = []
    def isEmpty(self):
        return self.items  == []
    def enqueue(self,item):#队列的对头对应列表的头部0
        self.items.append(item)
    def dequeue(self):
        return self.items.pop(0)#将先进来的元素删除掉
    def size(self):
        return len(self.items)

注意:如果将pop(0)改为pop(),则会删除队列中最后添加元素不是最先添加的元素。这将导致队列的顺序被颠倒,不符合队列的FIFO(先进先出)原则。因此,我们需要使用pop(0)来删除队列中最先添加的元素

在Python中,pop()是一个内置的列表(list)方法,用于删除并返回列表中指定位置的元素。pop()方法接受一个可选参数索引,默认值为-1,表示要删除并返回最后一个元素。如果提供了索引,则会删除并返回指定位置的元素。

例如,对于以下列表:

lst = [1, 2, 3, 4, 5]

调用pop()方法:

lst.pop()

删除并返回最后一个元素5

[1, 2, 3, 4]

而调用pop(2)方法:

lst.pop(2)

则会删除并返回索引为2的元素3

[1, 2, 4, 5]

热土豆问题🍁

“击鼓传花”的土豆版本

传烫手的热土豆,鼓声停的时候,手里有土豆的小孩就要出列

#stack queue 本质都是列表,通过函数实现不同进出
class Queue:
    def __init__(self):
        self.items = []
    def isEmpty(self):
        return self.items  == []
    def enqueue(self,item):#队列的对头对应列表的头部0
         self.items.append(item)
    def dequeue(self):
        return self.items.pop(0)
    def size(self):
        return len(self.items)
def hotPotato(namelist, num):
    simqueue = Queue()#实例化对象-模拟空队列
    for name in namelist:#入队
        simqueue.enqueue(name)#开始游戏
    while simqueue.size() > 1:#队列长度>1
        for i in range(num):#---相当于计数器  控制土豆传递数量0 - num-1
            simqueue.enqueue(simqueue.dequeue())#确定拿着热土豆的人---传递一次,通过for循环让一次传递重复n次
        print(str(simqueue.dequeue())+" is eliminated .")#将拿热土豆的人输出
    return simqueue.dequeue()#将唯一剩下的那个人返回
print(hotPotato(["Bill","David","Susan","Jane","Kent","Brad"],7))#根据传递次数淘汰

土豆传递的规律:当达到7次传递以后,拿到热土豆的人就会被淘汰,然后这个热土豆就会传递给刚刚淘汰的那个人的下一个人,但是这个过程不计入到传递次数里面,当土豆从下一个人开始继续往下传递时才开始计算传递次数.  (A B C D 表示4个人)以下是每传递3次热土豆淘汰一个人的两轮游戏过程演示

目录
相关文章
|
18天前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
95 9
|
21天前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
1月前
初步认识栈和队列
初步认识栈和队列
60 10
|
1月前
|
存储 算法 定位技术
数据结构与算法学习二、稀疏数组与队列,数组模拟队列,模拟环形队列
这篇文章主要介绍了稀疏数组和队列的概念、应用实例以及如何使用数组模拟队列和环形队列的实现方法。
21 0
数据结构与算法学习二、稀疏数组与队列,数组模拟队列,模拟环形队列
|
1月前
【数据结构】-- 栈和队列
【数据结构】-- 栈和队列
17 0
|
1月前
探索数据结构:队列的的实现与应用
探索数据结构:队列的的实现与应用
|
1月前
|
存储 C语言
栈和队列题目练习
栈和队列题目练习
16 0
|
28天前
|
算法 安全 数据安全/隐私保护
基于game-based算法的动态频谱访问matlab仿真
本算法展示了在认知无线电网络中,通过游戏理论优化动态频谱访问,提高频谱利用率和物理层安全性。程序运行效果包括负载因子、传输功率、信噪比对用户效用和保密率的影响分析。软件版本:Matlab 2022a。完整代码包含详细中文注释和操作视频。
|
13天前
|
算法 数据挖掘 数据安全/隐私保护
基于FCM模糊聚类算法的图像分割matlab仿真
本项目展示了基于模糊C均值(FCM)算法的图像分割技术。算法运行效果良好,无水印。使用MATLAB 2022a开发,提供完整代码及中文注释,附带操作步骤视频。FCM算法通过隶属度矩阵和聚类中心矩阵实现图像分割,适用于灰度和彩色图像,广泛应用于医学影像、遥感图像等领域。
|
14天前
|
算法 调度
基于遗传模拟退火混合优化算法的车间作业最优调度matlab仿真,输出甘特图
车间作业调度问题(JSSP)通过遗传算法(GA)和模拟退火算法(SA)优化多个作业在并行工作中心上的加工顺序和时间,以最小化总完成时间和机器闲置时间。MATLAB2022a版本运行测试,展示了有效性和可行性。核心程序采用作业列表表示法,结合遗传操作和模拟退火过程,提高算法性能。

热门文章

最新文章

下一篇
无影云桌面