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


猜你喜欢
- django中瀑布流初探img.html<!DOCTYPE html><html lang="en"&
- 硬币兑换问题:给定总金额为A的一张纸币,现要兑换成面额分别为a1,a2,....,an的硬币,且希望所得到的硬币个数最少。# 动态规划思想
- 上周跟朋友喝咖啡时聊起我想学Python,她恰好也有这个打算,顺便推荐了一本书《编程小白的第1本Python入门书》,我推送到Kindle后
- 写在之前SQLite 是一个小型的关系型数据库,它最大的特点在于不需要单独的服务、零配置。我们在之前讲过的两个数据库,不管是 MySQL 还
- string.Template()string.Template()内添加替换的字符, 使用"$"符号, 或 在字符串内
- 损失函数通过torch.nn包实现,1 基本用法criterion = LossCriterion() #构造函数有自己的参数loss =
- 1、mysql下载下载地址:https://dev.mysql.com/downloads/mysql/5.6.html<br>
- 前言Python文件默认的编码格式是ascii ,无法识别汉字,因为ascii码中没有中文。所以py文件中要写中文字符时,一般在开头加 #
- 1、先来看看为什么会出锁住: 数据库是一个多用户使用的共享资源。当多个用户并发地存取数据时,在数据库中就
- session的本质使用cookie来实现。原理大概是:http 带来服务端提前设置 cookie,服务端拿到标示用户身份的cookie,
- 在python3的sorted中去掉了cmp参数,转而推荐“key+lambda”的方式来排序。如果需要对python的list进行多级排序
- Matplotlib 是 Python 的二维绘图库,用于生成符合出版质量或跨平台交互环境的各类图形。图形解析与工作流图形解析 工
- 这篇文章主要介绍了python如何通过闭包实现计算器的功能,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要
- 今天处理了一个日期选择器的ie和ff的兼容问题,本来这种情况就很难找错误,找了好久才把错误定位到js中创建元素的方法document.cre
- 微软建议用Request.BinaryRead()读取表单数据,但由于这种方法读出的是二进制数据,需要对读出的数据逐字节进行分析,生成有意义
- 匿名函数匿名函数就是不需要显示式的指定函数名首先看一行代码:def calc(x,y): re
- 单线程实现单线程实现道理比较简单,这里尝试Soket连接3389,连接成功说明端口开放,否则说明没有开远程服务。随便修改了一下就ok了,代码
- “表情包”是现在非常流行的交流方式,通过一张图片就能把文字不能表达或不便于表达的情感给表示出来,表情包一经诞生,就统治了中国人的社交圈,尤其
- 本文实例讲述了Python3.5变量、数据结构、条件和循环语句、break与continue语句。分享给大家供大家参考,具体如下:1、变量:
- 一、获取安装包最近的版本为0.4.12,下载地址:http://sourceforge.net/projects/sysbench/二、编译