Python 实现数据结构-循环队列的操作方法

yipeiwu_com6年前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 实现数据结构-循环队列的操作方法,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对【听图阁-专注于Python设计】网站的支持!
如果你觉得本文对你有帮助,欢迎转载,烦请注明出处,谢谢!

相关文章

Python实现E-Mail收集插件实例教程

Python实现E-Mail收集插件实例教程

__import__函数 我们都知道import是导入模块的,但是其实import实际上是使用builtin函数import来工作的。在一些程序中,我们可以动态去调用函数,如果我们知道...

Python设计模式之桥接模式原理与用法实例分析

Python设计模式之桥接模式原理与用法实例分析

本文实例讲述了Python设计模式之桥接模式原理与用法。分享给大家供大家参考,具体如下: 桥接模式(Bridge Pattern):将抽象部分与它的实现部分分离,使它们都可以独立地变化....

python3常用的数据清洗方法(小结)

python3常用的数据清洗方法(小结)

首先载入各种包: import pandas as pd import numpy as np from collections import Counter from sklear...

Python开发网站目录扫描器的实现

Python开发网站目录扫描器的实现

有人问为什么要去扫描网站目录:懂的人自然懂 这个Python脚本的特点: 1.基本完善 2.界面美观(只是画了个图案) 3.可选参数增加了线程数 4.User Agent细节处理 5.多...

Python中存取文件的4种不同操作

Python中存取文件的4种不同操作

前言: 最近开始学习tensorflow框架,选修课让任选一种框架实现mnist手写数字的识别分类。小詹也就随着大流选择了 tf 框架,跟着教程边学边做,小詹用了不同的神经网络实现了识别...