济南做网站优化公司,现在电商做的设计用的什么网站,信用南京网站,个人网站名一、概述队列(Queue)是一种先进先出(FIFO)的线性数据结构#xff0c;插入操作在队尾(rear)进行#xff0c;删除操作在队首(front)进行。二、ADT队列ADT(抽象数据类型)一般提供以下接口#xff1a;Queue() 创建队列enqueue(item) 向队尾插入项dequeue() 返回队首的项#xf…一、概述队列(Queue)是一种先进先出(FIFO)的线性数据结构插入操作在队尾(rear)进行删除操作在队首(front)进行。二、ADT队列ADT(抽象数据类型)一般提供以下接口Queue() 创建队列enqueue(item) 向队尾插入项dequeue() 返回队首的项并从队列中删除该项empty() 判断队列是否为空size() 返回队列中项的个数队列操作的示意图如下三、Python实现使用Python的内建类型list列表可以很方便地实现队列ADT#!/usr/bin/env python# -*- coding: utf-8 -*-class Queue:def __init__(self):self.items []def enqueue(self, item):self.items.append(item)def dequeue(self):return self.items.pop(0)def empty(self):return self.size() 0def size(self):return len(self.items)四、应用著名的 约瑟夫斯问题(Josephus Problem)是应用队列(确切地说是循环队列)的典型案例。在 约瑟夫斯问题 中参与者围成一个圆圈从某个人(队首)开始报数报数到n1的人退出圆圈然后从退出人的下一位重新开始报数重复以上动作直到只剩下一个人为止。值得注意的是Queue类只实现了简单队列上述问题实际上需要用循环队列来解决。在报数过程中通过“将(从队首)出队的人再入队(到队尾)”来模拟循环队列的行为。具体代码如下#!/usr/bin/env python# -*- coding: utf-8 -*-def josephus(namelist, num):simqueue Queue()for name in namelist:simqueue.enqueue(name)while simqueue.size() 1:for i in xrange(num):simqueue.enqueue(simqueue.dequeue())simqueue.dequeue()return simqueue.dequeue()if __name__ __main__:print(josephus([Bill, David, Kent, Jane, Susan, Brad], 3))运行结果$ python josephus.pySusan
