今天我們來(lái)到了循環(huán)隊(duì)列這一節(jié)，之前的文章中项滑，我介紹過(guò)了用python自帶的列表來(lái)實(shí)現(xiàn)隊(duì)列，這是最簡(jiǎn)單的實(shí)現(xiàn)方法涯贞。
但是枪狂，我們都知道危喉，在列表中刪除第一個(gè)元素和刪除最后一個(gè)元素花費(fèi)的時(shí)間代價(jià)是不一樣的，刪除列表的第一個(gè)元素州疾，那么在它之后的所有元素都要進(jìn)行移動(dòng)辜限。所以當(dāng)列表特別長(zhǎng)的時(shí)候，這個(gè)代價(jià)就比較明顯了严蓖。我們本文介紹的循環(huán)隊(duì)列可以避免這個(gè)問(wèn)題薄嫡，同樣我們上篇文章提到的用鏈表實(shí)現(xiàn)的方法也可以避免。
下面颗胡，我們來(lái)介紹循環(huán)隊(duì)列毫深。
循壞隊(duì)列
循環(huán)隊(duì)列，就是將普通的隊(duì)列首尾連接起來(lái)毒姨， 形成一個(gè)環(huán)狀哑蔫，并分別設(shè)置首尾指針，用來(lái)指明隊(duì)列的頭和尾手素。每當(dāng)我們插入一個(gè)元素鸳址，尾指針就向后移動(dòng)一位，當(dāng)然泉懦，在這里我們隊(duì)列的最大長(zhǎng)度是提前定義好的稿黍，當(dāng)我們彈出一個(gè)元素，頭指針就向后移動(dòng)一位崩哩。
這樣巡球，列表中就不存在刪除操作，只有修改操作邓嘹，從而避免了刪除前面節(jié)點(diǎn)造成的代價(jià)大的問(wèn)題酣栈。
好，話不多說(shuō)汹押，我們用代碼來(lái)實(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ì)列最大長(zhǎng)度之外，我們還聲明一個(gè)表示隊(duì)列當(dāng)前長(zhǎng)度的屬性cnt妙痹。
接下來(lái)我們給隊(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ì)列類就定義好了，如果你看過(guò)介紹隊(duì)列的文章怯伊，就會(huì)發(fā)現(xiàn)循環(huán)隊(duì)列和普通隊(duì)列的操作在邏輯上還是有一些相似的琳轿。
代碼并不難，相信你已經(jīng)完全理解了，自己動(dòng)手操作一下吧崭篡。
你還了解哪些隊(duì)列類型呢挪哄？留言告訴我吧。
