Python 实现数据结构-循环队列的操作方法
作者:浩然haoran 发布时间:2022-10-13 23:15:00
标签:python,数据结构,循环队列
今天我们来到了循环队列这一节,之前的文章中,我介绍过了用python自带的列表来实现队列,这是最简单的实现方法。
但是,我们都知道,在列表中删除第一个元素和删除最后一个元素花费的时间代价是不一样的,删除列表的第一个元素,那么在它之后的所有元素都要进行移动。所以当列表特别长的时候,这个代价就比较明显了。我们本文介绍的循环队列可以避免这个问题,同样我们上篇文章提到的用链表实现的方法也可以避免。
下面,我们来介绍循环队列。
循坏队列
循环队列,就是将普通的队列首尾连接起来, 形成一个环状,并分别设置首尾指针,用来指明队列的头和尾。每当我们插入一个元素,尾指针就向后移动一位,当然,在这里我们队列的最大长度是提前定义好的,当我们弹出一个元素,头指针就向后移动一位。
这样,列表中就不存在删除操作,只有修改操作,从而避免了删除前面节点造成的代价大的问题。
好,话不多说,我们用代码来实现一下
class Loopqueue:
def __init__(self, length):
self.head = 0
self.tail = 0
self.maxSize = length
self.cnt = 0
self.__list = [None]*length
这里同样,我们定义一个队列类,在实例化循环队列的时候,要求指定队列的大小,除了首尾指针以及队列最大长度之外,我们还声明一个表示队列当前长度的属性cnt。
接下来我们给队列增加一些操作:
判空
def isEmpty(self):
return self.cnt == 0
判满
def isFull(self):
return self.cnt == self.maxSize
添加元素
def push(self, data):
if self.isFull():
return False
if self.isEmpty():
self.__list[0] = data
self.head = 0
self.tail = 0
self.cnt = 1
return True
self.tail = (self.tail+1)%self.maxSize
self.cnt += 1
self.__list[self.tail] = data
return True
弹出元素
def pop(self):
if self.isEmpty():
return False
data = self.__list[self.head]
self.head = (self.head+1)%self.maxSize
self.cnt -= 1
return data
清空队列
def clear(self):
self.head = 0
self.tail = 0
self.cnt = 0
return True
定义len和print函数
def __len__(self):
return self.cnt
def __str__(self):
s = ''
for i in range(self.cnt):
index = (i + self.head) % self.maxSize
s += str(self.__list[index])+' '
return s
OK,我们的循环队列类就定义好了,如果你看过介绍队列的文章,就会发现循环队列和普通队列的操作在逻辑上还是有一些相似的。
总结
以上所述是小编给大家介绍的Python 实现数据结构-循环队列的操作方法,网站的支持!
如果你觉得本文对你有帮助,欢迎转载,烦请注明出处,谢谢!
来源:https://www.cnblogs.com/dongyangblog/p/11198456.html
0
投稿
猜你喜欢
- 一、缺失数据剔除1. python 方式获取所有的缺失值,返回一个 true 和 false 的表df.isnull()统计缺失值,按照每一
- 如下所示:#coding:utf8import pandas as pdimport numpy as npfrom pandas impo
- 近来,打开微信群发消息,就会秒收到一些活跃分子的回复,有的时候感觉对方回答很在理,但是有的时候发现对方的回答其实是驴唇不对马嘴,仔细深究发现
- 应用场景:状态不是200的URL重试多次代码比较简单还有部分注释python2.7实现:# -*-coding:utf-8-*-"
- 前言:线程是指进程内的一个执行单元,也是进程内的可调度实体.与进程的区别:(1) 地址空间:进程内的一个执行单元;进程至少有一个线程;它们共
- 本文通过Python3+PyQt5实现自定义部件–分数滑块。它既能支持键盘也支持鼠标,使用物理(视口)坐标通过绘制方式显示。#!/usr/b
- reshape(shape) : 不改变数组元素,返回一个shape形状的数组,原数组不变。是对每行元素进行处理resize(shape)
- 目录1. 序列2. 列表2.1 列表的特性2.1.1 列表的连接操作符和重复操作符2.1.3 列表的索引2.1.4 列表的切片2.1.5 列
- Index.asp:程序代码<html><head><meta http-equiv="Conten
- 大家都知道,linux里一切皆为文件,在linux/unix的根目录下,有个/proc目录,这个/proc 是一种内核和内核模块用来向进程(
- 在SQL Server中进行开发会让你身处险地,并且寻找快速解决方案。我们编辑了前十名关于SQL Server开发的常见问题。对常见的针对表
- isNaN函数 返回一个 Boolean 值,指明提供的值是否是保留值 NaN (不是数字)。 NaN 即 Not a Number isN
- 前言Python代码缩进和测试模块是大家学习python必不可少的一部分,本文主要介绍了关于Python代码缩进和测试模块的相关内容,分享出
- 本文主要讲python支持zookeeper的接口库安装和使用。zk的python接口库有zkpython,还有kazoo,下面是zkpyt
- 经常地我们需要编写跨平台的脚本,但是由于不同的平台的差异性,我们不得不获得当前所工作的平台(操作系统类型)。代码如下:import plat
- 有一道题: 比较两个列表范围,如果包含的话,返回TRUE,否则FALSE。 详细题目如下:Create a function, this f
- 可能不少学习javascript在使用call,apply,callee时会感到困惑,以下希望对于你有所帮助:1、它是函数的方法或属性;2、
- 本文实例为大家分享了python实现txt文件格式转换为arff格式的具体代码,供大家参考,具体内容如下将文件读取出来的时候默认都是字符型的
- 话说用了就要有点产出,要不然过段时间又忘了,所以在这里就记录一下试用Kafka的安装过程和php扩展的试用。实话说,如果用于队列的话,跟PH
- 为什么要引入线程池如果在程序中经常要用到线程,频繁的创建和销毁线程会浪费很多硬件资源,所以需要把线程和任务分离。线程可以反复利用,省去了重复