本文实例讲述了Python实现的数据结构与算法之队列。分享给大家供大家参考。具体分析如下:
一、概述
队列(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() == 0
def size(self):
return len(self.items)
四、应用
著名的 约瑟夫斯问题(Josephus Problem)是应用队列(确切地说,是循环队列)的典型案例。在 约瑟夫斯问题 中,参与者围成一个圆圈,从某个人(队首)开始报数,报数到n+1的人退出圆圈,然后从退出人的下一位重新开始报数;重复以上动作,直到只剩下一个人为止。
值得注意的是,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.py
Susan
希望本文所述对大家的Python程序设计有所帮助。
本文向大家介绍Python实现的数据结构与算法之双端队列详解,包括了Python实现的数据结构与算法之双端队列详解的使用技巧和注意事项,需要的朋友参考一下 本文实例讲述了Python实现的数据结构与算法之双端队列。分享给大家供大家参考。具体分析如下: 一、概述 双端队列(deque,全名double-ended queue)是一种具有队列和栈性质的线性数据结构。双端队列也拥有两端:队首(front
本文向大家介绍C++数据结构与算法之双缓存队列实现方法详解,包括了C++数据结构与算法之双缓存队列实现方法详解的使用技巧和注意事项,需要的朋友参考一下 本文实例讲述了C++数据结构与算法之双缓存队列实现方法。分享给大家供大家参考,具体如下: “双缓存队列”是我在一次开发任务中针对特殊场景设计出来的结构。使用场景为:发送端持续向接收端发送数据包——并且不理会接收端是否完成业务逻辑。由于接收端在任何情
本文向大家介绍Python实现的数据结构与算法之链表详解,包括了Python实现的数据结构与算法之链表详解的使用技巧和注意事项,需要的朋友参考一下 本文实例讲述了Python实现的数据结构与算法之链表。分享给大家供大家参考。具体分析如下: 一、概述 链表(linked list)是一组数据项的集合,其中每个数据项都是一个节点的一部分,每个节点还包含指向下一个节点的链接。 根据结构的不同,链表可以分
本文向大家介绍JavaScript数据结构与算法之队列原理与用法实例详解,包括了JavaScript数据结构与算法之队列原理与用法实例详解的使用技巧和注意事项,需要的朋友参考一下 本文实例讲述了JavaScript数据结构与算法之队列原理与用法。分享给大家供大家参考,具体如下: 队列是一种列表,不同的是队列只能在队尾插入元素,在队首删除元素。队列用于存储按顺序排列的数据,先进先出,这点和栈不一样(
本文向大家介绍JavaScript数据结构与算法之栈与队列,包括了JavaScript数据结构与算法之栈与队列的使用技巧和注意事项,需要的朋友参考一下 学习起因 曾经有一次在逛V2EX时,碰到这么一个帖子。 数学完全还给老师了,想学回一些基础数学,大概是高中程度的,有什么书籍推荐? 发帖的楼主大学没有高数课程,出去工作时一直在从事前端的工作。感觉到数学知识的匮乏,所以想补一补数学。 看了看帖子,感
本文向大家介绍Python实现的数据结构与算法之快速排序详解,包括了Python实现的数据结构与算法之快速排序详解的使用技巧和注意事项,需要的朋友参考一下 本文实例讲述了Python实现的数据结构与算法之快速排序。分享给大家供大家参考。具体分析如下: 一、概述 快速排序(quick sort)是一种分治排序算法。该算法首先 选取 一个划分元素(partition element,有时又称为pivo