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

用户10920432

发布于 2024-01-18 17:09:48

1250

发布于 2024-01-18 17:09:48

文章被收录于专栏：Python数据结构与算法

队列的概念及特点🍁

队列(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))#根据传递次数淘汰