Python实现的数据结构与算法之队列详解
作者:RussellLuo 时间:2021-06-06 09:58:05
本文实例讲述了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,队列
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
基于python判断字符串括号是否闭合{}[]()
2022-03-25 15:58:45
记Qzone项目组视觉设计标注的前前后后
2010-03-24 18:03:00
![](https://img.aspxhome.com/file/UploadPic/20103/24/1321290-25s.jpg)
tensorflow转onnx的实现方法
2022-07-08 23:04:51
Window 7/XP 安装Apache 2.4与PHP 5.4 的过程详解
2023-11-24 09:28:09
python+pillow绘制矩阵盖尔圆简单实例
2022-07-04 02:44:39
![](https://img.aspxhome.com/file/2023/8/80428_0s.jpg)
Python入门第1/10页
2023-03-19 19:34:34
Python脚本实现网卡流量监控
2022-11-27 11:36:51
在win和Linux系统中python命令行运行的不同
2023-08-03 05:16:22
python调用cmd命令行制作刷博器
2023-07-26 15:18:35
从零开始学Golang的接口
2023-10-09 02:26:03
Python学习之异常中的finally使用详解
2021-09-08 02:21:38
Python与数据库的交互问题小结
2021-11-14 11:46:47
利用Python绘画双摆操作分享
2022-12-08 21:30:36
![](https://img.aspxhome.com/file/2023/7/85107_0s.png)
Python 冒泡,选择,插入排序使用实例
2021-11-24 21:42:35
IIS6.0下ASP的新增功能
2007-08-22 14:55:00
python获取代码运行时间的实例代码
2023-11-04 02:25:10
分析Python感知线程状态的解决方案之Event与信号量
2022-05-11 07:23:35
![](https://img.aspxhome.com/file/2023/3/76783_0s.jpg)
python3环境搭建过程(利用Anaconda+pycharm)完整版
2022-01-16 06:04:47
![](https://img.aspxhome.com/file/2023/5/75265_0s.png)
python 快速排序代码
2022-04-15 00:00:21
python装饰器底层原理详解
2021-12-31 08:48:32
![](https://img.aspxhome.com/file/2023/6/75216_0s.png)