快捷導(dǎo)航

Python 實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)-循環(huán)隊(duì)列的操作方法

更新時(shí)間：2019年07月17日 09:53:32 作者：浩然haoran

這篇文章主要介紹了Python 實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)-循環(huán)隊(duì)列的操作方法,需要的朋友可以參考下

今天我們來到了循環(huán)隊(duì)列這一節(jié)，之前的文章中，我介紹過了用python自帶的列表來實(shí)現(xiàn)隊(duì)列，這是最簡單的實(shí)現(xiàn)方法。

但是，我們都知道，在列表中刪除第一個(gè)元素和刪除最后一個(gè)元素花費(fèi)的時(shí)間代價(jià)是不一樣的，刪除列表的第一個(gè)元素，那么在它之后的所有元素都要進(jìn)行移動。所以當(dāng)列表特別長的時(shí)候，這個(gè)代價(jià)就比較明顯了。我們本文介紹的循環(huán)隊(duì)列可以避免這個(gè)問題，同樣我們上篇文章提到的用鏈表實(shí)現(xiàn)的方法也可以避免。

下面，我們來介紹循環(huán)隊(duì)列。

循壞隊(duì)列

循環(huán)隊(duì)列，就是將普通的隊(duì)列首尾連接起來，形成一個(gè)環(huán)狀，并分別設(shè)置首尾指針，用來指明隊(duì)列的頭和尾。每當(dāng)我們插入一個(gè)元素，尾指針就向后移動一位，當(dāng)然，在這里我們隊(duì)列的最大長度是提前定義好的，當(dāng)我們彈出一個(gè)元素，頭指針就向后移動一位。

這樣，列表中就不存在刪除操作，只有修改操作，從而避免了刪除前面節(jié)點(diǎn)造成的代價(jià)大的問題。

好，話不多說，我們用代碼來實(shí)現(xiàn)一下

class Loopqueue:
 def __init__(self, length):
  self.head = 0
  self.tail = 0
  self.maxSize = length
  self.cnt = 0
  self.__list = [None]*length

這里同樣，我們定義一個(gè)隊(duì)列類，在實(shí)例化循環(huán)隊(duì)列的時(shí)候，要求指定隊(duì)列的大小，除了首尾指針以及隊(duì)列最大長度之外，我們還聲明一個(gè)表示隊(duì)列當(dāng)前長度的屬性cnt。

接下來我們給隊(duì)列增加一些操作：

判空

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

清空隊(duì)列

def clear(self):
  self.head = 0
  self.tail = 0
  self.cnt = 0
  return True

定義len和print函數(shù)

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，我們的循環(huán)隊(duì)列類就定義好了，如果你看過介紹隊(duì)列的文章，就會發(fā)現(xiàn)循環(huán)隊(duì)列和普通隊(duì)列的操作在邏輯上還是有一些相似的。

總結(jié)

以上所述是小編給大家介紹的Python 實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)-循環(huán)隊(duì)列的操作方法,希望對大家有所幫助，如果大家有任何疑問請給我留言，小編會及時(shí)回復(fù)大家的。在此也非常感謝大家對腳本之家網(wǎng)站的支持！
如果你覺得本文對你有幫助，歡迎轉(zhuǎn)載，煩請注明出處，謝謝！

您可能感興趣的文章: