数据结构与算法-(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次热土豆淘汰一个人的两轮游戏过程演示

目录
相关文章
|
7天前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
71 9
|
10天前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
29天前
初步认识栈和队列
初步认识栈和队列
57 10
|
29天前
|
存储 算法 定位技术
数据结构与算法学习二、稀疏数组与队列,数组模拟队列,模拟环形队列
这篇文章主要介绍了稀疏数组和队列的概念、应用实例以及如何使用数组模拟队列和环形队列的实现方法。
20 0
数据结构与算法学习二、稀疏数组与队列,数组模拟队列,模拟环形队列
|
24天前
【数据结构】-- 栈和队列
【数据结构】-- 栈和队列
13 0
|
29天前
探索数据结构:队列的的实现与应用
探索数据结构:队列的的实现与应用
|
29天前
|
存储 C语言
栈和队列题目练习
栈和队列题目练习
15 0
|
26天前
|
存储 人工智能 算法
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法,这两种算法分别用于解决单源和多源最短路径问题,并且提供了Java语言的实现代码。
62 3
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
|
29天前
|
机器学习/深度学习 存储 缓存
数据结构与算法学习十:排序算法介绍、时间频度、时间复杂度、常用时间复杂度介绍
文章主要介绍了排序算法的分类、时间复杂度的概念和计算方法,以及常见的时间复杂度级别,并简单提及了空间复杂度。
20 1
数据结构与算法学习十:排序算法介绍、时间频度、时间复杂度、常用时间复杂度介绍
|
29天前
|
搜索推荐 算法
数据结构与算法学习十四:常用排序算法总结和对比
关于常用排序算法的总结和对比,包括稳定性、内排序、外排序、时间复杂度和空间复杂度等术语的解释。
17 0
数据结构与算法学习十四:常用排序算法总结和对比

热门文章

最新文章